2

I am having a hard time trying to prove the following recurrence relation $$f(n)=f(n-1)+2f(n-2),\quad n\geq 2, \quad f(1)=1 \quad \& \quad f(2)=3.$$

$f(n)$ is the number of ways to tile a $(2\times n)$-rectangle with tiles of the form $2 \times 1$, $1 \times 2$, or $2\times 2$.

I attempt this by induction but I am confused in the base case since I get $f(2)=f(1)+2f(0)$ but we do not know $f(0)$.

Can someone help?

Alexis Sandoval
  • 376
  • Plug in $f(2) = 3$ and $f(1) = 1$ in your equation $f(2) = f(1) + 2f(0)$ and you will get $f(0)$. – WhatsUp Mar 25 '21 at 21:44
  • It's possible to use the generating function to solve these recurrences. Assuming that is what is being asked... – Dole Mar 25 '21 at 21:46
  • @Dole Is not asking for a specific method. – Alexis Sandoval Mar 25 '21 at 21:48
  • Since $f(n)$ is the number of way to tile a $2 \times$ rectangle, you have to see how to express this in terms of tilings of the $2\times(n-1)$ and $2\times (n-2)$ rectangle. Here the trick is to look to the rightmost tile and to make a case per possibility: it can be either a $2\times2$ domino or ... Also it is not a problem that $f(0)$ is not given here, since you are mostly interested in $n\geq 2$ – thibo Mar 25 '21 at 21:49
  • this question https://math.stackexchange.com/questions/2080310/find-a-recurrence-relation-for-the-number-of-ways-to-arrange-n-dominoes-to-fil/2080316#2080316 and other references to Fibonacci relation and tiling by domino should be a good source of inspiration. Once you've understood this problem yours will follow easily. See https://link.springer.com/article/10.1007/s10948-013-2398-7/figures/2 for an visual help – thibo Mar 25 '21 at 21:55

1 Answers1

1

Hint

Suppose you start by using the tile $2\times 1$. So, you get exactly the same problem but facing a $(2\times (n-1))-$rectangle. So, you get $f(n-1)$ ways of to tile a $(2\times (n-1))-$rectangle.

However if first use $2\times 1$ tile, you find yourself forced to use another $2\times 1$ tile in the upper part. So, you get exactly the same problem but facing a $(2\times (n-2))-$rectangle. So, you get $f(n-2)$ ways of to tile a $(2\times (n-2))-$rectangle.

Can you understand what happens if you first use the $2\times 2$ tile?

Arnaldo
  • 21,342