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

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.

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.