DLS
  • DLS
Solve this recurrence using generating functions.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
DLS
  • DLS
\[\Large a_n = a_{n-1} + 2(n-1) , a_0 = 1\]
DLS
  • DLS
I'll post my attempt, just let me know where did I go wrong.
DLS
  • 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
  • DLS
My G(x) isn't matching with my textbook so I guess I messed up somewhere, dunno where.
ParthKohli
  • ParthKohli
so you need to specifically use generating functions here? a saner way is to assume\[a_n = An^2 + Bn + 1\]
DLS
  • DLS
Yes I need to use generating functions, I don't want to break it up into homogenous and particular solution part thing.
DLS
  • DLS
\[\Large G(x) = \frac{1-2x+3x^2}{(1-x)^3}\]
ParthKohli
  • ParthKohli
lol ok, I only know the IITJEE part of generating functions. I'll try though.
DLS
  • DLS
lol
DLS
  • DLS
nope..I was geting cubic stuff in numerator while the textbook has max order of 2..so didn't bother
DLS
  • DLS
Let me try though
DLS
  • 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
  • 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.
ganeshie8
  • 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
  • ganeshie8
still remember the extended binomial theorem for negative exponents ?
DLS
  • DLS
ofcourse :P
ganeshie8
  • ganeshie8
take a good look at the right hand side expression
ganeshie8
  • ganeshie8
\[ G(x)= \frac{1}{(1-x)^3} -2x*\frac{1}{(1-x)^3}+3x^2*\dfrac{1}{(1-x)^3}\]
ganeshie8
  • ganeshie8
you have 3 fractions. each fraction can be written as a power series using extended binomial theorem, yes ?
DLS
  • DLS
yes
DLS
  • DLS
\[\large (1-x)^{-3} = C(-3,0) + C(-3,1)(-x) + C(-3,2)(-x)^2+..\]
DLS
  • DLS
\[\Large C(-n,r) = (-1)^r C(n+r-1,r)\]
ganeshie8
  • ganeshie8
right, just read below part : |dw:1449999482848:dw|
DLS
  • DLS
yes that's right
ganeshie8
  • ganeshie8
\[a_n = C(-3, n) - 2*C(-3, n-1) + 3*C(-3, n-2)\]
ganeshie8
  • ganeshie8
just use ur usual formula for converting negative bonomial coefficients to positive
DLS
  • 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
  • ganeshie8
what happened to (-1)^n things ?
ParthKohli
  • ParthKohli
you don't need (-1)^n
ganeshie8
  • ganeshie8
why ?
DLS
  • 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
  • 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
  • ganeshie8
Oh right, (-1)^n is not needed
ganeshie8
  • 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
  • DLS
but the question was something else :|
ganeshie8
  • ganeshie8
that solution also has the same expression right ?
DLS
  • DLS
\[\Large G(x) =1 + \frac{x}{(1-x)^3}\] I had got this.
DLS
  • 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
  • ganeshie8
that doesn't look good
DLS
  • DLS
sorry, forgot that x was there
DLS
  • DLS
so we need coeff of x^n-1 in the 2nd term
ganeshie8
  • ganeshie8
your textbook has a nice solution, why not simply use it ?
DLS
  • DLS
I was doing the way that pdf taught me :/
DLS
  • DLS
diagonally subtract elements and make use of given relation etc.
ganeshie8
  • ganeshie8
which pdf ?
DLS
  • DLS
yesterday one!
ganeshie8
  • ganeshie8
you need to be very lucky for that to work
DLS
  • DLS
why so? :O
ganeshie8
  • ganeshie8
that is not a standard method, that works based on guessing right ?
ganeshie8
  • ganeshie8
how on earth do you know you need to multiply by x ? why not x^2 or x^3 ?
DLS
  • DLS
oh :/ I ignored this method in my textbook because of that :|
ganeshie8
  • ganeshie8
the standard method is very easy for you because you're familiar with summation notation and power series
ganeshie8
  • ganeshie8
let me walk u through first few steps
ganeshie8
  • ganeshie8
\[ a_n = a_{n-1} + 2(n-1) \]
ganeshie8
  • ganeshie8
step1 : multiply \(x^n\) through out, what do you get ?
DLS
  • DLS
