Find the number of ways to write 17 as a sum of 1’s and 2’s if order is relevant.
Find the number of ways to write 17 as a sum of 1’s and 2’s if order is relevant.
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}$
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.
-
0Neat solution.... – 2012-10-08