Take the 2-minute tour ×

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

share|improve this question

2 Answers 2

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|improve this answer
Neat solution.... –  N. S. Oct 8 '12 at 0:27

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

Your Answer


