# implicit equation for covering a $3\times{n}$ face with $2\times{1}$ mosaics with recursion solution?

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?

-
I don't understand how you're using the terms "implicit solution" and "explicit solution". I would have thought that the recursion relation is an implicit defnition of the function $f$, and the closed form derivable from it is an explicit definition. But by "implicit solution" you seem to be referring to a third form? What kind of form is this? – joriki Oct 12 '12 at 16:49
i used implicit for terms like that i wrote in my post and explicit for a single term for example a0(k0)^n – CoderInNetwork Oct 12 '12 at 16:55
It sounds like what you mean by implicit is what's traditionally called a 'recurrence relation'. – Steven Stadnicki Oct 12 '12 at 17:04
There's an extensive and detailed solution of this exact problem in the "Generating Functions" chapter of Concrete Mathematics by Graham, Knuth, and Patashnik, around page 343. – MJD Oct 12 '12 at 17:09
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... – joriki Oct 12 '12 at 21:21

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

-
Out of curiosity (somehow I've managed to never read Concrete Mathematics!), does the generating function approach work via intertwined recurrence relations among generating functions for each of the 'partial' cases? (e.g., '$t_{0,1,0}(n) =$ number of 3xn tilings with a single non-domino cell at (n, 2)', '$t_{0,1,1}(n) =$ number of 3xn tilings with two non-domino cells at (n,2) and (n,3)', etc?) – Steven Stadnicki Oct 12 '12 at 18:08
@Steven: It does indeed. In fact, I’m about to add the derivation of the recurrences needed to get the generating function(s) nicely, and you’ll see. – Brian M. Scott Oct 12 '12 at 18:12
Perfect, thank you! Incidentally, from the last expression there's a pretty straightforward derivation of a more explicit recurrence: $u_n-u_{n-1} = (u_{n-1}+2\sum_{k=0}^{n-1}u_k)-(u_{n-2}+2\sum_{k=0}^{n-2}u_k) = u_{n-1}-u_{n-2}+2u_{n-1}$ since the sums almost completely cancel, so $u_n = 4u_{n-1}-u_{n-2}$ and the usual characteristic methods should apply... – Steven Stadnicki Oct 12 '12 at 18:31
@Steven: You’re right; I’m so used to the other approach these days that I completely missed that. The answer’s getting a bit long, but that’s so easy that I’ll go ahead and finish it off. Thanks! – Brian M. Scott Oct 12 '12 at 18:35
thanks Brian for your complete and step by step solution.i learned it good.also i will plan to read the materials that you suggested – CoderInNetwork Oct 12 '12 at 20:13

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$

-