How many ways can $133$ be written as sum of only $1s$ and $2s$

Solution 1:

For $133$ ones there is $1$ outcome.

For $131$ ones and $1$ two there are $132$ outcomes.

For $129$ ones and $2$ twos there are ${131 \choose 2}$ outcome.

Thus there are ${133 \choose 0}+{133-1 \choose 1}+{133-2 \choose 2}+...+{133-66 \choose 66}$ outcomes, which is, as noted by Jack D'Aurizio, the 134th Fibonacci number (You may refer to Fibonacci number - Use in mathematics - WikiPedia article.)

Solution 2:

Hint: Note that the first digit in the sum is either a $1$ or a $2$, so the number of ways of getting a sum of $133$ is the number of ways of getting a sum of $132$ (add one at the beginning) plus the number of ways of getting a sum of $131$ (add two at the beginning).

Let's do it with the number of ways of getting to $5$.

If the first number in the sum is a $2$, the possibilities are $2+(2+1); 2+(1+2); 2+(1+1+1)$ which is the number of ways of getting to the total $3$ (see the bits in brackets) - which is three.

If the first digit is a $1$ then we have $1+(2+2); 1+(2+1+1); 1+(1+2+1); 1+(1+1+2); 1+(1+1+1+1)$ - the total in each bracket is $4$ and there are five ways of getting it.

So we get to $5$ in three plus five = eight ways.

Can you see that we would get to the total $6$ in five ($2$ first) plus eight($1$ first) = thirteen ways?

Solution 3:

I'll prove that this holds in general, not just for 133

Let $P_i$ be the solution to this problem for number $i$. That is, the answer to the exact question is $P_{133}$

Let $F_i$ be the $ith$ Fibonacci number.

Proof by induction that $\forall i\geq1:P_i = F_{i+1}$

Base:
$i=1$ Can make with only a single 1. So $P_1 = 1 = F_2$

Hypothesis:
Assume holds for $i=k$ and $i=k-1,k>1$

Step: Show that $P_k = F_{k+1} \rightarrow P_{k+1} = F_{k+2}$
From all solutions to $P_k$, we can add 1 and it is a solution to $P_{k+1}$.
From all solutions to $P_{k-1}$, we can add 2 and it is a solution to $P_{k+1}$
This is an exhaustive list of ways to make solutions to $P_{k+1}$, as going from any lower number, addings 1's and 2's will pass through either $P_k$ or $P_{k-1}$

Therefore
$P_{k+1} = P_k + P_{k-1} = F_{k+1} + F_k = F_{k+2}$ By hypothesis

(This is a bit of a crude proof. Mainly because I refer to $P_i$ as both a number and a set of solutions. But I think it gets the point accross)