# Using generating functions to solve recurrences

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}$

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.

• I am confused by your steps, so you created a generating function and then solve the equation? Jun 6 '17 at 20:34
• @Maggie By definition the generating function of a sequence is the formal power series with the elements of the sequence as coefficients. Then you use the recurrence relation on the series, regroup in order to re-obtain an expression in terms of known functions and the generating function (maybe multiplied by $x$, derived or something) and solve to find an explicit expression for the generating function. Finally you expand it into a power series and the coefficients give you the sequence you were looking for. Jun 6 '17 at 22:26

This can be done easier if you find the homogeneous solution first, and then variation of constants to find a particular solution, just like this is done with differential equations.

We have an associated polynomial $P(r) = r -5$ with root $r = 5$.

Therefore, $u_n^h = c*5^n$

For the particular solution $u_n^p$, we suggest $A*4^n$

Filling this in the original equation yields:

$$A*4^n - 5A*4^{n}/4 = 4^n \iff A - 5/4A = 1 \iff -1/4A = 1 \iff A = -4$$

Hence, the solution for $a)$ is $$u_n = c*5^n - 4^{n+1}$$

$c$ can be determined by the initial conditions.

You can do something analogue for $b)$ as well, but a particular solution of this form won't work anymore, because it is already in the homogeneous equation.

Try instead $u_n^p = A*n*5^n$.

• I am not familiar to this method of solving. How do you know that it was associated polynomial with root = 5? Jun 6 '17 at 20:37
• An example will make everything clear: the associated polynomial of $u_n - 5u_{n-1} + 7u_{n-2}$ is $P(r) = r^2 - 5r + 7$. If $r_1,r_2$ are roots of this polynomial, then $u_n^h = c_1r_1^n + c_2r_2^n$. But you should use the method you were taught.
– user370967
Jun 6 '17 at 20:40
• I see, you let $r^n = u_n$. Thus $r^n -5r^{n-1} +7r^{n-2}$, then you factor out $r^{n-2}$ and you find the general solution, is that correct? Jun 6 '17 at 20:43
• I just think about it as keeping the coefficients and adding increasing powers of $r$ starting from zero.
– user370967
Jun 6 '17 at 20:47