Fibonacci, compositions, history

Found it! (Sorry, Doug, ha ha.)

Augustus de Morgan added several appendices to his Elements of Arithmetic in the fifth edition, 1846 (available on Google Books). Appendix 10, pages 201-210, is "on combinations." The relevant paragraph is on 202-203.

Required the number of ways in which a number can be compounded of odd numbers, different orders counting as different ways. If $a$ be the number of ways in which $n$ can be so made, and $b$ the number of ways in which $n+1$ can be made, then $a+b$ must be the number of ways in which $n+2$ can be made; for every way of making $12$ out of odd numbers is either a way of making $10$ with the last number increased by $2$, or a way of making $11$ with a $1$ annexed. Thus, $1+5+3+3$ gives $12$, formed from $1+5+3+1$ giving $10$. But $1+9+1+1$ is formed from $1+9+1$ giving $11$. Consequently, the number of ways of forming $12$ is the sum of the number of ways of forming $10$ and of forming $11$. Now, $1$ can only be formed in $1$ way, and $2$ can only be formed in $1$ way; hence $3$ can only be formed in $1+1$ or $2$ ways, $4$ in only $1+2$ or $3$ ways. If we take the series $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, &c. in which each number is the sum of the two preceding, then the $n$th number of this set is the number of ways (orders counting) in which $n$ can be formed of odd numbers. Thus, $10$ can be formed in $55$ ways, $11$ in $89$ ways, &c.

He established "increasing" and "annexing" in deriving the formula for the number of what we now call compositions. He does not treat either of the other two restrictions mentioned above.

I make this an answer instead of a comment so as to bring it to the attention of others.

Using Google Books search for compositions "odd parts" Fibonacci brings up several modern combinatorics texts which might have a reference for the result. It also brings up a 1961 Canadian journal which only has a snippet view, but which might yield useful information. If the poster is still interested in tracking down the source, the search results may prove fruitful, especially as they may not have been available at the time of the first posting.

Gerhard "Ask Me About System Design" Paseman, 2012.02.10