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.

  • $\begingroup$ $2^5$ possible combinations for $n = 5$? $\endgroup$ – Don Larynx Dec 22 '14 at 22:45
  • 2
    $\begingroup$ 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. $\endgroup$ – ml0105 Dec 22 '14 at 22:46
  • $\begingroup$ How do we know that this is a Fibonacci sequence for all $n$? $\endgroup$ – Don Larynx Dec 22 '14 at 22:53
  • $\begingroup$ 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)$. $\endgroup$ – ml0105 Dec 22 '14 at 22:56
  • $\begingroup$ 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... $\endgroup$ – 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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.