Fibonacci sequence

Given an integer $n ≥ 1$, let $f_n$ be the number of lists whose elements all equal $1$ or $2$ and add up to $n−1$. For example $f_1 = 1 = f_2$ because only the empty list ($0$ ones and $0$ twos) sums to $0$ and only a single one sums to $1$. The lists $1,2;\, 2,1;\, 1,1,1$ show us that $f_4 = 3$.

(a) Show that $f_{n+2} = f_{n+1} + f_n$ and hence that $f_1, f_2,...$ is the Fibonacci sequence.

(b) How many lists of ones and twos are there that add up to $10$ and contain $3$ twos?

-

4 Answers

Given a list of $1$s and $2$s adding up to $n-1$, we can append a $2$ to the end of that list to get one adding up to $n+1$. Given a list of $1$s and $2$s adding up to $n$, we can append a $1$ to the end of that list to get one adding up to $n+1$. The lists obtained in this way are uniquely determined by the lists we started from. (Why?) Hence, $$f_{n+2}\geq f_{n+1}+f_n.$$ On the other hand, given a list of $1$s and $2$s adding up to $n+1$, removing the last number on the list will give us one adding up to $n$ or $n-1$. Hence, $$f_{n+2}\leq f_{n+1}+f_n,$$ and so $$f_{n+2}=f_{n+1}+f_n.$$

A list of $1$s and $2$s adding up to $10$ and having $3$ $2$s will necessarily have $7$ total entries. (Why?) Such a list is moreover completely determined by the placement of the $2$s. Since there are $7$ spots and $3$ $2$s to place, there are $\binom{7}{3}=35$ such lists.

-
can you please help me solve this Consider the ﬁnite sum S=1+2x+3x^(2)+4x^(3)+____+nx^(n-1) Calculate S − xS and hence give a closed expression for S? –  ofo Feb 24 '13 at 19:36
The site will only allow you to ask $6$ questions in a given $24$-hour period. If you wait until tomorrow, you can post that as a question. –  Cameron Buie Feb 24 '13 at 20:58

The first question has appeared several times on MSE.

For the second, there is some ambiguity: Do we mean contain (i) exactly $3$ twos or (ii) at least $3$ twos?

For (i), if there are exactly $3$ twos, then there must be $4$ ones, a total of $7$ digits. The locations of the twos can be chosen in $\dbinom{7}{3}$ ways. After the location of the twos is determined, the ones have to occupy the remaining slots. Calculate: there are $35$ choices.

For interpretation (ii), we are allowed to have $3$ twos, or $4$, or $5$. The analysis is much the same as for interpretation (i), except that we get $\dbinom{7}{3}+\dbinom{6}{4}+\dbinom{5}{5}$.

-
can you please help me solve this Consider the ﬁnite sum S=1+2x+3x^(2)+4x^(3)+____+nx^(n-1) Calculate S − xS and hence give a closed expression for S? –  ofo Feb 24 '13 at 19:36
To do it in the style they ask for, note that $xS=x+2x^2+3x^3+\cdots +nx^n$. Now calculate $S-xS$. This is $(1+2x+3x^2+\cdots+nx^{n-1})-(x+2x^2+\cdots+(n-1)x^{n-1}+nx^n)$. Look at the terms. We get a $1$. Also a $2x-x$. Also a $3x^2-2x^2$, and so on. We end up with (check it) $1+x+x^2+\cdots +x^{n-1}-nx^n$. The first part is a finite geometric series, with sum $\frac{1-x^n}{1-x}$, if $x\ne 1$. So we end up with $(1-x)S=\frac{1-x^n}{1-x}-nx^n$. Divide by $1-x$ to get $S$. –  André Nicolas Feb 24 '13 at 19:50
thank you very much –  ofo Feb 24 '13 at 20:06
@Aka: You are welcome. But in general I would prefer not to type much mathematics in comments, the editing facilities are poor, the length severely limited. –  André Nicolas Feb 24 '13 at 20:42

(a) should come from the fact that when you delete the final element of a list which sums to $n+2$ you may end up with a list that sums to $n+1$ (if you deleted a $1$) or to $n$ (if you deleted a $2$).

As to (b), you are talking of lists of length $7$, containing four $1$ and three $2$. This should be stars and bars (Theorem Two) which yields $$\binom{4 + 4 - 1}{4} = \binom{7}{4} = 35.$$ That is, you have to put your four $1$ in four bins (separated by the three $2$), and some bin may be empty.

PS I have read the post of @AndréNicolas. I have intended question (b) as requiring exactly three $2$.

-
can you please help me solve this? Consider the ﬁnite sum S=1+2x+3x^(2)+4x^(3)+____+nx^(n-1) Calculate S − xS and hence give a closed expression for S? –  ofo Feb 24 '13 at 19:35
@Aka, please post a separate question if you wish. Comments are not the place to start new questions. –  Andreas Caranti Feb 24 '13 at 19:37
i tried posting but the website didnt accept my question post –  ofo Feb 24 '13 at 19:39

Let $L_k$ the set of lists whose elements all equal $1$ or $2$ and add up to $k$. You want to show that $f_n=|L_n|$.
Note that $\ell\in L_{n-2}\Rightarrow \text{append}(\ell,2)\in L_n$ and $\ell \in L_{n-1}\Rightarrow \text{append}(\ell,1)\in L_n$. Conclude that $|L_{n-2}|+|L_{n-1}|\leq |L_{n}|$...

-