maths.free › Combinatorics & Graph Theory › 9. Recurrence Equations › Recurrence Equations: exercises

Recurrence Equations: exercises

Recurrence Equations: exercises — from Keller & Trotter, Applied Combinatorics.

Practice (23)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

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

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

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

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

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

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

    6. \(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^\text{th}\) Fibonacci number \(f_n\). (See .)

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

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

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

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

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

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

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

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

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

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

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

    3. \((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.

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

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

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

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

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

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

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

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

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

    10. \((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\).

    • Starting 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 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 , where we learned they count certain lattice paths. Develop a recurrence for the number \(l_n\) of lattice paths similar to the recurrence \[\begin{aligned}\end{aligned}\] 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.

  21. Which of the following recurrence equations are linear?

  22. Which of the following recurrence equations are homogeneous?

  23. Which of the following funtions satisfy the advancement operator equation \((A-3)f=0\)?

Symbols used here

\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Jaribu kufanya mambo yako mwenyewe

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mengi zaidi katika Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs