1
$\begingroup$

This is my university homework. I was on it for a day but I couldn't solve the problem. I found a implicitness solution for this problem:

$f(2)=3$

$f(4)=11$

$f(n)=3f(n-2)+2f(n-4)$

I thought that it should be true but when I found an implicitness solution there was difference between implicit and explicit answers. Can anybody please suggest a good strategy for finding implicit answer for this types of questions?

  • 0
    Ah, now I understand. This is a good example of why the question should be self-contained and not rely on the title. Because you hadn't stated the problem in the body of the question, I thought that "this problem" referred to the problem following it, so I concluded that "implicitness solution" must be referring to something else...2012-10-12

2 Answers 2

3

If I understand correctly, you’re trying to find a recurrence (and perhaps also a closed form) for the number of ways to tile a $3\times n$ checkerboard with $2\times 1$ dominoes. Clearly this is possible only when $n$ is even, and I agree that $f(2)=3$ and $f(4)=11$. Now let’s consider $f(2n)$ for some $n>2$. For $a\le k I’ll say that a tiling of $3\times(2n)$ splits at $2k$ if it is formed of a tiling of $3\times(2k)$ followed by a tiling of $3\times(2n-2k)$. Your term $3f(2n-2)$ counts the tilings of $3\times(2n)$ that split at $2n-2$, and your term $2f(2n-4)$ counts those that split at $2n-4$ but not at $2n-2$. However, these are not the only possibilities. Here’s a tiling of $3\times 6$ that doesn’t split:

$\begin{array}{|c|c|} \hline 1&1&2&2&3&3\\ \hline 4&5&5&6&6&7\\ \hline 4&8&8&9&9&7\\ \hline \end{array}$

Squares with the same number are covered by a single domino. This same idea can be extended indefinitely:

$\begin{array}{|c|c|} \hline 1&1&2&2&3&3&4&4&5&5\\ \hline 6&7&7&8&8&9&9&10&10&11\\ \hline 6&12&12&13&13&14&14&15&15&11\\ \hline \end{array}$

In each case the top row of dominoes prevents a split at any odd-numbered position, and the bottom two rows prevent a split at any even-numbered position. Thus, you won’t be able to set up a simple recurrence of the kind that you had in mind.

There is a way to derive a closed form using generating functions; it’s discussed in detail in Graham, Knuth, & Patashnik, Concrete Mathematics, pp. 325-7 and pp. 343-4. With a bit of work it can be turned into a derivation of a recurrence as well, though not a very nice one.

Added: Let $u_n=f(2n)$. Let $v_n$ be the number of tilings of a $3\times(2n+1)$ board that’s missing its lower left corner square; this is clearly also the number of tilings of a $3\times(2n+1)$ board that’s missing its upper left corner square. Every tiling of $3\times(2n)$ with $n>0$ begins in one of three ways:

$\begin{array}{|c|c|} \hline 1&\\ \hline 1&\\ \hline 2&2\\ \hline \end{array}\quad\text{or}\quad \begin{array}{|c|c|} \hline 1&1\\ \hline 2&\\ \hline 2\\ \hline \end{array}\quad\text{or}\quad \begin{array}{|c|c|} \hline 1&1\\ \hline 2&2\\ \hline 3&3\\ \hline \end{array}\;. $

The first must be followed by a tiling of a $3\times(2n-1)$ board that’s missing its lower left square; the second must be followed by a tiling of a $3\times(2n-1)$ board that’s missing its upper left square; and the last must be followed by a tiling of a $3\times(2n-2)$ board. Thus, $u_n=2v_{n-1}+u_{n-1}\;.$

Every tiling of a $3\times(2n+1)$ board that’s missing its lower left square must begin with

$\begin{array}{|c|c|} \hline 1&\;\\ \hline 1&\\ \hline &\\ \hline \end{array}\quad\text{or}\quad \begin{array}{|c|c|} \hline 1&1\\ \hline 2&2\\ \hline &3&3\\ \hline \end{array}\;;\tag{1} $

the first of these will be followed by a tiling of $3\times(2n)$, and the second by a tiling of a $3\times(2n-1)$ board that’s missing its lower left square. Thus, $v_n=u_n+v_{n-1}\;.$ Turning the pictures upside-down shows that this recurrence also holds for $v_n$ considered as the number of tilings of a $3\times(2n+1)$ board with the upper left square missing. Thus, we have the system

