Solve this recurrence using generating functions.

- DLS

Solve this recurrence using generating functions.

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- chestercat

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- DLS

\[\Large a_n = a_{n-1} + 2(n-1) , a_0 = 1\]

- DLS

I'll post my attempt, just let me know where did I go wrong.

- DLS

I'd prefer to write out the recurrence like this :
\[\Large a_{m+1} = a_{m} + 2m\]
\[\Large G(x) = a_0 + a_1 x + a_2 x^2 + ..\]
\[\Large x G(x) = a_0 x + a_1 x^2 + a_2 x^3 ..\]
Subtract them to get :
\[\Large G(x)(1-x) = a_0 + 0x + 2x^2 + 3x^3+..\]
Now I am looking for a pattern on RHS so i'd write it like
\[\Large G(x)(1-x) = 1 - x + x(1 + 2x^2 + 3x^3...)\]
\[\Large G(x)(1-x ) =1 -x + \frac{x}{(1-x)^2}\]

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- DLS

My G(x) isn't matching with my textbook so I guess I messed up somewhere, dunno where.

- ParthKohli

so you need to specifically use generating functions here? a saner way is to assume\[a_n = An^2 + Bn + 1\]

- DLS

Yes I need to use generating functions, I don't want to break it up into homogenous and particular solution part thing.

- DLS

\[\Large G(x) = \frac{1-2x+3x^2}{(1-x)^3}\]

- ParthKohli

lol ok, I only know the IITJEE part of generating functions. I'll try though.

- DLS

lol

- DLS

nope..I was geting cubic stuff in numerator while the textbook has max order of 2..so didn't bother

- DLS

Let me try though

- DLS

\[\Large G(x) = \frac{1-2x+3x^2}{(1-x)^3} = \frac{1}{(1-x)^3} +\frac{x(3x-1)}{(1-x)^3}\]

- DLS

I am attaching the screenshot from my textbook. I can't get better than this quality, sorry D: I am not following the textbook method.

##### 1 Attachment

- ganeshie8

\[ G(x) = \frac{1-2x+3x^2}{(1-x)^3} \\~\\~\\= \frac{1}{(1-x)^3} -2x*\frac{1}{(1-x)^3}+3x^2*\dfrac{1}{(1-x)^3}\]

- ganeshie8

still remember the extended binomial theorem for negative exponents ?

- DLS

ofcourse :P

- ganeshie8

take a good look at the right hand side expression

- ganeshie8

\[ G(x)= \frac{1}{(1-x)^3} -2x*\frac{1}{(1-x)^3}+3x^2*\dfrac{1}{(1-x)^3}\]

- ganeshie8

you have 3 fractions.
each fraction can be written as a power series using extended binomial theorem, yes ?

- DLS

yes

- DLS

\[\large (1-x)^{-3} = C(-3,0) + C(-3,1)(-x) + C(-3,2)(-x)^2+..\]

- DLS

\[\Large C(-n,r) = (-1)^r C(n+r-1,r)\]

- ganeshie8

right, just read below part :
|dw:1449999482848:dw|

- DLS

yes that's right

- ganeshie8

\[a_n = C(-3, n) - 2*C(-3, n-1) + 3*C(-3, n-2)\]

- ganeshie8

just use ur usual formula for converting negative bonomial coefficients to positive

- DLS

\[ a_n = C(n+3-1,n) - 2*C(3+n-1-1,n-1)+3*C(3+n-2-1,n-2)\]

- ganeshie8

what happened to (-1)^n things ?

- ParthKohli

you don't need (-1)^n

- ganeshie8

why ?

- DLS

\[\ a_n = (-1)^nC(n+2,n) - (-1)^{n-1}2*C(n+1,n-1) + (-1)^{n-2}3*(n,n-2)\]

- ParthKohli

the coefficient of \(x^r\) in the expansion of \((1-x)^{-n}\) is simply\[\binom{n+r-1}{n-1}\]unless the (-1)^n comes from some other place

- ganeshie8

Oh right, (-1)^n is not needed

- ganeshie8

\[ a_n = C(n+3-1,n) - 2*C(3+n-1-1,n-1)+3*C(3+n-2-1,n-2)\]
looks good then

- DLS

but the question was something else :|

- ganeshie8

that solution also has the same expression right ?

- DLS

\[\Large G(x) =1 + \frac{x}{(1-x)^3}\]
I had got this.

- DLS

\[\Large \Large G(x) =1 + \frac{x}{(1-x)^3} => 1 + x (1-x)^{-3}\]
Coefficient of x^n in that =>
\[\Large C(-3,n)\]
or
\[\Large C(n+2,n)\]

- ganeshie8

that doesn't look good

- DLS

sorry, forgot that x was there

- DLS

