1    Introduction

The goal of this writing assignment is to prove several theorems on the Fibonacci sequence of numbers, culminating in the Binet representation which expresses fn  as a formula in n.

2    Instructions

Below are the detailed instructions.

1. Define what is meant by a sequence of numbers, {an }1(o) .

2.  Define what it means for a sequence to be defined recursively.  Give two examples other then the Fibonacci sequence

3. Define the Fibonacci sequence.

4. Write a brief history of the Fibonacci sequence (in your own words).

5. Prove at least two of the following:

5.1 Let F =『1(0)   1(1)← and n e ←, n > 2. Prove that Fn  = ← . 5.2. Prove fn fn+2 - fn(2)  = (-1)n  holds for all n e ← .

5.3 Prove that fn(2) + fn(2)+1  = f2n+1  holds for all n e ← . Hint: F2n  = Fn Fn .

5.4 Prove that f2 + f4 + . . . + f2n  = f2n+1 - 1.

6. Prove at least one of the following.

6.1 Let sn be the number of ways of expressing n as a sum of one’s and two’s where the order counts; that is, 1 + 2 and 2 + 1 are considered different. Compute the first six values of sn and convince yourself that sn  = fn+1 .  Let n be a natural number and set h =「|.  Prove when expressing n as a sum of one’s and two’s the number of ways to do so with k two’s, k < h and n - 2k ones is ╱n k(-)k、and conclude that

k=「│

6.2 A subset U of {1, 2, . . . , n} is unfriendly if it does not contain any consecutive numbers, equivalently, if k  < l are in U then l - k  >  1.  Denote by un  the number of unfriendly subsets contained in {1, 2, . . . , n}? Note the empty set if unfriendly and needs to be counted. Compute the first six values of un and convince yourself that un  = fn+1 . Prove this statement.