9.9: Exercises

1. Write each of the following recurrence equations as advancement operator equations.

a. \(r_{n+2} = r_{n+1} +2r_n\)

b. \(r_{n+4} = 3r_{n+3} - r_{n+2} + 2r_n\)

c. \(g_{n+3} = 5g_{n+1} - g_n + 3^n\)

d. \(h_n = h_{n-1} - 2h_{n-2} + h_{n-3}\)

e. \(r_n = 4r_{n-1} + r_{n-3} - 3r_{n-5} + (-1)^n\)

f. \(b_n = b_{n-1} + 3b_{n-2} + 2^{n+1} - n^2\)

2. Solve the recurrence equation \(r_{n+2}=r_{n+1}+2r_n\) if \(r_0=1\) and \(r_2=3\) (Yes, we specify a value for \(r_2\) but not for \(r_1\)).

3. Find the general solution of the recurrence equation \(g_{n+2} = 3g_{n+1} - 2g_n\).

4. Solve the recurrence equation \(h_{n+3}=6h_{n+2}−11h_{n+1}+6h_n\) if \(h_0=3\), \(h_1=2\), and \(h_2=4\).

5. Find an explicit formula for the \(n^{th}\) Fibonacci number \(f_n\). (See Subsection 9.1.1.)

6. For each advancement operator equation below, give its general solution.

a. \((A-2)(A+10)f = 0\)

b. \((A^2 - 36)f = 0\)

c. \((A^2 - 2A - 5)f = 0\)

d. \((A^3 - 4A^2 - 20A + 48)f = 0\)

e. \((A^3 + A^2 - 5A + 3)f = 0\)

f. \((A^3 + 3A^2 + 3A + 1)f = 0\)

7. Solve the advancement operator equation \((A^2+3A−10)f=0\) if \(f(0)=2\) and \(f(1)=10\).

8. Give the general solution to each advancement operator equation below.

a. \((A-4)^3(A+1)(A-7)^4(A-1)^2f = 0\)

b. \((A+2)^4(A-3)^2(A-4)(A+7)(A-5)^3g = 0\)

c. \((A-5)^2(A+3)^3(A-1)^3(A^2-1)(A-4)^3h = 0\)

9. For each nonhomogeneous advancement operator equation, find its general solution.

a. \((A-5)(A+2)f = 3^n\)

b. \((A^2 + 3A - 1)g = 2^n + (-1)^n\)

c. \((A-3)^3f = 3n + 1\)

d. \((A^2 + 3A - 1)g = 2n\)

e. \((A-2)(A-4)f = 3n^2 + 9^n\)

f. \((A+2)(A-5)(A-1)f = 5^n\)

g. \((A-3)^2(A+1)g = 2 \cdot 3^n\)

h. \((A-2)(A+3)f = 5n2^n\)

i. \((A-2)^2(A-1)g = 3n^22^n + 2^n\)

j. \((A+1)^2(A-3)f = 3^n +2n^2\)

10. Find and solve a recurrence equation for the number \(g_n\) of ternary strings of length \(n\) that do not contain 102 as a substring.

11. There is a famous puzzle called the Towers of Hanoi that consists of three pegs and \(n\) circular discs, all of different sizes. The discs start on the leftmost peg, with the largest disc on the bottom, the second largest on top of it, and so on, up to the smallest disc on top. The goal is to move the discs so that they are stacked in this same order on the rightmost peg. However, you are allowed to move only one disc at a time, and you are never able to place a larger disc on top of a smaller disc. Let \(t_n\) denote the fewest moves (a move being taking a disc from one peg and placing it onto another) in which you can accomplish the goal. Determine an explicit formula for \(t_n\).

12. A valid database identifier of length \(n\) can be constructed in three ways:

• Starting with \(A\) and followed by any valid identifier of length \(n-1\).
• Starting with one of the two-character strings \(1A, 1B, 1C, 1D, 1E\), or \(1F\) and followed by any valid identifier of length \(n-2\).
• tarting with 0 and followed by any ternary (\(\{0,1,2\}\)) string of length \(n−1\).

Find a recurrence for the number \(g(n)\) of database identifiers of length \(n\) and then solve your recurrence to obtain an explicit formula for \(g(n)\). (You may consider the empty string of length 0 a valid database identifier, making \(g(0)=1\). This will simplify the arithmetic.)

13. Let \(t_n\) be the number of ways to tile a \(2 \times n\) rectangle using \(1 \times 1\) tiles and \(L\)-tiles. An \(L\)-tile is a \(2 \times 2\) tile with the upper-right \(1 \times 1\) square deleted. (An \(L\) tile may be rotated so that the “missing” square appears in any of the four positions.) Find a recursive formula for \(t_n\) along with enough initial conditions to get the recursion started. Use this recursive formula to find a closed formula for \(t_n\).

14. Prove Lemma 9.22 about advancement operator equations with repeated roots.

15. Use generating functions to solve the recurrence equation \(r_n=r_{n−1}+6r_{n−2}\) for \(n \geq 2\) with \(r_0=1\) and \(r_1=3\).

16. Let \(a_0=0, a_1=2\), and \(a_2=5\). Use generating functions to solve the recurrence equation \(a_{n+3}=5a_{n+2}−7a_{n+1}+3a_n+2^n\) for \(n \geq 0\).

17. Let \(b_0=1, b_2=1\), and \(b_3=4\). Use generating functions to solve the recurrence equation \(b_{n+3}=4b_{n+2}−b_{n+1}−6b_n+3^n\) for \(n \geq 0\).

18. Use generating functions to find a closed formula for the Fibonacci numbers \(f_n\).

19. How many rooted, unlabeled, binary, ordered, trees (RUBOTs) with 6 leaves are there? Draw 6 distinct RUBOTs with 6 leaves.

20. In this chapter, we developed a generating function for the Catalan numbers. We first encountered the Catalan numbers in Chapter 2, where we learned they count certain lattice paths. Develop a recurrence for the number ln of lattice paths similar to the recurrence

\(c_n = \displaystyle \sum_{k=0}^n c_kc_{n-k}\) for \(n \geq 2\)

for RUBOTs by thinking of ways to break up a lattice path from (0,0) to \((n,n)\) that does not cross the diagonal \(y=x\) into two smaller lattice paths of this type.