so we need coeff of x^n-1 in the 2nd term

- ganeshie8

your textbook has a nice solution, why not simply use it ?

- DLS

I was doing the way that pdf taught me :/

- DLS

diagonally subtract elements and make use of given relation etc.

- ganeshie8

which pdf ?

- DLS

yesterday one!

- ganeshie8

you need to be very lucky for that to work

- DLS

why so? :O

- ganeshie8

that is not a standard method, that works based on guessing right ?

- ganeshie8

how on earth do you know you need to multiply by x ?
why not x^2 or x^3 ?

- DLS

oh :/ I ignored this method in my textbook because of that :|

- ganeshie8

the standard method is very easy for you because you're familiar with summation notation and power series

- ganeshie8

let me walk u through first few steps

- ganeshie8

\[ a_n = a_{n-1} + 2(n-1) \]

- ganeshie8

step1 : multiply \(x^n\) through out, what do you get ?

- DLS

\[x^na_n = x^n a_{n-1}+x^n 2(n-1)\]

- ganeshie8

Yes, it doesn't matter much but below looks better :
\[a_nx^n = a_{n-1}x^n+ 2(n-1)x^n\]

- ganeshie8

step2 : sum both left side and right side from n = 1 to infinity

- DLS

\[\Large \sum_1^\infty a_nx^n = \sum_1^\infty a_{n-1}x^n+\sum_1^\infty 2(n-1)x^n\]

- ganeshie8

Let \(G(x) = \sum\limits_{0}^{\infty}a_nx^n\) be the required generating function

- DLS

most of the times or always ?

- ganeshie8

always

- ganeshie8

our goal now is to write those infinite series in terms of G(x)

- DLS

its already the standard G(x) :P nvm

- DLS

so we can take a0 out

- ganeshie8

\[ \sum_1^\infty a_nx^n = \sum_1^\infty a_{n-1}x^n+\sum_1^\infty 2(n-1)x^n\]
is same as
\[ \sum_0^\infty a_nx^n-a_0 = \sum_1^\infty a_{n-1}x^n+\sum_1^\infty 2(n-1)x^n\]

- DLS

yes

- ganeshie8

we're done with left hand side, lets look at right hand side

- DLS

take the summation from 2 to infinity and take a0 out

- ganeshie8

Nope, you want to make the exponent match with the index :
\[ \sum_0^\infty a_nx^n-a_0 = \sum_1^\infty a_{\color{red}{n-1}}x^{\color{red}{n}}+\sum_1^\infty 2(n-1)x^n\]

- bubblegum.

i was doing something similar to this but then i got stuck
\(a_n=a_{n-1} +2(n-1)\)
\(a_n -a_{n-1}=2(n-1)\)
lets say the generating function as \(Z\) which will be equal to the generating series
so lets make the series
\(A=1+1x+3x^2+7x^3+13x^4+...\) ----eq 1
now we gotta subtract the \(a_{n-1}\) terms
so we subtract this->
\(xA\)
and \(xA=1x+1x^2+3x^3+7x^4+...\) --eq 2
subtracting eq 2 from eq 1 we get->
\(A-xA=1+2x^2+4x^3+6x^4+8x^5..\)
now we need to find and write the generating function for 2x^2+4x^3.. and then i got stuck thinking what to do with the RHS

- bubblegum.

sorry
take the generating function to be *\(A\)

- ganeshie8

@bubblegum. that works nicely, but that is not general... lot of guessing is required with that method..

- bubblegum.

oh okay :) i'll go with your method

- ganeshie8

we can try both methods, let me finish mine first just so we don't mix up things :)

- DLS

yeah :P

- bubblegum.

okay

- ganeshie8

- ganeshie8

Notice that pulling out \(x\) does the job :
\[ \sum_0^\infty a_nx^n-a_0 = x\sum_1^\infty a_{\color{red}{n-1}}x^{\color{red}{n-1}}+\sum_1^\infty 2(n-1)x^n\]

- ganeshie8

would you agree that
\(\sum\limits_{n=0}^{\infty}a_nx^n\) is same as \(\sum\limits_{n=1}^{\infty}a_{n-1}x^{n-1}\)
?

- ganeshie8

\[ \sum_0^\infty a_nx^n-a_0 = x\sum_1^\infty a_{\color{red}{n-1}}x^{\color{red}{n-1}}+\sum_1^\infty 2(n-1)x^n\]
is same as
\[ \sum_0^\infty a_nx^n-a_0 = x\sum_0^\infty a_{\color{red}{n}}x^{\color{red}{n}}+\sum_1^\infty 2(n-1)x^n\]

- DLS

yes :D

- ganeshie8

you can convince they are same by substituting \(n-1=u\)

- ganeshie8

the index variable is just dummy

- ganeshie8

