http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf
excellent intro to generating functions, as well as advanced discussion.
http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf
excellent intro to generating functions, as well as advanced discussion.
Hello Banana1Starting with , write this using the first two terms that we've been given as:
Then plug in the recurrence relation:
Next, separate the summations, taking out powers of so that the power that's left matches the subscript of the term:
Next, we change the summation limits so that we get terms in :
Now we can express the summations in terms of the original one for :
(That's the clever bit!)
Then we get the Partial Fractions by equating the denominators:
Compare coefficients:
So and are the roots of
Let's say
(So note that and .)
Using the usual Partial Fractions technique gives
So we can write
... and I'll leave it to you to see if you can supply the missing working and finish up.
Grandad