$\left\{\begin{align*} u_n&=u_{n-1}+2v_{n-1}\\ v_n&=v_{n-1}+u_n\;. \end{align*}\right.$

Then

$\begin{align*} u_n&=u_{n-1}+2v_{n-1}\\ &=u_{n-1}+2(v_{n-2}+u_{n-1})\\ &=3u_{n-1}+2v_{n-2}\\ &=3u_{n-1}+2(v_{n-3}+u_{n-2})\\ &=3u_{n-1}+2u_{n-2}+2v_{n-3}\\ &\;\vdots\\ &=3u_{n-1}+2(u_{n-2}+u_{n-3}+\ldots+u_1)+2v_0\\ &=2+u_{n-1}+2\sum_{k=1}^{n-1}u_k\;, \end{align*}$

since $v_0=1$ (represented by the first picture in $(1)$). If we set $u_0=1$, this simplifies to $u_n=u_{n-1}+2\sum_{k=0}^{n-1}u_k\;.\tag{2}$ To get anything nicer than this, you really want to use generating functions.

Added2: As Steven Stadnicki pointed out in comments, $(2)$ allows us to get a nice recurrence very easily:

$\begin{align*} u_n-u_{n-1}&=\left(u_{n-1}+2\sum_{k=0}^{n-1}u_k\right)-\left(u_{n-2}+2\sum_{k=0}^{n-2}u_k\right)\\ &=u_{n-1}+2u_{n-1}-u_{n-2}\\ &=3u_{n-1}-u_{n-2}\;, \end{align*}$

so $u_n=4u_{n-1}-u_{n-2}\;.\tag{3}$

From $(3)$ we get the auxiliary equation $x^2-4x+1=0$, with roots $\frac{4\pm\sqrt{12}}2=2\pm\sqrt3\;;$ let $\alpha=2+\sqrt3$ and $\beta=2-\sqrt3$. Then $u_n=A\alpha^n+B\beta^n$ for suitable $A$ and $B$. Setting $n=0$ and $n=1$ yields $1=u_0=A+B$ and $3=u_1=A\alpha+B\beta$, respectively. The solution to this system is $A=\frac{3+\sqrt3}6=\frac1{3-\sqrt3},~B=\frac{3-\sqrt3}6=\frac1{3+\sqrt3}\;,$ so

$u_n=\frac{(2+\sqrt3)^n}{3-\sqrt3}+\frac{(2-\sqrt3)^n}{3+\sqrt3}\;.\tag{4}$

Finally, $\dfrac{(2-\sqrt3)^n}{3+\sqrt3}<\dfrac12$ for $n\ge 0$, so $f(2n)=u_n=\left\lfloor\frac{(2+\sqrt3)^n}{3-\sqrt3}+\frac12\right\rfloor\;,$ the integer nearest $\dfrac{(2+\sqrt3)^n}{3-\sqrt3}$, for all $n\ge 0$.

  • 0
    +1, nice treatment and nice pictures! However you can get the characteristic values more directly without going through the summation, either by eliminating one of $u$ and $v$ in favour of the other or by writing \begin{align*} u_n&=u_{n-1}+2v_{n-1}\\ v_n&=v_{n-1}+u_n \end{align*} as \pmatrix{u_n\\v_n} = \pmatrix{1&2\\1&3} \pmatrix{u_{n-1}\\v_{n-1}} (after substituting the first equation into the second) and finding the eigenvalues of the matrix.2012-10-12
0

If we define $m=\frac {n-2}2$ your recurrence becomes $f(m)=3f(m-1)+2f(m-2), f(0)=3, f(1)=11$. Using the standard technique of assuming a power law solution, the roots are $\frac {3 \pm \sqrt{17}}2$ and the solution is $f(m)=\left(\frac 32 + \frac {11}{\sqrt {17}}\right)\left(\frac {3 + \sqrt{17}}2\right)^m+\left(\frac 32 - \frac {11}{\sqrt {17}}\right)\left(\frac {3 - \sqrt{17}}2\right)^m$