\[x^na_n = x^n a_{n-1}+x^n 2(n-1)\]
ganeshie8
  • 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
  • ganeshie8
step2 : sum both left side and right side from n = 1 to infinity
DLS
  • 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
  • ganeshie8
Let \(G(x) = \sum\limits_{0}^{\infty}a_nx^n\) be the required generating function
DLS
  • DLS
most of the times or always ?
ganeshie8
  • ganeshie8
always
ganeshie8
  • ganeshie8
our goal now is to write those infinite series in terms of G(x)
DLS
  • DLS
its already the standard G(x) :P nvm
DLS
  • DLS
so we can take a0 out
ganeshie8
  • 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
  • DLS
yes
ganeshie8
  • ganeshie8
we're done with left hand side, lets look at right hand side
DLS
  • DLS
take the summation from 2 to infinity and take a0 out
ganeshie8
  • 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.
  • 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.
  • bubblegum.
sorry take the generating function to be *\(A\)
ganeshie8
  • ganeshie8
@bubblegum. that works nicely, but that is not general... lot of guessing is required with that method..
bubblegum.
  • bubblegum.
oh okay :) i'll go with your method
ganeshie8
  • ganeshie8
we can try both methods, let me finish mine first just so we don't mix up things :)
DLS
  • DLS
yeah :P
bubblegum.
  • bubblegum.
okay
ganeshie8
  • 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\]
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
  • 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
  • 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
  • DLS
yes :D
ganeshie8
  • ganeshie8
you can convince they are same by substituting \(n-1=u\)
ganeshie8
  • ganeshie8
the index variable is just dummy
ganeshie8
  • ganeshie8
\(n\) or \(u\) it doesnt matter
DLS
  • DLS
alright :)
ganeshie8
  • 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
  • ganeshie8
Look at third term, may be split it
DLS
  • 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
  • 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
  • ganeshie8
Maybe lets plugin \(G(x) = \sum\limits_{0}^{\infty}a_nx^n\) before simplifying those two red terms
DLS
  • DLS
you can take that from 0 or 1..it doesn't matter right ?
DLS
  • DLS
for the first red term that is
ganeshie8
  • 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
  • DLS
\[G(x)-a_0 = xG(x) + 2 \color{red}{G(x) - 2\sum_1^\infty x^n}\]
ganeshie8
  • ganeshie8
that is wrong that first red term is NOT G(x)
ganeshie8
  • ganeshie8
For G(x) we need to have \(a_n x^n\) not just \(nx^n\)
DLS
  • DLS
ohh..yeah sorry my bad
ganeshie8
  • ganeshie8
\(a_n\) is NOT same as \(n\)
ganeshie8
  • 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
  • DLS
that is 1/(1-x)^2 then
ganeshie8
  • ganeshie8
Look at the last red term does it look familiar ?
ganeshie8
  • ganeshie8
how did u get 1/(1-x)^2 ?
DLS
  • DLS
\[1x+2x^2+3x^3..\] is the expansion of \[\Large \frac{1}{(1-x)^2}\]
DLS
  • DLS
sorrry, 1+2x+3x^2..is we can make some modifications to get that
DLS
  • DLS
take x common in that
ganeshie8
  • 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
  • DLS
so we have everything I guess
ganeshie8
  • 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
  • DLS
perfect :)
ganeshie8
  • 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
  • ganeshie8
solve G(x) and it should be same as textbook..
DLS
  • DLS
nice!! thanks :D 1 more topic down :P 998 to go
ganeshie8
  • ganeshie8
haha you have no time to waste
ganeshie8
  • ganeshie8
good luck with the exam tomoro !
DLS
  • 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
  • DLS
I have a decent idea about the rest of the topics, hopefully ill do them :P
ganeshie8
  • ganeshie8
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
  • ganeshie8
memorizing that formula is a bit tricky
ganeshie8
  • ganeshie8
it is easy to get confused...
ganeshie8
  • ganeshie8
i was confused about multiplying (-1)^r earlier..
DLS
  • DLS
yeah! lots of facts were discovered in this one
ganeshie8
  • ganeshie8
just make sure you have clarity about the correct formula :)
DLS
  • 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.