[Math] Using generating functions to solve recurrences

Question

Use generating functions to solve the following recurrences.

(a) $u_{n} − 5u_{n−1} = 4^n$ with $u_{0} = 7 $

(b) $u_{n} − 5u_{n−1} = 5^n$ with $u_{0} = 7$

I am not sure if I am on the right track.

Here is my working out for b):

b) let $\int(x) = a_0 + a_1x^1 +a_2x^2 + a_3x^3 + …$

$5x $$\int(x) = 5a_0x + 5a_1x^2 + 5a_2x^3 + …$

$(1-5x) $$\int(x) = a_0 + (a_1-5a_0)x + (a_2-5a_1)x^2 + (a_3 -5a_2)x^3 …$

sub in $u_0 = 7$

= $ 7 + 5x +5^2x^2 + 5^3x^3 + ….$

$= 7 + \frac{(5x)}{1-5x}$

then $\int(x)=\frac{(7)}{1-5x} + \frac{(5x)}{(1-5x)^2} $

$\frac{(7)}{1-5x} = \sum_{n=0}^\infty 7(5x)^n = \sum_{n=0}^\infty 7 (5^n x^n)$

by using the formula of a geometric series

$\frac{(5x)}{(1-5x)^2} = 5x(1-5x)^2$
$= 5x *\sum_{n=0}^\infty {n+1 \choose 1} (5x)^n$

$= \sum_{n=0}^\infty 5(n+1)5^n x^{n+1} $

let $ n = n -1 $

then : $\sum_{n=0}^\infty (7*5^n)x^n +\sum_{n=0} 5_n 5^{n-1}x^n$

but $\int(x)= \sum_{n=0}^\infty a_n x^n $

Therefore, $a_n = 7*5^n +5_n5^{n-1} $

Answer 1

The clean way to proceed is the following:

Let $F(x) = \sum_{n\ge0}u_nx^n$, then by using the recurrence relation we have $$F(x) = 7+\sum_{n\ge1}(5u_{n-1} + 4^n)x^n = 6 + \sum_{n\ge0}(4x)^n + 5x\sum_{n\ge1}u_{n-1}x^{n-1} = 6 + \frac{1}{1-4x} + 5xF(x)$$ It follows that $$F(x) = \frac{6 + \frac{1}{1-4x}}{1-5x} = -\frac{24x-7}{(4x-1)(5x-1)} = \frac{11}{1-5x}-\frac{4}{1-4x}$$ $$= \sum_{n\ge0}(11(5x)^n-4(4x)^n) = \sum_{n\ge0}(11\cdot5^n-4^{n+1})x^n$$ and thus that $$u_n = 11\cdot5^n-4^{n+1}\ .$$

This was the first recurrence, I leave the second one to you.