Representing a nonnegative integer as the ordered sum of odd numbers Numbers of ways of representing a nonnegative integer as the ordered sum of odd numbers. For the first numbers we find that:
$0 \to 0\quad \text{ways}$
$1 \to 1\quad \text{way}$
$2: (1,1) \to 1\quad \text{ways}$
$3: (1,1,1), (3) \to 2\quad \text{ways}$
$4: (1,1,1,1), (3,1), (1,3)\to 3\quad \text{ways}$
$5: (1,1,1,1,1), (3,1,1), (1,3,1), (1,1,3), (5)\to 5\quad \text{ways}$
So, if $A_n$ is the numbers of ways to represent the nonnegative integer n as the ordered sum of $n$ (nonnegative) odd numbers, then $A_n = F_n$ where $F_n$ is the Fibonacci number.
How could this be proved? 
I was trying to prove this by induction, but I'm having problems with the induction step. I really don't know what to do there.
 A: EDIT: added the formal proof that the method described below works fine.
The base case has already been proven by you.
Now imagine all numbers up to $n-1$ can be written as you ask, in $a_{n-1}$ ways.
How can you write $n$? You can do one of two things:
You either take a way of writing $n-1$ and append a $1$ to its end, or you look at a way of writing $n-2$ and add $2$ to its last number. Because $a_{n-1}$ and $a_{n-2}$ take into consideration all permutations, it suffices to append the $1$ in the end and to sum the $2$ in the last position, therefore
$$a_n = a_{n-1} + a_{n-2}$$
We will make an example, showing that $a_6 = 8$.
We first append a $1$ to all the ways of writing 5:
$(1,1,1,1,1,1),(3,1,1,1),(1,3,1,1),(1,1,3,1),(5,1)$
And now add $2$ to the last entry in the ways of writing 4:
$(1,1,1,3),(3,3),(1,5)$
Therefore adding up to 8 different ways.
PROOF for the skeptical:
We shall use $(a_1, a_2, \cdots, a_k)$ as the notation for $\sum_{i=1}^{k} a_i$ Now assume that $(a_1, a_2, \cdots, a_k)$ is a way of writing $n$ as the sum of odd numbers. Then one of two things can happen:


*

*$a_n = 1$

*$a_n \ge 3$


Suppose $a_n = 1$. Then the sequece $(a_1, a_2, \cdots, a_{k-1})$ represents $n-1$. On the other hand, if $a_n \ge 3$ then the sequence $(a_1, a_2, \cdots, a_k-2)$ represents $n-2$. This means that for every sequence $(a_1, a_2, \cdots, a_k)$ you can uniquely connect it to, or a sequence for $n-1$, or a sequence for $n-2$. Since you can create these injections in both directions, you show that both sets of sequences have the same cardinality and therefore $a_n = a_{n-1} + a_{n-2}$.
