Number of ways to represent any N as sum of odd numbers? [duplicate]

Solution 1:

Let's say $S(n)$ is the set of ways to write $n$ as a sum of odd numbers.

We can partition this set into two subsets: $A(n)$ and $B(n)$, where $A(n)$ is the set of sums where the last summand is a $1$, and $B(n)$ is the set of all other sums.

Can you see why $A(n)$ has the same size as $S(n-1)$? Can you see why $B(n)$ has the same size as $S(n-2)$?

If you prove this, you find that $|S(n)| = |A(n)| + |B(n)| = |S(n-1)| + |S(n-2)|$, which is the Fibonacci recurrence relation. You can then prove by induction that your sequence is equal to the Fibonacci sequence.

Solution 2:

We have from first principles that the number of compositions into odd parts is given by

$$[z^N] \sum_{q\ge 1} \left(\frac{z}{1-z^2}\right)^q.$$

This simplifies to

$$[z^N] \frac{z/(1-z^2)}{1-z/(1-z^2)} = [z^N] \frac{z}{1-z-z^2}.$$

Now $$F(z) = \frac{z}{1-z-z^2}$$ is the OGF of the Fibonacci numbers and we have the claim.