[Math] Proving that the number of compositions of n into positive odd summands is Fibonacci sequence

combinatorics

I'm currently stuck with a problem of proving that the number of compositions of natural $n$ into positive odd summands generates a Fibonacci sequence. (i.e. $4=1+1+1+1=3+1=1+3$)

My guess is that solution should be similar to proving that amount of partitions of rectangle $2$ x $n$ into rectangles $2$ x $1$ is also a Fibonacci sequence. This one is pretty simple and elegant.

So one guess to find the number of compositions of $n$, could be split in

$n$ = $1+(n-1)$

and

$n$ =$2+$ the_first_number_in_each_composition_of $(n-2)$ (i.e. $6_{(n-2)}=3+1+1+1=5+1=3+3$)

Thus the amount of compositions will be $\#(n)=\#(n-1)+\#(n-2)$

For me it seems like not a complete solution. Is there a more strict prove?

Best Answer

We can also map the compositions of n into odd parts to the compositions of n-1 into 1s and 2s (which is the same as the number of ways of dividing a 2x(n-1) rectangle into 2x1 rectangles) as follows:

Given a composition of n into odd parts, split each part into 0 or more 2s followed by a 1. Remove the final 1. You now have a composition of n-1 into 1s and 2s.

To go in reverse, given a composition of n-1 into 1s and 2s, add an extra 1 at the end and then group parts in sequences of 0 or more 2s that end in a 1. Sum each group of 2s followed by a 1 to get a composition of n into odd parts.

For example, the compositions of 5 into odd parts and 4 into 1s and 2s are related as follows:

1+1+1+1+1 <-> 1+1+1+1

1+1+3 <-> 1+1+2

1+3+1 <-> 1+2+1

3+1+1 <-> 2+1+1

5 <-> 2+2

Related Question