Homework 10, due Friday, September 23, 2011

Recall that F1, F2, F3, ... is the Fibonacci sequence.

It's defined for n > 1 by the recursive rule that
Fn+1 = Fn + Fn-1
given that
F1 = F2 = 1.

By looking at patterns in class (Wed Sep 21) we found when n is odd that
(*)       F1 + F3 + F5 + ... + Fn = Fn+1.
Now we want to try to explain why this should always be true no matter how big of an odd number n is.

So we decided to see what kinds of similar statements hold. When n is even we looked at:
(**)     F2 + F4 + F6 + ... + Fn
Patterns suggested that this sum is always equal to Fn+1 - 1.

Here's another similar but slightly different problem. Start with any term of the Fibonacci sequence you like, say the ith one, Fi. Add on the next one and then every other one for as long as you like, as shown in the following sum (where the n in the sum must be odd):
(***)   Fi + Fi+1 + Fi+3 + Fi+5 + ... + Fi+n.

[1] Based on looking at patterns, we expect that the sum in (*) equals Fn+1 and that the sum in (**) equals Fn+1 - 1. So what should we expect (***) to equal? By looking at patterns, can you find an expression involving Fibonacci numbers for the sum (***) like what we found for (*) and (**)?

[2] Can you use the recursive rule Fn+1 = Fn + Fn-1 to justify your answer to [1]?