I want to pave a $2\times n$ rectangle with $1\times 2$ blocks which come in two colours, white and grey. Let $w_n$ be the number of different ways this can be done.
I determined the recursive equation: $w_n = 2w_{n-1} + 4w_{n-2}$
But I'm having difficulties solving the recursive equation.
I've gathered that the roots of the equation are $(2±\sqrt{ 20})/2$ which I've equated to $(\phi + 1)$ and $(1 - \phi \text{ or } 2\sigma)$ (golden ratio related symbols) respectively (I may be wrong at this point). and I've tried to solve for $w_n$ using a linear approach. My final equation is: $$ w_n = \sigma^2 (\phi+1)^n + \sigma(1-\phi)^n $$ however it doesn't work.
Let $u_n$ be the number of ways to pave a board of $2\times n$ using blocks of size $2\times n$ which come in one color. Clearly $u_1=1$ and $u_2=2$. From here on we prove $u_{n+2}=u_n+u_{n+1}$. To prove this look at the right edge of the board. You can fill the two squares on that edge in two ways. If you fill with a vertical block you can fill the other squares in $u_{n+1}$ ways, if you fill with two horizontal blocks you can fill the other squares in $u_{n}$ ways. Obtaining the recursion.
This tells us $u_n$ is fibonacci.
We can now modify this to accept blocks of various colors. You can first place the blocks in $u_n$ ways, since there are $n$ blocks we can color them in $2^n$ ways. Telling us $w_n=2^n u_n$. The formula for the fibonaccis is well know.