Show that $\forall n \in \mathbb{N}: n$ can be written as $F_{n+1}$ different sums of ones and twos where the order matter.
Presumably, mathematical induction can be leveraged here.
Step 1: Show that it is true for n = 1:
$1$ can be written as $F_{1+1} = F_{2} = 1$ different sums of ones and twos.
Step 2: Show that if it is true for n = p, it s true for n = p + 1:
$p + 1$ consists of two terms, $p$ and $1$. The $p$ term can, according to the assumption, be written as $F_{p+1}$ different sums. Adding 1 to p can be done as the first term, anywhere in the sum or at the end. Thus, there are $F_{p+1} + p + 1$ ways of doing it. We can also imaging stuffing this last $1$ term into another $1$ in the sum and making a 2. But how many ways this can be done depends on how many of the terms in the sum is a 1? Or it does not matter how many they are, since they can be rearranged anyways? That would suggest that there are $F_{p+1} + p + 1 + p$ ways?
This does not seem quite right as there is no reason to suppose that $p$ or $p + 1$ are Fibonacci numbers and can be arranged with $F_{p+1}$ into another Fibonacci number $F_{p+2}$.
I feel like I am missing some key insight here. Sure, the question makes me think of combinatorics ("order does not matter") and 1 and 2 are obviously themselves Fibonacci numbers...
What are some more productive approaches?
This is not true.
$3$ can be written in only $2 \neq F_4$ ways: $2+1$ and $1+1+1$.
Now, the statement is true, if the order does matter. In that case, here is a hint:
Hint In how many ways can you write $n+1$ as a sum of $1'$s and $2$'s, if the last term in the sum is $1$? What if the last term is $2$?