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

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

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.

• Last summand is 1? why is that coming ? – Kartik Bhatia Nov 27 '20 at 21:06
• Example: $S(5) = \{1{+}1{+}1{+}1{+}1, 1{+}1{+}3, 1{+}3{+}1, 3{+}1{+}1, 5\}$, $A(5) = \{1{+}1{+}1{+}1{+}1, 1{+}3{+}1, 3{+}1{+}1\}$, $B(5) = \{1{+}1{+}3, 5\}.$ You can see that A(5) has the same size as S(4) and B(5) has the same size as S(3). – Magma Nov 27 '20 at 21:20
• what does A(5) signify here? – Kartik Bhatia Nov 27 '20 at 21:21
• A(5) is the set of all possible ways to write $5$ as a sum of odd numbers. $A(12)$ is the set of all possible ways to write $12$ as a sum of odd numbers. – Magma Nov 27 '20 at 21:24
• getting you now , Understood the solution , :) will accept your answer later , just finding out new ways to do it as well like this ogz one – Kartik Bhatia Nov 27 '20 at 21:26

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.

• what is this using first principles ? I think I dont know this much But I surely want to learn any Resources for understanding ur solution better – Kartik Bhatia Nov 27 '20 at 21:13
• The OGF $z/(1-z^2)$ gives a single odd part so $(z/(1-z^2))^q$ gives a composition into $q$ odd parts. We have $q\ge 1$ parts hence the sum. – Marko Riedel Nov 27 '20 at 21:15
• where is it coming from OGF , z and all stuff ? is this linear algebra? – Kartik Bhatia Nov 27 '20 at 21:18
• Learn more at Wikipedia on the Fibonacci number OGF. – Marko Riedel Nov 27 '20 at 21:21
• Thanks for it :) , – Kartik Bhatia Nov 27 '20 at 21:22