How many ways can a number $k$ number be written as a sum of $1$s and $2$s?

Question

The order of the numbers does matter, which means that for $k=4$ $4= 1+1+1+1,1+1+2,1+2+1,2+1+1,2+2$ I have calculated it until $k=6$ and I get that the number of the valid calculations are:$1,2,3,5,8,13$. I assume that this is about the Fibonacci numbers, but in which way can I show it?

Answer 1

We can prove this using direct proof. First, we let $Q(k)$ be the number of ways can a number $k$ be written as a sum of 1s and 2s.

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.