In how many ways is possible to write a number as the ordered sum of $1$ and $2$

Question

In how many ways is possible to write a number as the ordered sum of $ 1$ and $2$.

By looking at the first (positive) integers:

$1: (1) \to 1\ \text{ways}$

$2: (1,1), (2) \to 2\ \text{ways}$

$3: (1,1,1), (2,1), (1,2) \to 3\ \text{ways}$

$4: (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2) \to 5\ \text{ways}$

If $Q_n$ denotes the number we need to find the number of ordered sums of, then

$$Q_n = F_{n+1}$$

Where $F_{n+1}$ denotes the $n+1$ term of the Fibonacci Sequence.

Is there a proof of this?

It is evident that if the number $m$ 2's and $r$ 1's will give ${m +r \choose m,r}$ different sums which give $Q_n$, but I have no idea how to connect this with Fibonacci or whether there is another way to prove it.

Maybe I'm trying to reinvent the wheel.

Answer 1

It's a relatively simple proof. We know that their is one way to add 1 and 2 up to get to 0, namely $0=0$. So $G_0 = 0$. A similar thing holds for $G_1 = 1$. Now let's assume we know $G_{n-1}$ and $G_{n-2}$. For every combination represented in $G_{n-1}$ we can add 1 to get combinations in $G_{n}$. We can similarly add 2 to each combination in $G_{n-2}$. These combinations are distinct since they add up different numbers. Therefore $G_n = G_{n-1} + G_{n-2}$, the same recurrence relation the Fibonacci numbers have. Since $G_0 = G_1 = 1$, the same initial values of the Fibonacci sequence, we know that the sequences will be identical.

Answer 2

We can prove this using direct proof.

Hypothesis: For Fibbonaci number $F_1=1, F_2=1, F_{n}=F_{n-1}+F_{n-2}$, $Q(k)=F_{k+1}$

We say that we have constructed every order of $Q(n)$. Then, we construct $Q(n+1)$ this way:

1. For all orders, we add $+1$ to change $n$ to $n+1$. (There are now $Q(n)$ numbers.) Note: all numbers that are constructed here ends in $+1$.
2. For all orders that end with $+1$, we change it to $+2$. We shall prove that the amount will be $Q(n-1)$ to complete the proof. Note: all numbers that are constructed here ends in $+2$.

It can be seen that by constructing in this way there contains all orders.

Proof of step 2: If we constructed $Q(n)$ in the way above, then all numbers ended in $+1$ will be the amount $Q(n-1)$ by step 1. above, and we are done.