# 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?

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.

• $2^5$ possible combinations for $n = 5$? – Don Larynx Dec 22 '14 at 22:45
• Yes. This is a "word" problem. There are five slots: $_ _ _ _ _$. Each slot can have vanilla or chocolate, and is independent of the others. So by rule of product, we multiply, giving us $2^{5}$ possible combinations, before we impose the restriction. – ml0105 Dec 22 '14 at 22:46
• How do we know that this is a Fibonacci sequence for all $n$? – Don Larynx Dec 22 '14 at 22:53
• You can prove it by induction. We have our base cases of $n = 1, 2$ taken care of by my explanation in the post. So suppose up to $n$ and look at the $n+1$ case. Use the $n-1, n$ cases to derive that this must be true for $T(n+1)$. – ml0105 Dec 22 '14 at 22:56
• I understand how to prove the Fibonacci sequence holds, but how do we know this doesn't diverge for large enough $n$, e.g. 1,1,2,3,5,8,13,21,44(it diverged),79,333, etc... – Don Larynx Dec 22 '14 at 22:58

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.

• But $f(3) = 3$, not $5$. – Don Larynx Dec 22 '14 at 22:43
• vcv,vvc,cvc,cvv,vvv – Jorge Fernández Hidalgo Dec 22 '14 at 22:47
• Oops, I was counting the number of impossible strings. – Don Larynx Dec 22 '14 at 22:47
• How do we know that this is a Fibonacci sequence for all $n$? – Don Larynx Dec 22 '14 at 22:54
• well, we proved $f(n)=f(n-1)+f(n-2)$ for all $n$, that's the recurrence ficonaccis follow by definition. – Jorge Fernández Hidalgo Dec 22 '14 at 23:01

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$$