Building a tower using colorful blocks How many possibilities are there to build a tower of n height, using colorful blocks, where:


*

*white block is of 1 height

*black, red, blue, green, yellow, pink blocks are equal to 2 heights


I need to find the generating function formula for this.
So, for n = 1 I get 1 possibility, 
for n = 2 I get 2 possibilities, 
for n = 3 I get 3 possibilities
for n = 4 I get > 4 possibilities etc.
The generating function at this moment would be $1 + 2x + 3x^{2} + ...$. But I have no idea how can I find the general formula calculating this.
Could you give me any suggestions, or solutions (;-)) ?
 A: It looks to me like for $n=2$ you have $7$ possibilities, either two white or one of any of the $6$ colors.  Similarly for $n=3$ you can have three white, or a white and a color, or a color and a white, for $13$ possibilities.
To make the recurrence, if there are $T(n)$ ways to make a tower $n$ high, we can either put a white block on a tower one shorter or put a colored block (6 ways) on a tower two shorter, so $$T(n)=T(n-1)+6T(n-2), T(1)=1, T(0)=1$$
This can be solved by the usual techniques-find the characteristic polynomial, factor, etc.
Added:  if color doesn't matter but order does, change the $6$ to $1$ above.  If color and order don't matter, the only choice to make is how many $2$ size blocks to use, which can range from $0$ to $\lfloor \frac n2 \rfloor$, for a total of $1+\lfloor \frac n2 \rfloor$ ways.
A: An alternative approach is to note that the generating function for the number towers made out of exactly $k$ blocks of any size can be written as $$(x+6x^2)^k$$ So the total generating function must be:
$$\sum_{k=0}^\infty (x+6x^2)^k$$
which is just a geometric sequence for which a closed form can easily be found.
If you want to ignore the colors of the bigger blocks, then the generating function for exactly $k$ blocks is $$(x+x^2)^k$$ and the total generating function is $$\sum_{k=0}^\infty (x+x^2)^k$$
It turns out in this case the sequence will look familiar.
A: Let the number of towers of height $n$ be $a_n$. To build a tower of height $n$, you start with a tower of height $n - 1$ and add a white block ($a_{n - 1}$ ways) or with a tower of height $n - 2$ and add one of 6 height-2 blocks. In all, you can write:
$$
a_{n + 2} = a_{n + 1} + 6 a_n
$$
Clearly $a_0 = a_1 = 1$.
Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get:
$$
\frac{A(z) - a_0 - a_1 z}{z^2} = \frac{A(z) - a_0}{z} + 6 A(z)
$$
You get:
$$
A(z) = \frac{1}{1 - z - 6 z^2}
     = \frac{3}{5} \cdot \frac{1}{1 - 3 z} + \frac{2}{5} \cdot \frac{1}{1 + 2 z}
$$
This is just geometric series:
$$
a_n = \frac{3}{5} \cdot 3^n + \frac{2}{3} \cdot (-2)^n
    = \frac{3^{n + 1} - (-2)^{n + 1}}{5}
$$