\(n\) or \(u\)
it doesnt matter

- DLS

alright :)

- ganeshie8

so far we have
\[ \sum_0^\infty a_nx^n-a_0 = x\sum_0^\infty a_{n}x^{n}+\sum_1^\infty 2(n-1)x^n\]

- ganeshie8

Look at third term, may be split it

- DLS

\[\sum_0^\infty a_nx^n-a_0 = x\sum_0^\infty a_{n}x^{n}+\sum_1^\infty 2nx^n-\sum_1^\infty 2x^n\]

- ganeshie8

\[ \sum_0^\infty a_nx^n-a_0 = x\sum_0^\infty a_{n}x^{n}+\color{red}{\sum_1^\infty 2(n-1)x^n}\]
\[ \sum_0^\infty a_nx^n-a_0 = x\sum_0^\infty a_{n}x^{n}+2 \color{red}{\sum_1^\infty nx^n-2\sum_1^\infty x^n}\]

- ganeshie8

Maybe lets plugin \(G(x) = \sum\limits_{0}^{\infty}a_nx^n\) before simplifying those two red terms

- DLS

you can take that from 0 or 1..it doesn't matter right ?

- DLS

for the first red term that is

- ganeshie8

\[ \sum_0^\infty a_nx^n-a_0 = x\sum_0^\infty a_{n}x^{n}+2 \color{red}{\sum_1^\infty nx^n-2\sum_1^\infty x^n}\]
\[G(x)-a_0 = xG(x) + 2 \color{red}{\sum_1^\infty nx^n-2\sum_1^\infty x^n}\]

- DLS

\[G(x)-a_0 = xG(x) + 2 \color{red}{G(x) - 2\sum_1^\infty x^n}\]

- ganeshie8

that is wrong
that first red term is NOT G(x)

- ganeshie8

For G(x) we need to have \(a_n x^n\)
not just \(nx^n\)

- DLS

ohh..yeah sorry my bad

- ganeshie8

\(a_n\) is NOT same as \(n\)

- ganeshie8

we're left with
\[G(x)-a_0 = xG(x) + 2 \color{red}{\sum_1^\infty nx^n-2\sum_1^\infty x^n}\]

- DLS

that is 1/(1-x)^2 then

- ganeshie8

Look at the last red term
does it look familiar ?

- ganeshie8

how did u get 1/(1-x)^2 ?

- DLS

\[1x+2x^2+3x^3..\]
is the expansion of
\[\Large \frac{1}{(1-x)^2}\]

- DLS

sorrry, 1+2x+3x^2..is we can make some modifications to get that

- DLS

take x common in that

- ganeshie8

Ahh that looks nice!
\[\dfrac{1}{1-x} = \sum\limits_{n=0}^{\infty} x^n\]
differentiate both sides and get
\[\dfrac{1}{(1-x)^2} = \sum\limits_{n=\color{red}{1}}^{\infty} nx^{n-1}\]
multiply x both sides and get
\[\dfrac{x}{(1-x)^2} = \sum\limits_{n=\color{red}{1}}^{\infty} nx^{n}\]

- DLS

so we have everything I guess

- ganeshie8

\[G(x)-a_0 = xG(x) + 2 \color{red}{\sum_1^\infty nx^n-2\sum_1^\infty x^n}\]
\[G(x)-a_0 = xG(x) + 2 \color{red}{\dfrac{x}{(1-x)^2}-2(\dfrac{1}{1-x}-1)}\]
?

- DLS

perfect :)

- ganeshie8

perhaps this looks better
\[G(x)-a_0 = xG(x) + 2 \color{red}{\sum_1^\infty nx^n-2\sum_1^\infty x^n}\]
\[G(x)-a_0 = xG(x) + 2 \color{red}{\dfrac{x}{(1-x)^2}-2\dfrac{x}{1-x}}\]
?

- ganeshie8

solve G(x) and it should be same as textbook..

- DLS

nice!! thanks :D
1 more topic down :P
998 to go

- ganeshie8

haha you have no time to waste

- ganeshie8

good luck with the exam tomoro !

- DLS

thanks :) just need to practice some proving stuff and graph theory :)
I was particularly interested in all this stuff since long time so decided to give it more time..trying to study the subj with interest :)

- DLS

I have a decent idea about the rest of the topics, hopefully ill do them :P

- ganeshie8

- ganeshie8

memorizing that formula is a bit tricky

- ganeshie8

it is easy to get confused...

- ganeshie8

i was confused about multiplying (-1)^r earlier..

- DLS

yeah! lots of facts were discovered in this one

- ganeshie8

just make sure you have clarity about the correct formula :)

- DLS

haha hopefully..gotta write them down at a nice place

Looking for something else?

Not the answer you are looking for? Search for more explanations.