4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I suppose it would be an interesting exercise to start with the combinatorial interpretation of the Fibonacci sequence (either using a board of height $2$ or of height $1$), and see how many of the known identities on Fibonacci identities can be proved combinatorially... $\endgroup$ – TMM Apr 23 '13 at 20:15
4
+50
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It sounds like it's time for me to take a visit to OEIS. Thanks for your response! $\endgroup$ – user73041 Apr 19 '13 at 22:03
  • $\begingroup$ Could we also consider the tromino as covering three squares on a rectangle of size 3n rather than dealing with two dimensions? $\endgroup$ – user73041 Apr 19 '13 at 22:11
2
$\begingroup$

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 ... :-)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I would like to be able to accept both of your answers, as they are very insightful, but TMM used 1 x n boards as (perhaps not so clearly) requested. That said, the cases certainly appear to be interchangeable. $\endgroup$ – user73041 Apr 23 '13 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.