Generating Function (Finding An)

Printable View

March 6th 2012, 01:14 PM
ThatPinkSock

Generating Function (Finding An)

Discrete Mathematics with Graph Theory
by Goodaire and Parmenter

Page 182 # 10b

a_n = -10a_n-1 - 25a_n-2, n ≥ 2, given a₀=1, a₁ = 25

So far I have:

f(x) - a₀ -a₁x = -10x(f(x) - a₀) - 25x²f(x)
f(x) - 1 -25x = -10x(f(x) - 1) - 25x²f(x)

Then solving for f(x)

I get:
f(x) = (1+35x)/(1+10X+25x²)
f(x) = (1+35x)/(1+5x)²

Then when I do partial fractions I get:
(1+35x) = (A/(5x+1)^2) + (B/(5x+1))

Then solving for A & B I get:
A = 7
B = -6

And now I'm having trouble finding my a_n coefficient.
March 6th 2012, 03:09 PM
Soroban

Re: Generating Function (Finding An)

Hello, ThatPinkSock!

I am unfamiliar with your method.
I'll show you the procedure I was taught.

Quote:

$a_n \:=\:-10a_{n-1}- 25a_{n-2},\;\; n \ge2,\;\;a_0 = 1,\;a_1 = 25$

We have: . $a_n + 10a_{n-1} + 25a_{n-2} \:=\:0$

Let: $x^n = a_n$

Substitute: . $x^n +10x^{n-1} + 25x^{n-2} \:=\:0$

Divide by $x^{n-2}\!:\;\;x^2 + 10x + 25 \:=\:0 \quad\Rightarrow\quad (x+5)(x+5) \:=\:0 \quad\Rightarrow\quad x \:=\:\text{-}5,\,\text{-}5$

The function has the form: . $f(n) \:=\:A(\text{-}5)^n + Bn(\text{-}5)^n$

Substitute the first two terms:

. . $f(0) \,=\, 1\!:\;\;A(\text{-}5)^0 + B(0)(\text{-}5)^0 \:=\:1 \quad\Rightarrow\quad A \:=\:1$

. . $f(1)\,=\,25\!:\;\;A(\text{-}5)^1 + B(1)(\text{-}5)^1 \:=\:25 \Rightarrow\quad \text{-}5A - 5B \:=\:25$

. . . . . . . . . . . $\text{-}5(1) - 5B \:=\:25 \quad\Rightarrow\quad \text{-}5B \:=\:30 \quad\Rightarrow\quad B \:=\:\text{-}6$

Therefore: . $f(n) \:=\:(\text{-}5)^n - 6n(\text{-}5)^n$

. . . . . . . . . . $a_n \;=\;(\text{-}5)^n(1 - 6n)$
March 7th 2012, 05:28 PM
awkward

Re: Generating Function (Finding An)

Hi ThatPinkSock,

For the generating function approach, use the series
$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$ to expand $\frac{B}{5x-1}$
and use the series $\frac{1}{(1-x)^2} = \sum_{n=0}^\infty (n+1) x^n$ to expand $\frac{A}{(5x-1)^2}$ .

Here's one part: $\frac{B}{5x-1} = \frac{-B}{1-5x} = -B \sum_{n=0}^\infty (5x)^n$

I'll leave the rest for you...