Question

Solve this recurrence using generating functions.

Answer 1

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

Answer 2

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

Answer 3

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}\]

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

lol

Answer 10

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

Answer 11

Let me try though

Answer 12

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

Answer 13

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.

Answer 14

\[ 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}\]

Answer 15

still remember the extended binomial theorem for negative exponents ?

Answer 16

ofcourse :P

Answer 17

take a good look at the right hand side expression

Answer 18

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

Answer 19

you have 3 fractions.

each fraction can be written as a power series using extended binomial theorem, yes ?

Answer 20

yes

Answer 21

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

Answer 22

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

Answer 23

right, just read below part :

Answer 24

yes that's right

Answer 25

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

Answer 26

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

Answer 27

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

Answer 28

what happened to (-1)^n things ?

Answer 29

you don't need (-1)^n

Answer 30

why ?

Answer 31

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

Answer 32

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

Answer 33

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

Answer 34

\[ 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

Answer 35

but the question was something else :|

Answer 36

that solution also has the same expression right ?

Answer 37

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

Answer 38

\[\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)\]

Answer 39

that doesn't look good

Answer 40

sorry, forgot that x was there

Answer 41

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

Answer 42

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

Answer 43

I was doing the way that pdf taught me :/

Answer 44

diagonally subtract elements and make use of given relation etc.

Answer 45

which pdf ?

Answer 46

yesterday one!

Answer 47

you need to be very lucky for that to work

Answer 48

why so? :O

Answer 49

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

Answer 50

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

Answer 51

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

Answer 52

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

Answer 53

let me walk u through first few steps

Answer 54

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

Answer 55

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

Answer 56

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

Answer 57

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

Answer 58

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

Answer 59

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

Answer 60

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

Answer 61

most of the times or always ?

Answer 62

always

Answer 63

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

Answer 64

its already the standard G(x) :P nvm

Answer 65

so we can take a0 out

Answer 66

\[ \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\]

Answer 67

yes

Answer 68

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

Answer 69

take the summation from 2 to infinity and take a0 out

Answer 70

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\]

Answer 71

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

Answer 72

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

Answer 73

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

Answer 74

oh okay :) i'll go with your method

Answer 75

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

Answer 76

yeah :P

Answer 77

okay

Answer 78

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\]

Answer 79

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\]

Answer 80

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}\)

?

Answer 81

\[ \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\]

Answer 82

yes :D

Answer 83

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

Answer 84

the index variable is just dummy

Answer 85

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

Answer 86

alright :)

Answer 87

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\]

Answer 88

Look at third term, may be split it

Answer 89

\[\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\]

Answer 90

\[ \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}\]

Answer 91

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

Answer 92

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

Answer 93

for the first red term that is