Can Every Number Be Expressed as a Sum of 1's and 2's in Fibonacci Ways?

[Moridin]

Homework Statement

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.

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.

 

[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?