Homework 10, due Friday, September 23, 2011

Recall that F_{1}, F_{2}, F_{3}, ... is the Fibonacci sequence.

It's defined for n > 1 by the recursive rule that

F_{n+1} = F_{n} + F_{n-1}

given that

F_{1} = F_{2} = 1.

By looking at patterns in class (Wed Sep 21) we found when n is odd that

(*) F_{1} + F_{3} + F_{5} + ... + F_{n} = F_{n+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:

(**) F_{2} + F_{4} + F_{6} + ... + F_{n}

Patterns suggested that this sum is always equal to F_{n+1} - 1.

Here's another similar but slightly different problem. Start with any term
of the Fibonacci sequence you like, say the ith one, F_{i}. 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):

(***) F_{i} + F_{i+1} + F_{i+3} + F_{i+5} + ... + F_{i+n}.

[1] Based on looking at patterns,
we expect that the sum in (*) equals F_{n+1} and that the
sum in (**) equals F_{n+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 F_{n+1} = F_{n} + F_{n-1} to
justify your answer to [1]?