Representing a nonnegative integer as the ordered sum of odd numbers

Question

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.

Answer 1

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}$.