Could you please walk me through this example, as I am struggling with this topic?
Many thanks in advance.
excellent intro to generating functions, as well as advanced discussion.
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:
So and are the roots of
(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.