Recurrence Relation Problems PDF

### **Solve the Recurrence Relation** 1. Solve the recurrence relation for $a_n - a_{n-1} .5 + 6a_{n-2} = 0, a_0 = 1, a_1 = 1$. Sol: Given: The recurrence relation is homogeneous of order 2. Characteristic equation: $1 - 5x + 6x^2 = 0$ $=> x = 3, 2$ (Real and distinct) General Solution: (Real a...

### **Solve the Recurrence Relation** 1. Solve the recurrence relation for $a_n - a_{n-1} .5 + 6a_{n-2} = 0, a_0 = 1, a_1 = 1$. Sol: Given: The recurrence relation is homogeneous of order 2. Characteristic equation: $1 - 5x + 6x^2 = 0$ $=> x = 3, 2$ (Real and distinct) General Solution: (Real and distinct), $a_n = A3^n + B2^n$ $=> a_n = A . 3^n + B . 2^n$ To find the constants: Given conditions $a_0 = 1, a_1 = 1$ $n = 0, a_0 = A . 3^0 + B . 2^0$ $1 = A + B$ $n = 1, a_1 = A . 3^1 + B . 2^1$ $1 = 3A + 2B$. Solving we get: $A = -1$ and $B = 2$ $=> Solution: a_n = -1 . (3^n) + 2 . (2^n)$. 2. Solve the recurrence relation for $a_n + 5a_{n-1} + 6a_{n-2} = 42.4^n$, $a_0 = 2, a_1 = 5$. Sol: Given: Recurrence relation is $a_n + 5a_{n-1} + 6a_{n-2} = 42 . 4^n$ The characteristic equation is $r^2 + 5r + 6 = 0$ The general solution is $a_n^h = A(-2)^n + B(-3)^n$ $r^2 + 5r + 6 = 0$ $r^2 + 3r + 2r + 6 = 0$ $(r+3) + 2(r + 3) = 0$ $(r + 3) (r + 2) = 0$ $=> a_n = A(-2)^n + B(-3)^n$ We have RHS $42 . 4^n$ Let the trial solution be $a_n = 42.A.6^{4n} = 42C(4)^n$ Here $4, 6$ is not a set of the characteristic equation. $=> r = -3, - 2$ Therefore, the particular solution is; $a_n = 42C(4)^n$ Therefore, the general solution of is; $a_n = a_n^h + a_n^p$ $a_n = A(-2)^n + B(-3)^n + 42 . C(4)^n$ Therefore, the general solution is: $a_n = A(-2)^n + B(-3)^n + 42C(4)^n$ where A is constant, C is constant, 42C = D is also a constant. 3. Solve the recurrence relation for $a_n + 3a_{n-1} + 2 a_{n-2} = 3^n$, $n >= 0, a_0 = 1, a_1 = 1$. Sol: Step 1: $a_n + 3a_{n-1} + 2 a_{n-2} = 3^n, a_0 = 1, a_1 = 1$ Step 2: $G(x) = \sum_{n=0}^\infty a_n x^n = a_0 + a_1x + a_2x^2 + ...$ Step 3: Multiply $x^n$: $\sum_{n=0}^\infty a_{n+2}x^{n+2} + 3\sum_{n=0}^\infty a_{n+1}x^{n+1} + 2 \sum_{n=0}^\infty a_n x^{n} = \sum_{n=0}^\infty 3^n x^n$ Step 4: To find $G(x)$: $x^2[a_2x^2+a_3x^3+...] + x[a_1x+a_2x^2+...] + 2[a_0+a_1x + a_2x^2+...] = (1 - 3x)^{-1}$ $[G(x) - a_0 - a_1x] + x[G(x) - a_0] + 2G(x) = (1 - 3x)^{-1}$ Given initial conditions $a_0 = 1, a_1 = 1$ $[G(x) - 1 - 1] + x[G(x) - 1] + 2G(x) = (1 - 3x)^{-1}$ $[G(x) - 2]+ x[G(x) - 1] + 2x^2G(x) = x^2(1 - 3x)^{-1}$ $G(x)[1 + 3x + 2x^2] - 2-3x = x^2(1 - 3x)^{-1}$ $G(x)[1 + 3x + 2x^2] = 2 + (3x + 2)x^2(1 - 3x)^{-1}$ $[1 + 3x + 2x^2] G(x) = 2 + (3x + 2)(1 - 3x)^{-1}$ $[1 + 3x + 2x^2] G(x) = x^2 + 3x - 9x^2 + 2 - 6x$ $[1 + 3x + 2x^2] G(x) = -8x - 3x^2 + 2$ $G(x) = \frac{-8x - 3x^2 + 2}{[1 + 3x + 2x^2]}$ Consider: $G(x) = \frac{2 - 3x^2 - 8x}{(1 - 3x)(1 + 3x^2 + 2x^2)}$ $2 - 3x^2 - 8x = A(1 + 3x)(2x + 1) + B (1 - 3x)(2x + 1) + C(1-3x)(1 + 3x)$ $\Rightarrow x = \frac{1}{3}, 2 -3(\frac{1}{9}) - 8(\frac{1}{3}) = A(\frac{1}{3} + 1)[2(\frac{1}{3}) +1 ] + B(0) + C(0)$ $2 - \frac{1}{3} - \frac{8}{3} = A(\frac{4}{3})(\frac{5}{3})$ $\Rightarrow \frac{1}{3} = A (\frac{20}{9})$ $A = \frac{3}{20}$ $\Rightarrow x= -1, 2 -3(-1)^2- 8 (-1) = A(0) + B(1 - 3)(-1 + 1) + C(1 - 3)(- 1 + 3)$ $2 -3 + 8 = 3(4)(-1)$ $\Rightarrow 7 = -12$ $\therefore B = \frac{-7}{12}$ $\Rightarrow x = -\frac{1}{2}, 2 - 3(-\frac{1}{2})^2 - 8(-\frac{1}{2}) = A(0) + B(0) + C(1 - 3(-\frac{1}{2}))(-\frac{1}{2} + 1)$ $2 + \frac{3}{2} - 4 = C(1 + \frac{3}{2})(\frac{1}{2})$ $\frac{3}{4} = C(\frac{5}{2})(\frac{1}{2})$ $C = \frac{6}{5}$ Therefore, $G(x) = \frac{3}{20(1-3x)} + \frac{-7}{12(x + 1)} + \frac{6}{5(2x + 1)}$ $\sum_{n=0}^\infty a_n x^n= \frac{3}{20} \sum_{n=0}^\infty 3^n x^n + \frac{-7}{12} \sum_{n=0}^\infty (-1)^n x^n + \frac{6}{5} \sum_{n=0}^\infty (-2)^n x^n$ Equating Coefficient of $x^n$: $a_n = \frac{3}{20} (3^n) + \frac{-7}{12} (-1)^n + \frac{6}{5} (-2)^n$ 4. Solve the recurrence relation for $a_n - 5a_{n-1} + 6a_{n-2} = 2 + 3n$ with $a_0 = 2, a_1 = 5$. Sol: Given: Step 1: $a_n - 5a_{n-1} + 6a_{n-2} = 2 + 3n$ It is a non-homogeneous relation with order 2. General solution: $a_n^h = A2^n + B3^n$ To find $a_n^p$? Homogeneous relation: $a_n -5a_{n-1} +6a_{n-2} = 0$ Characteristic equation: $y^2 - 5y + 6 = 0$ Roots: $y = 3,2$ (Real & Distinct) Homogeneous Solution: $a_n^h = A2^n + B3^n$ To find $a_n^p$: RHS = 2 + 3n (Polynomial of degree 1) Trial Solution: $a_n^p = A + An + 2$ To find A, A, assuming $a_n = A + Aa + 2$, $a_{n-1} = A + A(n-1) + 2$, $a_{n-2} = A + A(n-2) + 2$ $a_n - 5a_{n-1} + 6a_{n-2} = 2 + 3n$ $[A + An + 2] - 5[A + A(n-1) + 2] + 6[A + A(n-2) + 2] = 2 + 3n$ $(A +An - 5A - 5A(n-1) + 6A + 6A(n-2) = 2 + 3n$ $A[1 - 5 + 6] + An[1 - 5 + 6] + A[-6 - 12] = 2 + 3n$ Comparing coefficients: $3A - 5A + 6A = 0$ $2A - 3 = 0$ $A = \frac{3}{2}$ $A - 5A_1 + 6A_2 = 0$ $2A_1 = 2 + 6$ $2A_1 = 8$ $A_1 = 4$ $\therefore$ Particular Solution: $a_n^p = 3 + \frac{3}{2}n + 2$ $\therefore$ Given Condition is: $a_0 = 2, a_1 = 5$ General Solution : $a_n = A2^n + B3^n + \frac{3}{2}n + 5$ n = 0, $a_0 = A2^0 + B3^0 + \frac{3}{2}(0) + 5$ $2 = A + 3 + 5$ $A + B = -3 + 5$ n = 1, $a_1 = A2^1 + B3^1 + \frac{3}{2}(1) + 5$ $5 = 2A + 3B + \frac{3}{2} + 5$ $5 = 2A + 3B + \frac{13}{2}$ $2A +3B = 5 - \frac{13}{2}$ $2A + 3B = \frac{-3}{2}$ $4A + 6B = -3$ Solving: i & ii by Calculator: $A = \frac{-15}{2}, B = 2$ Therefore, the solution is: $a_n = (-1\frac{1}{2}) . 2^n + (2)3^n + 3 + \frac{3}{2}n + 5$ 5 Apply generating function method to find the solution of $a_{n+2} + 6 a_{n-1} + 9 a_{n-2} =3^n$ with $a_0 = 2$ and $a_1 = 3$. Sol: Step 1: $a_{n+ 2} + 6 a_{n-1} + 9 a_{n-2} = 3^n$, $a_0 = 2, a_1 = 3$ Step 2: Let $G(x) = \sum_{n=0}^\infty a_n x^n$ Step 3: Multiply by $x^n$: $\sum_{n=0}^\infty a_{n+2}x^{n+2} + 6 \sum_{n=0}^\infty a_{n+ 1}x^{n+1} + 9 \sum_{n=0}^\infty a_n x^{n} = \sum_{n=0}^\infty 3^n x^n$ Step 4: To find $G(x)$: $x^2[a_2x^2 + a_3x^3 + ...] - x[a_1x + a_2x^2 + ...] + [a_0 + a_1x + a_2x^2 + ...] = (1 - 3x)^{-1}$ $x^2[G(x) -a_0 - a_1x] - 6x[G(x) - a_0] + 9x^2[G(x)] = (1 - 3x)^{-1}$ $[G(x) - a_0 - a_1x] - 6x [G(x) - a_0] + 9x^2 [G(x)] = x^2(1 - 3x)^{-1}$ $G(x)[1 - 6x + 9x^2] = x^2 - 5 - 12x$ $G(x)[1 - 6x + 9x^2] = x²-(5+12x )(1-3x )$. $G(x)[1 - 6x + 9x^2] = x^2 - 5 + 15x + 12x + 36x^2$ $G(x) = \frac{x² + 34x - 5}{(1-3x)}$ Consider: $G(x) = \frac{x^2 + 34x - 5}{(1-3x)(1 + 3x)(1 - 3x)(1 - 3x)}$ $x^2 + 34x - 5 = A(1 + 3x)^2 + B (1 - 3x)(1 + 3x) + C(1-3x)(1 + 3x)$ $x^2 + 34x - 5 = A(1 + 6x + 9x^2) + B (1 - 9x^2) +C(1 - 9x^2)$ Put: $x = \frac{1}{3}, (\frac{1}{3})^2 + 34(\frac{1}{3}) - 5 = A(1 + 3(\frac{1}{3})) + B(0) + C(0)$ $\frac{1}{9} + \frac{34}{3} - 5 = A(2)$ $\Rightarrow \frac{73}{9} = 2A$ $A = \frac{73}{18}$ Put: $x = -\frac{1}{3}, (\frac{1}{3})^2 + 34(-\frac{1}{3})- 5 = A(0) + B(0) + C(0)$ $\therefore B = 0$ $\therefore C = 0$ Equating coefficient of $x^n$: $a_n = \frac{73}{18}(3^n) + 0 . (-3)^n + 0 . (-3)^n$