# Thread: Recurrence Relations: Generating Functions

1. ## Recurrence Relations: Generating Functions

I was looking to figure out how to solve the following:

The recurrence relation: $\displaystyle a_{n}=4a_{n-1}-4a_{n-2}+4^{n}$
Given: $\displaystyle n\ge 2 , a_{0}=2 , a_{1} = 8$

How would you go about solving this in terms of a generating function?

Thanks!

Kev

2. Hello, Kev!

This one requires another trick . . .

The recurrence relation: .$\displaystyle a_{n}\:=\:4a_{n-1}-4a_{n-2}+4^{n}$ .[1]
Given: .$\displaystyle n\ge 2,\;a_0\,=\,2,\;a_1\,=\,8$

Consider the $\displaystyle (n+1)^{th}$ case: .$\displaystyle a_{n+1} \;=\;4a_n - 4 a_{n-1} + 4^{n+1}$ .[2]

. . . . . . Multiply [1] by 4: . .$\displaystyle 4a_n \;=\;16a_{n-1} - 16a_{n-2} + 4^{n+1}$ .[3]

Subtract [3] from [2]: .$\displaystyle a_{n+1}-4a_n \;=\;4a_n - 20a_{n-1} + 16a_{n-2}$

. . . . .$\displaystyle a_{n+1} - 8a_n + 20a_{n-1} - 16a_{n-2} \;=\;0$

Let $\displaystyle X^k = a_k\!:\;\;X^{n+1} = 8X^n + 20X^{n-1} - 16X^{n-2} \;=\;0$

Divide by $\displaystyle X^{n-2}\!:\;\;X^3 - 8X^2 + 20X - 16 \;=\;0$

. . which factors; .$\displaystyle (X-2)^2(X-4) \;=\;0$

. . and has roots: .$\displaystyle 2,\,2,\,4$

. . . . . .Go for it!

3. I must admit that I'm curious to see the generating function method myself.

-Dan

4. I haven't thought about recurrences and GF since college. This is an interesting topic. Here is an example of one I solved years ago. I still had the paper. I keep running into problems with the one posted. Something small I'm overlooking. Most always is. Maybe this will give you something to go by.

Anyway, here's an example of a recurrence using GF

$\displaystyle a_{n}=5a_{n-1}-6a_{n-2}, \;\ a_{0}=1, \;\ a_{1}=0$

$\displaystyle A(x)=1-6x-30x^{2}-114x^{3}-.................$

$\displaystyle A(x)=\sum_{n=0}^{\infty}a_{n}x^{n}$

$\displaystyle 1+\sum_{n=2}^{\infty}a_{n}x^{n}$

$\displaystyle 1+\sum_{n=2}^{\infty}(5a_{n-1}-6a_{n-2})x^{n}$

$\displaystyle 1+5\sum_{n=2}^{\infty}a_{n-1}x^{n}-6\sum_{n=2}^{\infty}a_{n-2}x^{n}$

$\displaystyle 1+5x\sum_{n=2}^{\infty}a_{n-1}x^{n-1}-6x^{2}\sum_{n=2}^{\infty}a_{n-2}x^{n-2}$

$\displaystyle 1+5x\sum_{k=1}^{\infty}a_{k}x^{k}-6x^{2}\sum_{k=0}^{\infty}a_{k}x^{k}$

$\displaystyle 1+5x\sum_{k=0}^{\infty}a_{k}x^{k}-5x(1)-6x^{2}\sum_{k=0}^{\infty}a_{k}x^{k}$

$\displaystyle A(x)=1+5xA(x)-5x-6x^{2}A(x)$

Let y=A(x):

$\displaystyle y=1+5xy-5x-6x^{2}y$

$\displaystyle y=\frac{1-5x}{6x^{2}-5x+1}=\frac{-2}{1-3x}+\frac{3}{1-2x}$

Notice the familiar geometric series solution in the PFD, $\displaystyle \sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}$

This gives us $\displaystyle \boxed{a_{n}=3\cdot{2^{n}}-2\cdot{3^{n}}}$

Hope this helps. I can easily get the result from Maple, but that's no fun.

5. Hello, Kev ... and anyone else interested,

Thought I'd show how I crank out the recursion function.

In the above problem, we had roots: .$\displaystyle X \:=\:2,\,2,\,4$
. . where $\displaystyle X$ the base of exponential terms.

We now construct the function.
It contains: $\displaystyle 2^n$ and $\displaystyle 4^n$
And because the 2 is repeated, we have the term: .$\displaystyle n\!\cdot2^n$

The function has the form: .$\displaystyle a(n) \;=\;A\!\cdot\!2^n + B\!\cdot\!n\!\cdot\!2^n + C\!\cdot\!4^n$
. . and we must determine $\displaystyle A,\,B,\,C.$

We use the first two terms of the sequence: .$\displaystyle a(0) =2,\;a(1) = 8$
. . and we can calculate the third term: .$\displaystyle a(2) = 40$

So we have:

$\displaystyle \begin{array}{ccccccccc}a(0) = 2: & A\!\cdot\!2^0 + B\!\cdot\!0\!\cdot2^0 + C\!\cdot\!4^0 & = & 2 & \Rightarrow & A + C & = & 2 & [1] \\ a(1) = 8: & A\!\cdot\!2^1 + B\!\cdot\!1\!\cdot\!2^1 + C\!\cdot\!4^1 & = & 8 & \Rightarrow & 2A + 2B + 4C & = & 8 & [2] \\ a(2) = 40: & A\!\cdot\!2^2 + B\!\cdot\!2\!\cdot\!2^2 + C\!\cdot\!r^2 & = & 40 & \Rightarrow & 4A + 8A + 16C & = & 40 & [3]\end{array}$

