12
$\begingroup$

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

Improve this question
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Last summand is 1? why is that coming ? $\endgroup$ – Kartik Bhatia Nov 27 '20 at 21:06
  • 1
    $\begingroup$ 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). $\endgroup$ – Magma Nov 27 '20 at 21:20
  • $\begingroup$ what does A(5) signify here? $\endgroup$ – Kartik Bhatia Nov 27 '20 at 21:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Magma Nov 27 '20 at 21:24
  • $\begingroup$ 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 $\endgroup$ – Kartik Bhatia Nov 27 '20 at 21:26
4
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Kartik Bhatia Nov 27 '20 at 21:13
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Nov 27 '20 at 21:15
  • $\begingroup$ where is it coming from OGF , z and all stuff ? is this linear algebra? $\endgroup$ – Kartik Bhatia Nov 27 '20 at 21:18
  • $\begingroup$ Learn more at Wikipedia on the Fibonacci number OGF. $\endgroup$ – Marko Riedel Nov 27 '20 at 21:21
  • $\begingroup$ Thanks for it :) , $\endgroup$ – Kartik Bhatia Nov 27 '20 at 21:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.