Solving Elementary Recurrence Relations

Cheatsheet Content

0. Initial Values and General Solutions When solving recurrence relations, you first find the general solution which contains arbitrary constants (e.g., $A, B, C_1, C_2$). These constants arise from the order of the recurrence (e.g., a second-order recurrence will have two constants). The initial values (e.g., $a_0, a_1$) are then used at the very end of the process to determine the specific values of these constants. They "pin down" the particular sequence that satisfies both the recurrence relation and the given starting conditions. Therefore, when finding the general form of $a_n^{(h)}$ or $a_n^{(p)}$, you typically don't consider the initial values until the final step of solving for the arbitrary constants in the complete solution $a_n = a_n^{(h)} + a_n^{(p)}$. 1. Homogeneous Recurrence Relations Form: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$ These are linear homogeneous recurrence relations with constant coefficients. We look for solutions of the form $a_n = r^n$ for some constant $r$. This is analogous to finding eigenfunctions in linear algebra, where $r^n$ acts as an "eigenvector" under the recurrence operator. Substitute $a_n = r^n$ into the recurrence: $r^n = c_1 r^{n-1} + c_2 r^{n-2} + \dots + c_k r^{n-k}$ Divide by $r^{n-k}$ (assuming $r \ne 0$): $r^k = c_1 r^{k-1} + c_2 r^{k-2} + \dots + c_k$ Rearranging gives the Characteristic Equation: $r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0$ The roots of this polynomial determine the form of the homogeneous solution $a_n^{(h)}$. 1.1 Distinct Roots If $r_1, r_2, \dots, r_k$ are distinct roots of the characteristic equation, then $r_1^n, r_2^n, \dots, r_k^n$ are $k$ linearly independent solutions. The general homogeneous solution is a linear combination of these solutions: $a_n^{(h)} = A_1 r_1^n + A_2 r_2^n + \dots + A_k r_k^n$ Constants $A_i$ are found using initial conditions. 1.2 Repeated Roots If $r_1$ is a root with multiplicity $m$ (i.e., $(r-r_1)^m$ is a factor of the characteristic equation), then $r_1^n, n r_1^n, n^2 r_1^n, \dots, n^{m-1} r_1^n$ are $m$ linearly independent solutions. Its contribution to the solution is: $(A_1 + A_2 n + A_3 n^2 + \dots + A_m n^{m-1}) r_1^n$ 1.3 Example: Fibonacci Numbers $F_n = F_{n-1} + F_{n-2}$ with $F_0=0, F_1=1$. 1. Characteristic Equation: Assume $F_n = r^n$. Substituting gives $r^n = r^{n-1} + r^{n-2}$. Divide by $r^{n-2}$: $r^2 = r + 1$. $r^2 - r - 1 = 0$. 2. Find roots: Using the quadratic formula $r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$: $r_{1,2} = \frac{-(-1) \pm \sqrt{(-1)^2 - 4(1)(-1)}}{2(1)} = \frac{1 \pm \sqrt{1+4}}{2} = \frac{1 \pm \sqrt{5}}{2}$ Let $\phi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2}$. These are distinct roots. 3. General solution: $F_n = A_1 \phi^n + A_2 \psi^n$ 4. Use initial conditions $F_0=0, F_1=1$ to find $A_1, A_2$: For $n=0$: $F_0 = A_1 \phi^0 + A_2 \psi^0 \implies 0 = A_1 \cdot 1 + A_2 \cdot 1 \implies A_1 + A_2 = 0 \implies A_2 = -A_1$. For $n=1$: $F_1 = A_1 \phi^1 + A_2 \psi^1 \implies 1 = A_1 \phi + A_2 \psi$. Substitute $A_2 = -A_1$ into the second equation: $1 = A_1 \phi - A_1 \psi \implies 1 = A_1 (\phi - \psi)$. Calculate $\phi - \psi = \left(\frac{1+\sqrt{5}}{2}\right) - \left(\frac{1-\sqrt{5}}{2}\right) = \frac{1+\sqrt{5}-1+\sqrt{5}}{2} = \frac{2\sqrt{5}}{2} = \sqrt{5}$. So, $1 = A_1 \sqrt{5} \implies A_1 = \frac{1}{\sqrt{5}}$. And $A_2 = -A_1 = -\frac{1}{\sqrt{5}}$. 5. Final solution (Binet's Formula): $F_n = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n$ $F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$ 2. Nonhomogeneous Recurrence Relations Form: $a_n = c_1 a_{n-1} + \dots + c_k a_{n-k} + f(n)$ General Solution: $a_n = a_n^{(h)} + a_n^{(p)}$ $a_n^{(h)}$: Homogeneous solution (from section 1). $a_n^{(p)}$: Particular solution (depends on $f(n)$). 2.1 Guessing the Particular Solution $a_n^{(p)}$ Match the form of $f(n)$ with some adjustments. $f(n)$ Initial Guess for $a_n^{(p)}$ $P(n)$ (polynomial of degree $d$) $D_d n^d + \dots + D_1 n + D_0$ $c^n$ (constant $c$) $D c^n$ $P(n) c^n$ $(D_d n^d + \dots + D_0) c^n$ Modification Rule: If any term in the initial guess for $a_n^{(p)}$ is a solution to the homogeneous equation $a_n^{(h)}$, then multiply the entire guess by $n^s$, where $s$ is the smallest non-negative integer such that no term in the modified guess $n^s a_n^{(p)}$ is a solution to the homogeneous equation. Equivalently, $s$ is the multiplicity of the "base" of $f(n)$ as a root of the characteristic equation. If $f(n)$ is a polynomial $P(n)$, its "base" is $1^n$. If $r=1$ is a root of the characteristic equation with multiplicity $s$, multiply $P(n)$ by $n^s$. If $f(n)$ is $c^n$, its "base" is $c$. If $r=c$ is a root of the characteristic equation with multiplicity $s$, multiply $c^n$ by $n^s$. If $f(n)$ is $P(n)c^n$, its "base" is $c$. If $r=c$ is a root of the characteristic equation with multiplicity $s$, multiply $P(n)c^n$ by $n^s$. 2.2 Example 1: $a_n = 2a_{n-1} + n$, with $a_0=1$ 1. Homogeneous solution ($a_n^{(h)}$): Characteristic equation: $r - 2 = 0 \implies r=2$. $a_n^{(h)} = A \cdot 2^n$. 2. Particular solution ($a_n^{(p)}$): $f(n)=n$ (polynomial of degree 1). Initial guess: $a_n^{(p)} = D_1 n + D_0$. The "base" of $f(n)=n$ is $1^n$. Since $r=1$ is NOT a root of the characteristic equation ($r=2$), $s=0$. No modification needed. Substitute $a_n^{(p)}$ into the nonhomogeneous recurrence: $D_1 n + D_0 = 2(D_1 (n-1) + D_0) + n$ $D_1 n + D_0 = 2D_1 n - 2D_1 + 2D_0 + n$ $D_1 n + D_0 = (2D_1+1)n + (2D_0 - 2D_1)$ Equating coefficients: For $n$: $D_1 = 2D_1 + 1 \implies -D_1 = 1 \implies D_1 = -1$ For constant: $D_0 = 2D_0 - 2D_1 \implies -D_0 = -2D_1 \implies D_0 = 2D_1 = 2(-1) = -2$ So, $a_n^{(p)} = -n - 2$. 3. General solution: $a_n = a_n^{(h)} + a_n^{(p)} = A \cdot 2^n - n - 2$. 4. Use initial condition $a_0=1$ to find $A$: $1 = A \cdot 2^0 - 0 - 2 \implies 1 = A - 2 \implies A = 3$. 5. Final solution: $a_n = 3 \cdot 2^n - n - 2$. 2.3 Example 2: $a_n = a_{n-1} + n$, with $a_0=0$ 1. Homogeneous solution ($a_n^{(h)}$): Characteristic equation: $r - 1 = 0 \implies r=1$. $a_n^{(h)} = A \cdot 1^n = A$. 2. Particular solution ($a_n^{(p)}$): $f(n)=n$ (polynomial of degree 1). Initial guess: $a_n^{(p)} = D_1 n + D_0$. The "base" of $f(n)=n$ is $1^n$. Since $r=1$ IS a root of the characteristic equation ($r-1=0$) with multiplicity $s=1$. We must multiply the initial guess by $n^1$. Modified guess: $a_n^{(p)} = n(D_1 n + D_0) = D_1 n^2 + D_0 n$. Substitute $a_n^{(p)}$ into the nonhomogeneous recurrence: $D_1 n^2 + D_0 n = (D_1 (n-1)^2 + D_0 (n-1)) + n$ $D_1 n^2 + D_0 n = D_1 (n^2 - 2n + 1) + D_0 n - D_0 + n$ $D_1 n^2 + D_0 n = D_1 n^2 - 2D_1 n + D_1 + D_0 n - D_0 + n$ $D_1 n^2 + D_0 n = D_1 n^2 + (-2D_1 + D_0 + 1)n + (D_1 - D_0)$ Equating coefficients: For $n^2$: $D_1 = D_1$ (consistent) For $n$: $D_0 = -2D_1 + D_0 + 1 \implies 0 = -2D_1 + 1 \implies 2D_1 = 1 \implies D_1 = 1/2$ For constant: $0 = D_1 - D_0 \implies D_0 = D_1 = 1/2$ So, $a_n^{(p)} = \frac{1}{2} n^2 + \frac{1}{2} n = \frac{n(n+1)}{2}$. 3. General solution: $a_n = a_n^{(h)} + a_n^{(p)} = A + \frac{n(n+1)}{2}$. 4. Use initial condition $a_0=0$ to find $A$: $0 = A + \frac{0(0+1)}{2} \implies 0 = A + 0 \implies A=0$. 5. Final solution: $a_n = \frac{n(n+1)}{2}$. 2.4 Example 3: $a_n = 2a_{n-1} - a_{n-2} + 2^n$ 1. Homogeneous solution ($a_n^{(h)}$): Characteristic equation: $r^2 - 2r + 1 = 0 \implies (r-1)^2 = 0$. Root $r=1$ with multiplicity $s=2$. $a_n^{(h)} = (A_1 + A_2 n) \cdot 1^n = A_1 + A_2 n$. 2. Particular solution ($a_n^{(p)}$): $f(n)=2^n$. Initial guess: $a_n^{(p)} = D \cdot 2^n$. The "base" of $f(n)=2^n$ is $2$. Since $r=2$ is NOT a root of the characteristic equation ($r=1$), $s=0$. No modification needed. Substitute $a_n^{(p)}$ into the nonhomogeneous recurrence: $D \cdot 2^n = 2(D \cdot 2^{n-1}) - (D \cdot 2^{n-2}) + 2^n$ $D \cdot 2^n = D \cdot 2^n - D \cdot 2^{n-2} + 2^n$ Subtract $D \cdot 2^n$ from both sides: $0 = -D \cdot 2^{n-2} + 2^n$ $D \cdot 2^{n-2} = 2^n$ Divide by $2^{n-2}$: $D = \frac{2^n}{2^{n-2}} = 2^{n - (n-2)} = 2^2 = 4$. So, $a_n^{(p)} = 4 \cdot 2^n = 2^{n+2}$. 3. General solution: $a_n = a_n^{(h)} + a_n^{(p)} = A_1 + A_2 n + 2^{n+2}$. (Initial values would be needed to find $A_1, A_2$). 2.5 Example 4: Sum of Squares $S_n = \sum_{i=1}^n i^2$ The recurrence relation is $S_n = S_{n-1} + n^2$, with $S_0 = 0$. 1. Homogeneous solution ($S_n^{(h)}$): Characteristic equation: $r - 1 = 0 \implies r=1$. $S_n^{(h)} = A \cdot 1^n = A$. 2. Particular solution ($S_n^{(p)}$): $f(n)=n^2$ (polynomial of degree 2). Initial guess $S_n^{(p)} = D_2 n^2 + D_1 n + D_0$. The "base" of $f(n)=n^2$ is $1^n$. Since $r=1$ IS a root of the characteristic equation ($r-1=0$) with multiplicity $s=1$. We must multiply the initial guess by $n^1$. Modified guess: $S_n^{(p)} = n(D_2 n^2 + D_1 n + D_0) = D_2 n^3 + D_1 n^2 + D_0 n$. Substitute $S_n^{(p)}$ into the nonhomogeneous recurrence: $D_2 n^3 + D_1 n^2 + D_0 n = [D_2 (n-1)^3 + D_1 (n-1)^2 + D_0 (n-1)] + n^2$ Expand $(n-1)^3 = n^3 - 3n^2 + 3n - 1$ and $(n-1)^2 = n^2 - 2n + 1$: $D_2 n^3 + D_1 n^2 + D_0 n = D_2 (n^3 - 3n^2 + 3n - 1) + D_1 (n^2 - 2n + 1) + D_0 (n - 1) + n^2$ $D_2 n^3 + D_1 n^2 + D_0 n = D_2 n^3 - 3D_2 n^2 + 3D_2 n - D_2 + D_1 n^2 - 2D_1 n + D_1 + D_0 n - D_0 + n^2$ Group terms by powers of $n$: $D_2 n^3 + D_1 n^2 + D_0 n = D_2 n^3 + (-3D_2 + D_1 + 1)n^2 + (3D_2 - 2D_1 + D_0)n + (-D_2 + D_1 - D_0)$ Equating coefficients: For $n^3$: $D_2 = D_2$ (consistent) For $n^2$: $D_1 = -3D_2 + D_1 + 1 \implies 0 = -3D_2 + 1 \implies 3D_2 = 1 \implies D_2 = 1/3$ For $n$: $D_0 = 3D_2 - 2D_1 + D_0 \implies 0 = 3D_2 - 2D_1$. Substitute $D_2=1/3$: $0 = 3(1/3) - 2D_1 \implies 0 = 1 - 2D_1 \implies 2D_1 = 1 \implies D_1 = 1/2$ For constant: $0 = -D_2 + D_1 - D_0$. Substitute $D_2=1/3, D_1=1/2$: $0 = -1/3 + 1/2 - D_0 \implies D_0 = -1/3 + 1/2 = -2/6 + 3/6 = 1/6$ So, $S_n^{(p)} = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n$. Factor out $\frac{n}{6}$: $S_n^{(p)} = \frac{n}{6} (2n^2 + 3n + 1) = \frac{n}{6} (n+1)(2n+1)$. 3. General solution: $S_n = S_n^{(h)} + S_n^{(p)} = A + \frac{n(n+1)(2n+1)}{6}$. 4. Use initial condition $S_0=0$: $0 = A + \frac{0(0+1)(2(0)+1)}{6} \implies 0 = A + 0 \implies A=0$. 5. Final solution: $S_n = \frac{n(n+1)(2n+1)}{6}$. 3. Using Generating Functions Let $G(x) = \sum_{n=0}^\infty a_n x^n$ be the generating function for the sequence $\{a_n\}$. Steps: Multiply the recurrence relation by $x^n$ and sum over $n$ (from appropriate starting index). Substitute $G(x)$ and its shifted forms (e.g., $\sum a_{n-k} x^n = x^k G(x)$ adjusted for initial terms). Solve for $G(x)$. Use partial fraction decomposition if $G(x)$ is rational. Expand $G(x)$ into a power series using known series to find $a_n$. 3.1 Common Series Expansions $\frac{1}{1-cx} = \sum_{n=0}^\infty c^n x^n$ $\frac{1}{(1-cx)^k} = \sum_{n=0}^\infty \binom{n+k-1}{k-1} c^n x^n$ 3.2 Example: $a_n = 3a_{n-1} + 2$, with $a_0=1$ 1. Multiply by $x^n$ and sum from $n=1$ to $\infty$: $\sum_{n=1}^\infty a_n x^n = 3 \sum_{n=1}^\infty a_{n-1} x^n + 2 \sum_{n=1}^\infty x^n$ 2. Recognize sums in terms of $G(x)$ and known series: $\sum_{n=1}^\infty a_n x^n = (a_0 x^0 + a_1 x^1 + \dots) - a_0 = G(x) - a_0 = G(x) - 1$ $3 \sum_{n=1}^\infty a_{n-1} x^n = 3x \sum_{n=1}^\infty a_{n-1} x^{n-1} = 3x \sum_{m=0}^\infty a_m x^m = 3x G(x)$ (by letting $m=n-1$) $2 \sum_{n=1}^\infty x^n = 2 (x + x^2 + x^3 + \dots) = 2 \left(\frac{x}{1-x}\right)$ (geometric series starting from $x^1$) Substitute these into the equation: $G(x) - 1 = 3x G(x) + \frac{2x}{1-x}$ 3. Rearrange to solve for $G(x)$: $G(x) - 3x G(x) = 1 + \frac{2x}{1-x}$ $G(x) (1-3x) = \frac{1-x}{1-x} + \frac{2x}{1-x} = \frac{1-x+2x}{1-x} = \frac{1+x}{1-x}$ $G(x) = \frac{1+x}{(1-x)(1-3x)}$ 4. Use partial fraction decomposition: Let $\frac{1+x}{(1-x)(1-3x)} = \frac{A}{1-x} + \frac{B}{1-3x}$. Multiply by $(1-x)(1-3x)$: $1+x = A(1-3x) + B(1-x)$. To find $A$, set $x=1$: $1+1 = A(1-3) + B(1-1) \implies 2 = -2A \implies A = -1$. To find $B$, set $x=1/3$: $1+1/3 = A(1-1) + B(1-1/3) \implies 4/3 = B(2/3) \implies B = 2$. So, $G(x) = \frac{-1}{1-x} + \frac{2}{1-3x}$ 5. Expand using the geometric series formula $\frac{1}{1-cx} = \sum_{n=0}^\infty c^n x^n$: $G(x) = - \sum_{n=0}^\infty (1)^n x^n + 2 \sum_{n=0}^\infty (3)^n x^n$ $G(x) = \sum_{n=0}^\infty (-1) x^n + \sum_{n=0}^\infty (2 \cdot 3^n) x^n$ $G(x) = \sum_{n=0}^\infty (-1 + 2 \cdot 3^n) x^n$ Therefore, $a_n = -1 + 2 \cdot 3^n$. 4. Changing Variables / Defining a Second Sequence This method transforms the original recurrence into a simpler form, often by substitution or by defining a related sequence. 4.1 Substitution for Divide and Conquer Recurrences For $a_n = c a_{n/k} + f(n)$, set $n=k^m$. This converts it to a linear recurrence in $b_m = a_{k^m}$. $b_m = c b_{m-1} + f(k^m)$. Solve for $b_m$, then substitute $m = \log_k n$ back into the solution. 4.2 Logarithmic Transformation For recurrences involving products or powers, taking the logarithm can linearize them. Example: $a_n = \sqrt{a_{n-1}}$, with $a_0$ given. 1. Apply logarithm to both sides: $\log a_n = \log (\sqrt{a_{n-1}}) = \frac{1}{2} \log a_{n-1}$. 2. Define a new sequence: Let $b_n = \log a_n$. The recurrence becomes $b_n = \frac{1}{2} b_{n-1}$. 3. Solve the new recurrence: This is a simple homogeneous recurrence. The characteristic equation is $r - 1/2 = 0 \implies r = 1/2$. So, $b_n = C \left(\frac{1}{2}\right)^n$. 4. Use initial condition for $b_n$: $b_0 = \log a_0$. So, $C \left(\frac{1}{2}\right)^0 = \log a_0 \implies C = \log a_0$. Thus, $b_n = (\log a_0) \left(\frac{1}{2}\right)^n$. 5. Substitute back to find $a_n$: Since $b_n = \log a_n$, we have $\log a_n = (\log a_0) \left(\frac{1}{2}\right)^n$. Exponentiate both sides: $a_n = e^{(\log a_0) (1/2)^n}$. Using the property $e^{x \ln y} = y^x$ (or $e^{x \log y} = y^x$ in natural log): $a_n = (e^{\log a_0})^{(1/2)^n} = (a_0)^{(1/2)^n}$. 4.3 Difference Sequences (for non-homogeneous terms) This method is essentially telescoping sums. For $a_n = a_{n-1} + f(n)$. 1. Rearrange the recurrence: $a_n - a_{n-1} = f(n)$. 2. Sum both sides from $i=1$ to $n$ (assuming $a_0$ is the starting point): $\sum_{i=1}^n (a_i - a_{i-1}) = \sum_{i=1}^n f(i)$ 3. Evaluate the telescoping sum on the left side: $(a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \dots + (a_1 - a_0) = a_n - a_0$. 4. Combine results: $a_n - a_0 = \sum_{i=1}^n f(i) \implies a_n = a_0 + \sum_{i=1}^n f(i)$. Example: $a_n = a_{n-1} + n$, $a_0=0$. Here $f(n)=n$. $a_n = a_0 + \sum_{i=1}^n i = 0 + (1+2+\dots+n) = \frac{n(n+1)}{2}$. (Matches example 2.3). 4.4 Scaling Factor Transformation For recurrences that have a product term or can be made into a constant difference by division. Example: $a_n = n a_{n-1}$ (for $n \ge 1$), with $a_0$ given. 1. Initial observation (direct expansion/telescoping product): $a_n = n \cdot a_{n-1}$ $a_{n-1} = (n-1) \cdot a_{n-2}$ $a_{n-2} = (n-2) \cdot a_{n-3}$ ... $a_1 = 1 \cdot a_0$ Substitute back successively: $a_n = n \cdot ( (n-1) \cdot a_{n-2} ) = n \cdot (n-1) \cdot ( (n-2) \cdot a_{n-3} ) = \dots$ $a_n = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 1 \cdot a_0 = n! a_0$. 2. Using a scaling factor (formal method): The form $a_n = n a_{n-1}$ suggests dividing by a factorial to simplify. Divide the recurrence by $n!$: $\frac{a_n}{n!} = \frac{n a_{n-1}}{n!} = \frac{a_{n-1}}{(n-1)!}$ 3. Define a new sequence: Let $b_n = \frac{a_n}{n!}$. Then the recurrence becomes $b_n = b_{n-1}$. 4. Solve the new recurrence: This implies $b_n$ is a constant sequence. So $b_n = b_0$ for all $n \ge 0$. 5. Use initial condition for $b_n$ and substitute back: The initial value for $b_n$ is $b_0 = \frac{a_0}{0!} = a_0$. So, $b_n = a_0$. Substitute back $b_n = \frac{a_n}{n!}$: $\frac{a_n}{n!} = a_0$. Thus $a_n = a_0 n!$.