Combinatorial Proof for a Recursive Sequence

Question

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?

Answer 1

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}.$$

Answer 2

The OEIS calls $(g_n)$ Narayana's cows sequence. This sequence is known to count the number of tilings of a $3 \times n$ rectangle by straight trominoes.

The first recurrence follows by considering the orientation of a straight tromino which covers the upper left corner of a rectangle of height $3$ and width $n$. If it is oriented vertically, the number of tilings is given by $g_{n-1}$. (Simply tile the remaining $3 \times (n-1)$ rectangle with straight trominoes). If it is oriented horizontally, then the two straight trominoes below it must be aligned horizontally, and we have a $3 \times (n-3)$ rectangle left. Thus $g_n = g_{n-1} + g_{n-3}$ for $n \geq 3$.

For the identity $g_{2n} = (g_n)^2 + 2g_{n-1}g_{n-2}$, I believe this has to do with whether a horizontal tromino crosses the vertical axis of symmetry of the rectangle.

Answer 3

Elaborating on @Daniel's excellent answer, consider the vertical line bisecting the $3\times(2n)$ rectangle. If this line does not pass through the interior of any tromino, then we have $g_n$ tilings of the left side, and $g_n$ tilings of the right side, yielding $g_n^2$. If this line does pass through the interior of a tromino, there must be a $3\times 3$ block of horizontal trominos that this line passes through. If the line splits the $3\times 3$ block with with $1\times 3$ on the left and $2\times 3$ on the right, to the left of the block we tile in $g_{n-1}$ ways; to the right of the block we tile in $g_{n-2}$ ways. If instead the line splits the $3\times 3$ block the other way, with the small piece on the right, we have $g_{n-2}$ ways to tile the part to the left of the $3\times 3$ block, and $g_{n-2}$ ways to tile to the right. Combining, we get $g_{2n}=g_n^2+g_{n-1}g_{n-2}+g_{n-2}g_{n-1}=g_n^2+2g_{n-1}g_{n-2}$.

If instead we used dominos and a $2\times n$ board, we would get the recurrence $g_n=g_{n-1}+g_{n-2}$. The vertical line has only one place it can split the middle $2\times 2$ block, so the variant identity will be $g_{2n}=g_n^2+g_{n-1}^2$.

If instead we used quadrominoes (?) i.e. $1\times 4$ tiles on a $4\times n$ board, we would get the recurrence $g_n=g_{n-1}+g_{n-4}$. The vertical line now has three places it can split the $4\times 4$ block, so the identity will be $g_{2n}=g_n^2+g_{n-1}g_{n-3}+g_{n-2}g_{n-2}+g_{n-3}g_{n-1}=g_n^2+g_{n-2}^2+2g_{n-1}g_{n-3}$.

Generalizing a different way, there is no need for the vertical line to be in the middle. Back to the original tromino problem. If we have a $3\times(3n)$ board, and place a line after $n$ squares. If this is between two blocks, then we have $g_{n}g_{2n}$. If it's not, we have either $g_{n-1}g_{2n-2}$ or $g_{n-2}g_{2n-1}$. Combining, we get $g_{3n}=g_ng_{2n}+g_{n-1}g_{2n-2}+g_{n-2}g_{2n-1}$. One could do this all day ... :-)