generating function for sequence question

**smplease** · October 24th 2010, 09:04 PM

Consider the sequence $(a_n)_{n\ge 0}$ defined by the following recurrence

$a_0 = 2, a_{n+1} = 4a_n + 5, \forall n \ge 0.$

Let $f(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = a_0+a_1z+a_2+z^2+....$ be the gernerating function for the sequence.
Express f(z) as a rational function.

**chisigma** · October 25th 2010, 05:37 AM

The solution of the difference equation $a_{n+1}= 4\ a_{n} + 5$ with the 'initial condition' $a_{0}=2$ is...

$a_{n} = 2^{2n+1} +5\ n$ (1)

... so that is...

$\displaystyle f(z)= \sum_{n=0}^{\infty} (2^{2n+1}+ 5\ n)\ z^{n}$ (2)

Now we consider separately the terms of (2)...

$\displaystyle \sum_{n=0}^{\infty} 2^{2n+1} z^{n} = 2\ \sum_{n=0}^{\infty} (4z)^{n} = \frac{2}{1-4\ z}$ (3)

$\displaystyle \sum_{n=0}^{\infty} 5\ n\ z^{n} = 5\ \sum_{n=0}^{\infty} n\ z^{n} = 5\ z\ \sum_{n=1}^{\infty} n\ z^{n-1} = 5\ z\ \frac{d}{dz} \frac{1}{1-z} = \frac{5\ z}{(1-z)^{2}}$ (4)

... so that the series (2) converges for $|z|<\frac{1}{4}$ and is...

$\displaystyle f(z)= \frac{2}{1-4\ z} + \frac{5\ z}{(1-z)^{2}}$ (5)

Kind regards

$\chi$ $\sigma$

**smplease** · October 26th 2010, 03:55 AM

Thanks so much for your reply chisigma!

How did you get equation 1 though?

I have been looking for tutorials online for "difference equation" and not making much sense of it.

For eg. If its a similar question with a different sequence

$2a_{n+2} = 9a_{n+1} + 5a_n$

$a_0 = 0, a_1 = 11$

$\forall n \geq 0$

How would you equate the "difference equation"

Thanks again

**Plato** · October 26th 2010, 04:15 AM

Originally Posted by smplease

Thanks so much for your reply chisigma!
How did you get equation 1 though?

Actually there is mistake in $\chi\sigma$ 's equation (1).
You can use this website to see the correct answer.

**smplease** · October 26th 2010, 04:33 AM

Is there a function that can be used to find this answer?

**chisigma** · October 26th 2010, 07:11 AM

A great 'Thank You' to Plato for having found my mistake... a mistake caused by my superficiality

...

If we have a linear first order difference equation of the form...

$\displaystyle a_{n+1}= \alpha_{n}\ a_{n} + \beta_{n}$ , $\a_{0}= a$ (1)

... its solution is...

$\displaystyle a_{n}= p_{n}\ (a + \frac{\beta_{0}}{p_{1}} + \frac{\beta_{1}}{p_{2}} + ... + \frac{\beta_{n-1}}{p_{n}})$ (2)

... where $\displaystyle p_{n}= \prod_{k=0}^{n-1} \alpha_{k}$ . In this case the difference equation is...

$\displaystyle a_{n+1}=4\ a_{n} +5$ , $a_{0}=2$ (3)

... so that is $\alpha_{n}=4=2^{2}$ , $\beta_{n}= 5$ and $a=2$ and the solution of (3) is...

$\displaystyle a_{n}= 2^{2n+1} + 5\ (1+2^{2} + 2^{4} + ...+ 2^{2n}) = 2^{2n+1} + 5\ \frac{2^{2n}-1}{2^{2}-1} = 2^{2n+1} + \frac {5}{3}\ (2^{2n}-1})$ (4)

The first term was correct and the same is for its contribution to $f(z)$ ... the contribution of the second term has to be evaluated...

Kind regards

$\chi$ $\sigma$

**chisigma** · October 26th 2010, 08:12 AM

The contribution of the second term is easy to find because is...

$\displaystyle \sum_{n=0}^{\infty} (2^{2n}-1)\ z^{n} = \sum_{n=0}^{\infty} (4z)^{n} - \sum_{n=0}^{\infty} z^{n} = \frac{1}{1-4z} - \frac{1}{1-z}$ (1)

... so that...

$\displaystyle f(z)= \frac{\frac{11}{3}}{1-4z} - \frac{\frac{5}{3}}{1-z}$ (2)

Kind regards

$\chi$ $\sigma$

Thread: generating function for sequence question

LinkBack

Thread Tools

Display

generating function for sequence question

Similar Math Help Forum Discussions

closed form for sequence z=z^2+c & generating function

Generating function for a sequence

Generating Function Application Question

moment generating function question

last generating function question.

Search Tags