Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

enter image description here

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

enter image description here

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

Partition , Composition

share|cite|improve this question
up vote 3 down vote accepted

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?

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.