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

Since last week I have been working on a way, how to sum $1$ and $2$ to have $133$.

So for instance we can have $133$ $1s$ or $61$ $s$2 and one and so on. Looking back to the example: if we sum: $1 + 1... + 1 = 133$ there is only one way. But for the second one there will be $131$ possible ways. And I have to do this for every possible combination. I am stuck with it and I have no idea whatsoever on how to begin.

Any ideas or methods I could use guys?

• Try the combinations of $\sum x_i$ = 133 where $x_i \in [0,1,2]$ not sure though 0 for the possible that the specific x wasn't required in the sum at all. – Mann May 6 '15 at 10:53
• The answer might be $^{135}C_{3}-^{133}C_{1}$ – Mann May 6 '15 at 10:58
• @Mann how did you get that? I do not quite understand it. – jumetaj May 6 '15 at 10:59
• @Mann the 0 can be shown up. So it only remains 1 and 2. Already thought of that but it is wrong – jumetaj May 6 '15 at 11:09
• Let $T_n$ be the number of ways to represent a number $n$ in ones and twos. Now, each way is counted if we consider a way of $T_{n-1}$ and add one, or if we consider a way of $T_{n-2}$ and add two. So $T_n=T_{n-1}+T_{n-2}$. – Shahab May 6 '15 at 11:27

Hint: $$[x^{133}]\,\frac{1}{1-(x+x^2)}=F_{134}=4517090495650391871408712937.$$

More information and context can be found in the questions here and here. Just to be clear, the number we want to compute is given by the coefficient of $x^{133}$ in the sum: $$1+(x+x^2)+(x+x^2)^2+(x+x^2)^3+\ldots = \frac{1}{1-(x+x^2)}$$ and since the Taylor coefficients $a_n$ of the function $$f(x)=\frac{1}{1-x-x^2}=\sum_{n\geq 0}a_n\,x^n\tag{1}$$ obey the recurrence relation: $$a_{n+2}=a_{n+1}+a_{n}$$ (to prove it, it is sufficient to multiply both sides of $(1)$ by $1-x-x^2$), the solution is given by a Fibonacci number, since $a_0=1=F_1$ and $a_1=1=F_2$.

• @JackDAurizio how did you get this formula? And what value does x get? – jumetaj May 6 '15 at 11:10
• Even I am interested! Please explain! – Mann May 6 '15 at 11:14
• This is not a fair hint or a complete answer. – jwg May 6 '15 at 12:42
• It is not a good hint because it gives the complete answer. It is not a good answer because it does not give any explanation. The OP is not the only intended audience of answers to this question. – jwg May 6 '15 at 12:48
• Jack, you should probably elaborate for the community's sake. I, too, am interested in what you did but I don't see your logic at all. – Bliebervik May 6 '15 at 13:16

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.)

• thanks buddy now I understood it. – jumetaj May 6 '15 at 11:27

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?

• Well yeah. But I have to do it when there are 2 2s and the rest 1 and so on. That is where I cannot determine a formula @mark – jumetaj May 6 '15 at 10:55
• @jumetaj I've added an example to show what I mean - do you recognise the numbers which are turning up for the low examples? – Mark Bennet May 6 '15 at 12:36

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)

This is essentially an explanation of Jack D'Aurizio's answer.

Let $k$ be the number of twos, then we have $n-2k$ ones. There are then $$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}=\sum_{k=0}^\infty\binom{n-k}{n-2k}$$ ways to write $n$ as a sum of ones and twos. One way to compute this number is to look at the generating function. \begin{align} \sum_{n=0}^\infty\sum_{k=0}^\infty\binom{n-k}{n-2k}x^n &=\sum_{k=0}^\infty x^{2k}\sum_{n=0}^\infty\binom{-k-1}{n-2k}(-x)^{n-2k}\\ &=\sum_{k=0}^\infty\frac{x^{2k}}{(1-x)^{k+1}}\\ &=\frac1{1-x}\frac1{1-\frac{x^2}{1-x}}\\ &=\frac1{1-x-x^2} \end{align} Which is the generating function for $F_{n+1}$, the Fibonacci numbers offset by $1$. Setting $n=133$, we get $$F_{134}=4517090495650391871408712937$$

Consider for instance how many ways to make a sum of 1? Then of 2?

To make a sum of 3, you can add a 2 to all the ways to make a sum of 1, and a 1 to all the ways to make a sum of 2 (so the number of ways of making 3 is the sum of the ways of making 2 plus the number of ways of making 1). For a total of 4, you can add a 2 to the ways to make 2, and a 1 to the ways to make 3...

Ok, Here is a simple answer that you can explain to an elementary school student. The answer is 67. First you make 133 by using as many twos as possible, which is 133/2 = 66. That gives you one way of making 133. Now you can look at the number of twos in your answer, and you can add another way by splitting one of those twos into ones. Since you have 66 twos, you will get 67 ways of making 133.

• Basically, you pick the number of 2's that you want (0 up to 66 of them) and the rest are 1's. – TravisJ May 6 '15 at 18:20
• That would be the answer if the order doesn't matter, but the OP distinguishes $1+2$ and $2+1$, so the number is much larger. – Daniel Fischer May 6 '15 at 19:03
• I think you are reading too much into it. I see no such distinction in his Question. – Mauser May 7 '15 at 19:54

This problem could be formulated as follows:

A rectangle $133\times1$ is given and dominoes $1\times1$ and $2\times1$. In how many ways can one cover the rectangle with dominoes?

The result can be obtained by induction like shown in other answers or there are other methods like cutting rectangle approximately in half.

However, the beauty of the reformulation is that there are many generalizations with different rectangles and dominoes, and their result involves Fibonaccies too. See here for example.

See also paper New Proofs of Some Fibonacci Identities for many other examples.