Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Find the number of ways to write 17 as a sum of 1’s and 2’s if order is relevant.

share|cite|improve this question

You need $k$ twos and $17-2k$ ones, where $0 \leq k \leq 8$.

For each particular $0 \leq k \leq 8$, you have exactly $17-k$ terms in the sum, and the order is determined by the positions of the $k$ twos. Thus you have exactly $\binom{17-k}{k}$ sums containing $k$ twos.

Hence, your number is

$$\sum_{k=0}^8 \binom{17-k}{k}$$

share|cite|improve this answer

Let $A_n$ be the number of ways to represent $n$. Note that any representation of $n$ ends with $1$ or with $2$. There are by definition $A_{n-1}$ representations of $n-1$, so there are $A_{n-1}$ representations of $n$ that end with $1$. Similarly, there are $A_{n-2}$ representations of $n$ that end with $2$. It follows that $$A_n=A_{n-1}+A_{n-2}.\tag{$1$}$$ This is a well-known recurrence, the Fibonacci Recurrence. The "next" number is always the sum of the previous two.

We have $A_1=1$ and $A_2=2$. Now we can use the Recurrence $(1)$ to compute $A_{17}$ relatively quickly.

Here is a start: $A_3=A_2+A_1=3$, $A_4=A_3+A_2=5$, $A_5=8$, $A_6=13$, $A_7=21$, $A_8=34$, $A_9=55$. We are halfway there.

Remark: There are shortcuts available for computing the Fibonacci numbers, but for $17$ it is not clear they are worth the trouble.

share|cite|improve this answer
Neat solution.... – N. S. Oct 8 '12 at 0:27

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.