How many stacks of chips $n$ cm high can be made from white and black chips 1 cm in height and red, green, and blue chips 2 cm in height?

Question

How many stacks of chips $n$ cm high can be made from white and black chips 1 cm in height and red, green, and blue chips 2 cm in height?

If $s_n$ is the number of ways to create a stack of $n$ chips, then I figured that $s_n = 2s_{n-1} + 3s_{n-2}$. If the nth chip is white or black, then there are $s_{n-1}$ ways to build the stack of $n-1$ chips before the nth chip, and if the nth chip is red, green, or blue, then there are $s_{n-2}$ ways to build the stack of $n-2$ chips before the nth chip. However, with $s_0 = 0, s_1 = 2$, the numbers aren't working out. Is there something wrong with my recurrence or initial conditions?

Thanks!

Answer 1

You are almost correct. Note that in your question, you are to find a stack of chips of $n~$cm high, rather than a stack of $n$ chips. Your recurrence is correct, but the explanation should go as follows: Let $s_n$ be the # of ways to create a stack of chips of $n$cm high. If the top chip is of white or black, then it is $1~$cm high and there are $s_{n-1}$ ways to build a stack of $(n-1)~$cm high; if the top chip is of red, green or blue, then it is $2~$cm high and there are $s_{n-2}$ ways to build a stack of $(n-2)~$cm high.

For the initial condition, $s_0$ should be $1$ since a stack containing no chip is also a way.

Answer 2

Hint: For $s_2$, you need to consider the possible ways to construct a 2 cm stack without using any 1 cm chips.