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
    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?2012-10-12
  • 0
    i used implicit for terms like that i wrote in my post and explicit for a single term for example a0(k0)^n2012-10-12
  • 0
    It sounds like what you mean by implicit is what's traditionally called a 'recurrence relation'.2012-10-12
  • 0
    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.2012-10-12
  • 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 ksplits 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
    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?)2012-10-12
  • 0
    @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.2012-10-12
  • 0
    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...2012-10-12
  • 0
    @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!2012-10-12
  • 0
    thanks Brian for your complete and step by step solution.i learned it good.also i will plan to read the materials that you suggested2012-10-12
  • 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$