So here's the problem:
A winning configuration in the game of Mini-Tetris is a complete tiling of a 2 x n board using only the three shapes shown in Figure 1. By allowing rotations, there can be more configurations to complete the titling. Figure 2 shows some winning configurations to fill 2 x 3 board. Letting Tn denote the number of different winning configurations on a 2 x n board, the first five values are T1 = 1, T2 = 3, T3 = 7, T4 = 17, and T5 = 39. Express Tn in terms of Tn-1, Tn-2, Tn-3, and Tn-4, and compute T6.
Can someone please solve it and explain to me what's going on at each step? Thank you!
I said Tn = Tn-1 + 2Tn-2 and T6 = 73 but apparently that's wrong.
Let $U_n$ be the number of ways to cover a $2\times n$ board with one corner square missing. Clearly $$U_1=0\ ,\quad U_2=1\ .$$ In the first of your five diagrams, we start the $2\times n$ board with an L-shaped piece at the bottom. The number of ways to complete the covering is then $U_{n-1}$. In the fourth, we start with a two-square piece placed vertically; then the one next to it is forced; then there are $T_{n-2}$ ways to complete the covering of the $2\times n$ board. In fact, the five diagrams show all ways of placing the initial piece. See if you can use arguments similar to those I have given to show that the total number of ways to cover the board is $$T_n=U_{n-1}+U_{n-1}+T_{n-2}+T_{n-2}+T_{n-1}\ ,$$ that is, $$T_n=T_{n-1}+2T_{n-2}+2U_{n-1}\ .\tag{$*$}$$ Starting with a $2\times(n-1)$ board with a bottom corner missing, show similarly that $$U_{n-1}=U_{n-2}+T_{n-3}\ .\tag{$*{*}$}$$ Now from $(*)$ we get $$\eqalign{ 2U_{n-1}&=T_n-T_{n-1}-2T_{n-2}\cr 2U_{n-2}&=T_{n-1}-T_{n-2}-2T_{n-3}\ ;\cr}$$ substitute into $(*{*})$ to eliminate the $U$ terms, and then simplify.