Take the 2-minute tour ×
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.

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
add comment

2 Answers

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
add comment

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
add comment

Your Answer

 
discard

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.