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?

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.
