# Homework Help: Induction and Fibonacci

1. Jun 30, 2008

### Moridin

1. The problem statement, all variables and given/known data

Show that $\forall n \in \mathbb{N}$, the number n can written as a sum of 1's and 2's in $F_{n+1}$ number of ways. $F_{n+1}$ is the n+1:th number in the Fibonacci numbers. The order of summation makes a difference only when you get different sequences eg. 3 = 1 + 1 + 1 = 2 + 1 = 1 + 2.

3. The attempt at a solution

(1) Show that it is true for n = 1:

The number one can be written as precisely one sum of the numbers 1 and 2:

1

This is also the second of the Fibonacci numbers.

(2) Show that if it is true for n = p, it is true for n = p + 1:

Assume that p can be written $F_{n+1}$ different ways as the sum of 1's and 2's.

It is clear that p + 1 can be written in at least as many ways, since you can just add a 1 to the different ways you can write p. However, I seem to be having some trouble with how many additional ways that it can be written. I imagine that since adding a 1 to the each of the earlier ways enables you to form additional ways by merging the added 1 to another 1 in the different sums where they happen to exist. However, for even numbers, there will be at least one way that includes only 2's, in which case this would not work.
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Jun 30, 2008

### Dick

Let P(n) be the number of ways to write n as the sum of a sequence of 1's and 2's. To get P(n+1) you can either append a 1 to a sequence that sums to n (a total of P(n) ways), or you can append a 2 to a sequence that sums to n-1 (a total of P(n-1) ways). Does that recursion remind you of Fibonacci?