Divide [3] by -4: .$\displaystyle -A - 2B - 4C \:=\,\text{-}10$
. . . . . . Add [2]: .$\displaystyle 2A + 2B + 4C \:=\;\;8$

And we get: .$\displaystyle \boxed{A \:=\:\text{-}2}$

Substitute into [1]: .$\displaystyle \text{-}2 + C \:=\:2\quad\Rightarrow\quad \boxed{C \:=\:4}$

Substitute into [2]: .$\displaystyle 2(\text{-}2) + 2B + 4(4) \:=\:8\quad\Rightarrow\quad \boxed{B \:=\:\text{-}2}$

The function is: .$\displaystyle a(n) \;=\;-2\!\cdot\!2^n - 2\!\cdot\!n\!\cdot\!2^n + 4\!\cdot\!4^n \;=\;-2^{n+1} - n\!\cdot\!2^{n+1} + 4^{n+1}$

. . $\displaystyle = \;-(1 + n)2^{n+1} + (2^2)^{n+1} \;=\;-(n+1)2^{n+1} + 2^{2n+2} \;=\;2^{2n+2} - (n+1)2^{n+1}$

Factor: .$\displaystyle \boxed{\:a(n) \;=\;2^{n+1}\left[2^{n+1} - (n+1)\right]\:}$

6. Originally Posted by galactus
Anyway, here's an example of a recurrence using GF

$\displaystyle a_{n}=5a_{n-1}-6a_{n-2}, \;\ a_{0}=1, \;\ a_{1}=0$

$\displaystyle A(x)=\sum_{n=0}^{\infty}a_{n}x^{n}$
$\displaystyle A(x)=1+5xA(x)-5x-6x^{2}A(x)$

Let y=A(x):

$\displaystyle y=1+5xy-5x-6x^{2}y$

$\displaystyle y=\frac{1-5x}{6x^{2}-5x+1}=\frac{-2}{1-3x}+\frac{3}{1-2x}$

Notice the familiar geometric series solution in the PFD, $\displaystyle \sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}$

This gives us $\displaystyle \boxed{a_{n}=3\cdot{2^{n}}-2\cdot{3^{n}}}$
If you would be so kind...

I'm trying to run the original question through this method and I'm running into some trouble. I know I can avoid this by using Soroban's trick of putting the recursion into a form that removes the $\displaystyle 4^n$ term, but can this be done from the original problem itself?

I'm probably being confusing. I'll just post this:
Define a series
$\displaystyle A(x) = \sum_{n = 0}^{\infty}a_nx^n$

Then
$\displaystyle A(x) = 2 + 8x + \sum_{n = 2}^{\infty}(4a_{n - 1} - 4a_{n - 2} + 4^n)x^n$

$\displaystyle A(x) = 2 + 8x + 4 \sum_{n = 2}^{\infty}a_{n - 1}x^n - 4 \sum_{n = 2}^{\infty} a_{n - 2}x^n + \sum_{n = 2}^{\infty}4^nx^n$

The last term is giving me problems. All I can think of to do with it is to cast it in the form
$\displaystyle \sum_{n = 2}^{\infty}4^nx^n = \sum_{n = 2}^{\infty}(4x)^n$

But when I complete the steps of the method to find an equation for A(x) I get
$\displaystyle A(x) = 2 + 8 + 4xA(x) - 8x - 4x^2A(x) - 2 - 32x + A(4x)$

Assuming I have everything else right, I'm still stuck with that A(4x) term. Any thoughts?

-Dan

7. That is the same exact snag I run into, TQ.

Solving for y and using PFD, results in $\displaystyle \frac{-7}{2x+1}-\frac{13}{2x-3}$

I don't beleive that gets us anywhere, though?.

Alas, I am at work and don't have much time. I will try to take a glance this evening.

Hey. This is #1000. I am now a contributor, as Janvdl reminded me.

8. Originally Posted by galactus
That is the same exact snag I run into, TQ.

That can't work in general, I don't think. We can't assume that $\displaystyle A(4x) = 4A(x)$ in general. (What's that called anyway? A homogeneous function, or something like that?)

Originally Posted by galactus
Hey. This is #1000. I am now a contributor, as Janvdl reminded me.
Congrats!

-Dan

9. With that A(4x), I was grabbing at straws. There's something to be done with that 4^n, I just don't know for sure what it is. I have never tackled any like that. If you figure it out, please let me know. I will surely reciprocate if I get lucky.
Perhaps a search regarding generating functions and recurrence relations may prove fruitful.

10. Well: $\displaystyle A(4x)=\sum_{n=0}^{\infty}{a_n\cdot{4^n}\cdot{x^n}}$

But we have: $\displaystyle \sum_{n=2}^{\infty}{4^n\cdot{x^n}}$

Which are not necessarily the same

Our equation is: $\displaystyle A(x)\cdot{(1-2x)^2}=2+\sum_{n=2}^{\infty}{4^n\cdot{x^n}}$

We have to remember now that $\displaystyle \frac{1}{(1-2x)^2}=\sum_{n=1}^{\infty}{n\cdot{(2x)^{n-1}}}$

Finally:$\displaystyle A(x)=2\sum_{n=0}^{\infty}{(n+1)2^n\cdot{x^{n}}}+\l eft(\sum_{n=0}^{\infty}{(n+1)2^n\cdot{x^{n}}}\righ t)\cdot{\left(\sum_{n=2}^{\infty}{4^n\cdot{x^n}}\r ight)}$

Then doing that product we are done