Let the number of ordered partitions of $n$ with odd parts be $f(n)$. Find the generating function $f(n)$ .
My try : For $n=1$ we have $f(1)=1$, for $n=2$, $f(2)=1$, for $n=3$, $f(3)=2$, for $n=4$, $f(4)=3$, for $n=5$,$f(5)=5$, for $n=6$, $f(6)=8$, for $n=7$, $f(7)=13$ ,for $n=8$, $f(8)=21$. $f(n)$ follows a Fibonacci sequence. Now, if I can derive the recursion $f(n+2)=f(n+1)+f(n)$ then we are done . But how can I prove that $f(n)$ is a Fibonacci sequence. Can induction help here? Can anyone suggest any other method ? Any help would be appreciated .
To show that a count satisfies the Fibonacci recurrence, show how each object can be generated in exactly one way from an object smaller by either $1$ or $2$. In the present case, of the compositions of $n+2$ into odd parts, the ones ending in $1$ are in bijection with the compositions of $n+1$ obtained by omitting the $1$, and the ones not ending in $1$ are in bijection with the compositions of $n$ obtained by subtracting $2$ from the last part.