# composition of a number using 1 and 2

The number of partitions of n in which all parts are 1 or 2 is

Similarly how can I formulate the number of compositions formed using 1 or 2. I could come up with a following series. if n=7. then the number of compositions using 1 and 2 are 21 and are given by series

How can I form a formula to calculate the sum of this series ?

-

## 1 Answer

Let $F(n)$ be the number of compositions of $n$ by $1$ and $2$. A composition of $n$ can either end in $1$ or $2$. There are $F(n-1)$ that end in $1$ and $F(n-2)$ that end in $2$, so we have $F(n)=F(n-1)+F(n-2)$. Does that look familiar?

-
fibonacci series right ? And the fastest way to calculate the sum would be fibonacci exponentiation.Please correct me if I am wrong. –  g4ur4v Feb 2 '13 at 21:06
@g4ur4v: Exactly right. You need to think a bit about how this $n$ matches up with the indices of the Fibonacci series. –  Ross Millikan Feb 2 '13 at 21:42