#10 Recursion and Sequences

Let \(a_n\) be the number of ways. Then \(a_0=1\), \(a_1=1\), and \(a_n=a_{n-1}+a_{n-2}\). Thus \(a_2=2\), \(a_3=3\), \(a_4=5\), \(a_5=8\).

Let \(a_n\) be the number of tilings of \(2\times n\). Then \(a_0=1\), \(a_1=1\), \(a_n=a_{n-1}+a_{n-2}\). Thus \(a_2=2\), \(a_3=3\), \(a_4=5\).

Let \(a_n\) be the number of such strings. Then \(a_0=1\), \(a_1=2\), \(a_n=a_{n-1}+a_{n-2}\). Thus \(a_2=3\), \(a_3=5\), \(a_4=8\).

One must make \(2\) right moves and \(3\) up moves. There are \(5\) steps total, so choose positions for the \(2\) right moves: \(\binom{5}{2}=10\).

We get \(a_3=3\), \(a_4=5\), \(a_5=8\), \(a_6=13\).

With \(a_0=1\), \(a_1=1\), \(a_n=a_{n-1}+a_{n-2}\), we get \(1,1,2,3,5,8,13,21,34,55,89\). Hence \(a_{10}=89\).

For domino tilings of \(2\times n\), \(a_n=a_{n-1}+a_{n-2}\). Values: \(a_0=1\), \(a_1=1\), \(a_2=2\), \(a_3=3\), \(a_4=5\), \(a_5=8\), \(a_6=13\), \(a_7=21\), \(a_8=34\).

The recurrence is \(a_n=a_{n-1}+a_{n-2}\). Thus \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\), \(a_7=34\), \(a_8=55\).

There are \(7\) steps total. Choose positions for the \(4\) right moves: \(\binom{7}{4}=35\).

To \((2,1)\): \(\binom{3}{1}=3\). From \((2,1)\) to \((5,4)\): need \(3\) right and \(3\) up moves, so \(\binom{6}{3}=20\). Total: \(3\cdot20=60\).

Let \(a_n\) be the number of tilings. Then \(a_n=a_{n-1}+a_{n-2}\), with \(a_0=1\), \(a_1=1\). We get \(a_9=55\).

Let \(a_n\) be the number of such subsets of \(\{1,\ldots,n\}\). If \(n\) is not included, there are \(a_{n-1}\) ways. If \(n\) is included, then \(n-1\) is not included, leaving \(a_{n-2}\) ways. Hence \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Thus \(a_7=34\).

If a subset does not contain \(n\), it is a valid subset of \(\{1,\ldots,n-1\}\), giving \(a_{n-1}\) choices. If it contains \(n\), then it does not contain \(n-1\), and the remaining part is a valid subset of \(\{1,\ldots,n-2\}\), giving \(a_{n-2}\) choices. The cases are disjoint and exhaustive, so \(a_n=a_{n-1}+a_{n-2}\).

If the upper-right cell is covered by a vertical domino, then the whole last column is covered, leaving \(2\times(n-1)\): \(a_{n-1}\) ways. If it is covered by a horizontal domino, then the lower-right cell must also be covered by a horizontal domino from the previous column, leaving \(2\times(n-2)\): \(a_{n-2}\) ways. There are no other cases and they do not overlap. Hence \(a_n=a_{n-1}+a_{n-2}\).

Let \(a_n\) be the number of strings of length \(n\). A valid string ends in \(1\), \(01\), or \(001\), according to its final block of zeros. Therefore \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). Initial values are \(a_0=1\), \(a_1=2\), \(a_2=4\). Then \(a_3=7\), \(a_4=13\), \(a_5=24\), \(a_6=44\), \(a_7=81\), \(a_8=149\), \(a_9=274\), \(a_{10}=504\).

There are \(\binom{9}{5}=126\) paths in total. Paths through \((2,1)\) number \(\binom{3}{1}\cdot\binom{6}{3}=3\cdot20=60\). Hence \(126-60=66\) paths avoid the point.

Let \(a_n\) be the number of ways. Then \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\), with \(a_0=1\), \(a_1=1\), \(a_2=2\). We get \(a_3=4\), \(a_4=7\), \(a_5=13\), \(a_6=24\), \(a_7=44\), \(a_8=81\), \(a_9=149\).

There are \(3\) choices for the first position. Each next letter must differ from the previous one, so it has \(2\) choices. Total: \(3\cdot2^7=384\).

Let \(a_n\) be the number of ways. Then \(a_n=a_{n-1}+a_{n-3}\), with \(a_0=1\), \(a_1=1\), \(a_2=1\). We get \(a_3=2\), \(a_4=3\), \(a_5=4\), \(a_6=6\), \(a_7=9\), \(a_8=13\), \(a_9=19\), \(a_{10}=28\), \(a_{11}=41\), \(a_{12}=60\).

Let \(a_n\) be the number of tilings. The last tile has length \(1\), \(2\), or \(3\), so \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\). With \(a_0=1\), \(a_1=1\), \(a_2=2\), we get \(a_8=81\).

Let \(a_n\) be the number of tilings of \(2\times n\). The last column may be a vertical domino: \(a_{n-1}\). The last two columns may be two horizontal dominoes or one \(2\times2\) square: \(2a_{n-2}\). Hence \(a_n=a_{n-1}+2a_{n-2}\), \(a_0=1\), \(a_1=1\). Thus \(a_2=3\), \(a_3=5\), \(a_4=11\), \(a_5=21\), \(a_6=43\).

Let \(a_n\) be the number of such strings. As usual, \(a_n=a_{n-1}+a_{n-2}\): the string ends in \(0\) or in \(01\). Initial values are \(a_0=1\), \(a_1=2\). For Fibonacci numbers, \(F_2=1\), \(F_3=2\). Thus \(a_0=F_2\), \(a_1=F_3\), and both sequences satisfy the same recurrence. Therefore \(a_n=F_{n+2}\).

There are \(\binom{8}{4}=70\) paths in total. Bad paths are those that first go above the diagonal after some up-step. Reflect the initial segment up to this step across the line \(y=x+1\); this gives a bijection with paths from \((-1,1)\) to \((4,4)\), requiring \(5\) right moves and \(3\) up moves. There are \(\binom{8}{3}=56\) such paths. Hence the number of good paths is \(70-56=14\).

Let \(A_n\) be the number of full tilings of \(2\times n\), and let \(B_n\) be the number of tilings of a \(2\times n\) board with one right corner cell removed. Then \(B_n=A_{n-2}+B_{n-1}\): the gap can be closed by an L-tromino, leaving a full rectangle of width \(n-2\), or the gap state can be shifted one column. For the full board, \(A_n=A_{n-1}+A_{n-2}+2B_{n-1}\): the last block is a vertical domino, two horizontal dominoes, or two symmetric ways to close the right part using a gap state. Initial values: \(A_0=1\), \(A_1=1\), \(B_0=0\), \(B_1=0\). We get \(B_2=1\), \(A_2=2\); \(B_3=2\), \(A_3=5\); \(B_4=4\), \(A_4=11\); \(B_5=9\), \(A_5=24\); \(B_6=20\), \(A_6=53\). Answer: \(53\).