# generating function for sequence question

• October 24th 2010, 09:04 PM
generating function for sequence question
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.
• October 25th 2010, 05:37 AM
chisigma
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$
• October 26th 2010, 03:55 AM

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
• October 26th 2010, 04:15 AM
Plato
Quote:

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.
• October 26th 2010, 04:33 AM
Is there a function that can be used to find this answer?
• October 26th 2010, 07:11 AM
chisigma
A great 'Thank You' to Plato for having found my mistake... a mistake caused by my superficiality (Headbang)...

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$
• October 26th 2010, 08:12 AM
chisigma
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$
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 34, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9404181241989136, "perplexity": 1917.028293079919}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-36/segments/1471982294158.7/warc/CC-MAIN-20160823195814-00287-ip-10-153-172-175.ec2.internal.warc.gz"}