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.

  • $\begingroup$ I am confused by your steps, so you created a generating function and then solve the equation? $\endgroup$
    – Maggie
    Jun 6 '17 at 20:34
  • $\begingroup$ @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. $\endgroup$ 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$.

  • $\begingroup$ I am not familiar to this method of solving. How do you know that it was associated polynomial with root = 5? $\endgroup$
    – Maggie
    Jun 6 '17 at 20:37
  • $\begingroup$ 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. $\endgroup$
    – user370967
    Jun 6 '17 at 20:40
  • $\begingroup$ 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? $\endgroup$
    – Maggie
    Jun 6 '17 at 20:43
  • $\begingroup$ I just think about it as keeping the coefficients and adding increasing powers of $r$ starting from zero. $\endgroup$
    – user370967
    Jun 6 '17 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.