Q3Discrete Mathematics Structure

Question

Use generating functions to solve the recurrence relation a_r - 7a_{r-1} + 10a_{r-2} = 0 for r ≥ 2 where a_0 = 10 and a_1 = 41.

Answer 1

Recurrence: $a_{r} - 7 a_{r - 1} + 10 a_{r - 2} = 0$ . Let $G (x) = \sum a_{r} x^{r}$ .

Multiply by $x^{r}$ and sum from $r = 2$ : $\sum (a_{r} x^{r} - 7 a_{r - 1} x^{r} + 10 a_{r - 2} x^{r}) = 0$ .

$(G (x) - a_{0} - a_{1} x) - 7 x (G (x) - a_{0}) + 10 x^{2} G (x) = 0$

$G (x) (1 - 7 x + 10 x^{2}) = a_{0} + a_{1} x - 7 a_{0} x = 10 + 41 x - 70 x = 10 - 29 x$

$G (x) = \frac{10 - 29 x}{( 1 - 5 x ) ( 1 - 2 x )} = \frac{A}{1 - 5 x} + \frac{B}{1 - 2 x}$

$10 - 29 x = A (1 - 2 x) + B (1 - 5 x)$ . For $x = 1/5, 10 - 29/5 = A (1 - 2/5) ⟹ 21/5 = A (3/5) ⟹ A = 7$ . For $x = 1/2, 10 - 29/2 = B (1 - 5/2) ⟹ - 9/2 = B (- 3/2) ⟹ B = 3$ .

Actually $A = 3, B = 7$ or similar. Let's check: $10 - 29 x = 3 (1 - 5 x) + 7 (1 - 2 x) = 3 - 15 x + 7 - 14 x = 10 - 29 x$ . Correct.

$a_{r} = 3 (5^{r}) + 7 (2^{r})$ .

Q3Discrete Mathematics Structure

Question

Answer