Homework 10, due Friday, September 23, 2011<br><br>

Recall that F<sub>1</sub>, F<sub>2</sub>, F<sub>3</sub>, ... is the Fibonacci sequence.<br><br>
It's defined for n > 1 by the recursive rule that <br>
&nbsp &nbsp &nbsp F<sub>n+1</sub> = F<sub>n</sub> + F<sub>n-1</sub> <br>
given that<br> 
&nbsp &nbsp &nbsp F<sub>1</sub> = F<sub>2</sub> = 1.<br><br>


By looking at patterns in class (Wed Sep 21) we found when n is odd that<br>
(*) &nbsp &nbsp &nbsp F<sub>1</sub> + F<sub>3</sub> + F<sub>5</sub> + ... + F<sub>n</sub> = F<sub>n+1</sub>.<br>
Now we want to try to explain why this should always be true no matter how big of an odd number n is.<br><br>

So we decided to see what kinds of similar statements hold. When n is even we looked at:<br>
(**) &nbsp &nbsp F<sub>2</sub> + F<sub>4</sub> + F<sub>6</sub> + ... + F<sub>n</sub><br>
Patterns suggested that this sum is always equal to F<sub>n+1</sub> - 1.<br><br>

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

(***) &nbsp F<sub>i</sub> + F<sub>i+1</sub> + F<sub>i+3</sub> + F<sub>i+5</sub> + ... + F<sub>i+n</sub>.<br><br>

[1] Based on looking at patterns,
we expect that the sum in (*) equals F<sub>n+1</sub> and that the 
sum in (**) equals F<sub>n+1</sub> - 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 (**)?<br><br>

[2] Can you use the recursive rule F<sub>n+1</sub> = F<sub>n</sub> + F<sub>n-1</sub> to 
justify your answer to [1]?

</body>
</html>