Recurrence Relations: Generating Functions

**kevi555** · November 24th 2007, 07:47 PM

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

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

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

Thanks!

Kev

**Soroban** · November 25th 2007, 06:40 AM

Hello, Kev!

This one requires another trick . . .

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

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

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

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

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

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

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

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

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

. . . . . .Go for it!

**topsquark** · November 25th 2007, 10:10 AM

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

-Dan

**galactus** · November 25th 2007, 11:15 AM

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

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

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

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

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

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

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

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

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

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

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

Let y=A(x):

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

$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, $\sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}$

This gives us $\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.

**Soroban** · November 25th 2007, 07:15 PM

Hello, Kev ... and anyone else interested,

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

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

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

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

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

So we have:

$\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] \\<br /> a(1) = 8: & A\!\cdot\!2^1 + B\!\cdot\!1\!\cdot\!2^1 + C\!\cdot\!4^1 & = & 8 & \Rightarrow & 2A + 2B + 4C & = & 8 & [2] \\<br /> 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: . $-A - 2B - 4C \:=\,\text{-}10$
. . . . . . Add [2]: . $2A + 2B + 4C \:=\;\;8$

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

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

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

The function is: . $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}$

. . $= \;-(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: . $\boxed{\:a(n) \;=\;2^{n+1}\left[2^{n+1} - (n+1)\right]\:}$

**topsquark** · November 29th 2007, 06:53 AM

Originally Posted by galactus

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

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

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

Let y=A(x):

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

$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, $\sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}$

This gives us $\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 $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
$A(x) = \sum_{n = 0}^{\infty}a_nx^n$

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

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

**galactus** · November 29th 2007, 10:24 AM

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

I thought about leaving A(4x)=4y.

Solving for y and using PFD, results in $\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.

**topsquark** · November 29th 2007, 10:34 AM

Originally Posted by galactus

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

I thought about leaving A(4x)=4y.

That can't work in general, I don't think. We can't assume that $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

**galactus** · November 29th 2007, 10:52 AM

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.

**PaulRS** · November 30th 2007, 12:47 PM

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

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

Which are not necessarily the same

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

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

Finally: $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

Thread: Recurrence Relations: Generating Functions

LinkBack

Thread Tools

Display

Recurrence Relations: Generating Functions

Similar Math Help Forum Discussions

how to solve this recurrence using generating functions?

recurrence and generating functions

Generating funtion -> recurrence relation

Solving "runtime" of recurrence realtion with generating functions

recurrence relations - degree of the recurrence

Search Tags