Conditionally combining vanilla and chocolate ice cream scoops Suppose I have a plate that fits $n$ number of ice cream scoops. I can choose between vanilla and chocolate flavors. The only condition is that I cannot scoop for chocolate twice in a row, e.g. if $n=5$ then {$v,c,c,v,c$} is not allowed - an impossible combination - but {$c,v,c,v,c$} or {$v,v,v,v,c$} is allowed.
How many possible combinations are there? I know I have to perform the operation $${n \choose 2} - \text{impossible combinations}$$
But just how do I figure out the number of impossible combinations?
 A: You want binary sequences not containing two consecutive ones.
Let $f(n)$ be the number of such sequences of length $n$.
then we have $f(1)=2,f(2)=3$.
After this we use the recursion $f(n)=f(n-1)+f(n-2)$.
Why? seperate the strings of lentgh $n$ into two kinds, those ending in $1$ and those ending in $0$.
How many end in $0$? $f(n-1)$, since after removing the last digit you must have a valid sequence of length $n-1$.
How many end in $1$? $f(n-2)$ since the secon to last digit must be $0$, and then the first $n-2$ must form a valid sequence.
Thus the sequence goes, $1,2,3,5,8,13\dots$ And so on, it is a tail of the Fibonacci sequence.
A: There are $2^{5}$ possible combinations. We want a recurrence to help us out. So let $T(1)$ be our recurrence denoting the number of allowed combinations for a string of length $n$. So $T(1) = 2$. Similarly, $T(2) = 2^{2} - 1 = 3$, giving us $vv, vc, cv$. Now for $T(3)$, we cannot have $ccv, vcc, ccc$. So there are $2^{3} = 8$ possible combinations and we exclude three, leaving $T(3) = 5 = T(2) + T(1)$.
So more generally, $T(n) = T(n-1) + T(n-2)$ with initial conditions $T(1) = 2$, $T(2) = 3$. We set up the characteristic polynomial and solve:
$\lambda^{2} - \lambda - 1 = 0$, which gives us eigenvalues $\lambda = \frac{ 1 \pm \sqrt{5}}{2}$. 
The general form equation is: $T(n) = A \cdot (\frac{1 + \sqrt{5}}{2})^{n} + B \cdot (\frac{1 - \sqrt{5}}{2})^{n}$.
Now plug in your initial conditions and solve.
The number of impossible combinations is $2^{n} - T(n)$.
Edit: Proving T(n) holds by induction. The base cases are given in my analysis above for $T(1), T(2)$. So assume true up to $n-1$ and consider case $n$.
Now look at $T(n)$ and remove the last flavor added. If it was vanilla, there are $T(n-1)$ ways of constructing such a sequence. By the inductive hypothesis, $T(n-1)$ correctly counts the number of valid $n-1$ configurations. So adding vanilla is valid. 
If the last flavor is instead chocolate, we note that the flavor before last is vanilla (otherwise, the configuration would be invalid). So there are $T(n-2)$ such strings so that the $n-1$ flavor is vanilla. And then the $n$th flavor is chocolate. Thus, $T(n) = T(n-1) + T(n-2)$, exhausting all valid possibilities.
So by the principle of mathematical induction, $T(n)$ correctly counts the valid configurations for your problem.
A: We reason by cases. Suppose that we place down $k$ vanilla scoops first. This leaves $k + 1$ gaps, each of which will either contain exactly $0$ or exactly $1$ of the $n - k$ remaining chocolate scoops (since we can't have more than $1$ chocolate scoop in the same gap). This can be done in $\binom{k+1}{n-k}$ ways. Summing over each possible value of $k$ (that is, from $k = 2$ to $k = 5$), we obtain:
$$
\binom{3}{3} + \binom{4}{2} + \binom{5}{1} + \binom{6}{0} = 1 + 6 + 5 + 1 = 13
$$
