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

Question

I was solving some basic Math Coding Problem and found that For any number $N$, the number of ways to express $N$ as sum of Odd Numbers is $Fib[N]$ where $Fib$ is Fibonnaci , I don't have a valid proof for this and didnot understand that how this can be solved using recurrences Can someone provide with it ?
If you are not getting it Suppose for N=4 number of ways to write it as sum of Odd Numbers is 3 which is Fibonnaci at $3$

$4=> 1+1+1+1$
$4=> 1+3$
$4=> 3+1$
NOTE-> the composition is ordered $( 1+3)$ and $(3+1)$ are different . UPD -> I do not claim that I observed it myself but in the problem solution I found it , I asked to just find some valid proof / reason to it

Answer 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.

Answer 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.