Combinatorial Proof for a Recursive Sequence For $n>3$ let $g_n = g_{n-1} + g_{n-3}$ where the recursion takes the value 1 for n = 0,1,2.
Prove that $g_{2n} = (g_n)^2 + 2g_{n-2}g_{n-1}$ combinatorially, $n > 1$.  
For the time being I am looking for a hint on how to get started with this kind of question.  My idea is that structurally we should find a combinatorial interpretation for the first recurrence and then extend that to the identity below.  The first few terms along with initial conditions suggest a 'cluster' effect in so far as a larger index of the previous terms results in a greater increase with each step.  
This is similar to the interpretation for Fibonacci numbers that describe tiling an n-board.  One site describing this interpretation is 
http://www.cut-the-knot.org/arithmetic/combinatorics/FibonacciTilings.shtml
Does anyone have any ideas on how to think about these problems?

Consider an $1 \times n$ board, which we want to tile with pieces of size $1 \times 1$ and $1 \times 3$. We can use any type as often as we want, but we have to tile the complete board with no overlapping pieces.
Now, to tile an $1 \times n$ board, we can either put a piece of size $1 \times 1$ at the left end (leaving us with a $1 \times (n-1)$ board), or put a large piece of size $1 \times 3$ at the far left end (leaving a $1 \times (n-3)$ board to be tiled). So if $g_n$ counts the number of ways to tile a $1 \times n$ board with these pieces, then the above recursion gives us 
$$g_n = g_{n-1} + g_{n-3}.$$
Note that the "base cases" $g_0 = 1$, $g_1 = 1$ and $g_2 = 1$ are also satisfied.
To get to the recursion you want, consider a $1 \times (2n)$ board, and see this as two boards of size $1 \times n$, glued together on the short ends. To tile the complete board, we have two options: (i) tile each board separately, or (ii) tile the board in a way that uses the fact that the boards are glued together. 
(i) If we just tile each board separately, then there are $g_n$ ways to tile each board. So in this case, there are $g_n^2$ ways to tile both boards.
(ii) If we do not tile each board separately, then we have to put a $1 \times 3$ piece across the middle, e.g., with one block on the left half of the $1 \times (2n)$ board, and two blocks on the right half. This leaves a $1 \times (n-1)$ board on the left side, and a $1 \times (n-2)$ board on the right side to be filled with other pieces. So there are $g_{n-1} \cdot g_{n-2}$ ways to tile the rest of the board. Since we can also let a piece cover two squares of the left half of the board and one square of the right half of the board, we get an extra factor $2$.
Combining (i) and (ii), we therefore get the final result $$g_{2n} = g_n^2 + 2 g_{n-1} g_{n-2}.$$

A generalization of this idea shows that e.g. a Fibonacci-like recursion 
$$f_n = f_{n-1} + f_{n-2}, \quad (f_0 = f_1 = 1)$$ 
satisfies 
$$f_{2n} = f_n^2 + f_{n-1}^2,$$ 
by applying the same argument to tiles of sizes $1 \times 1$ and $1 \times 2$. Except for the starting values, this is exactly the Fibonacci sequence. More precisely, $f_n = F_{n+1}$, where $F_n$ is the normal Fibonacci sequence starting at $f_0 = 0$, and the above identity then translates to 
$$F_{2n+1} = F_{n+1}^2 + F_n^2.$$
With pieces of size $1 \times 1$ and $1 \times 4$, the same reasoning leads to a sequence 
$$h_n = h_{n-1} + h_{n-4}, \qquad (h_0 = h_1 = h_2 = h_3 = 1)$$ 
satisfying 
$$h_{2n} = h_n^2 + h_{n-2}^2 + 2 h_{n-1} h_{n-3}.$$
With pieces of size $1 \times 1$, $1 \times 2$ and $1 \times 3$ we can extend the argument even further, and show that the sequence satisfying 
$$k_n = k_{n-1} + k_{n-2} + k_{n-3}, \qquad (k_0 = k_1 = 1, \ k_2 = 2)$$ 
also satisfies the recurrence relation 
$$k_{2n} = k_n^2 + k_{n-1}^2 + 2 k_{n-1} k_{n-2}.$$
