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?

 A: 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}$. 
A: (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$.
A: 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}|$...
A: 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.
