Proving that the number of compositions of n into positive odd summands is Fibonacci sequence 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?
 A: Suppose the number of compositions of n into odd parts is c(n). For even n we have
$$c(n) = c(n-1) + c(n-3) + c(n-5) + ... + c(1)$$
because we can add a 1 to each of compositions of n-1, or add a 3 to each of the compositions of n-3 etc.
For odd n we have
$$c(n) = c(n-1) + c(n-3) + c(n-5) + ... + c(2) + 1$$
where the extra +1 at the end is to account for the singleton composition n=n (which does not occur if n is even).
The Fibonacci numbers satisfy the same recurrence relations, and we also have c(1)=F(1)=1 and c(2)=F(2)=1, so we can prove by induction that c(n)=F(n) for all positive n.
A: 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
