Suppose that we’re given the function , find the ordinary generating function associated with it in the form of . Furthermore, find/compute .
We can employ Taylor’s theorem, but to my knowledge, there’s no easy way to construct the derivatives of [that’s left to the more ambitious reader ;)] Instead, we focus on classical algebraic techniques to carry us through the day.
recall that all terms of the form , so this becomes
Okay, let’s suppose that , then the above tells us that
If we compute the first few out, we will see that it looks like
Why, this is the Fibonacci sequence! It seems that for the first few terms we looked at, obeys the fibonacci recurrence
Lemma (Fibonacci Sequence)
Proof: Substituting the definition of in, we have
Finally, recall that , so
so we would expect
If we want a closed form, we can find that, letting
Finally, we can compute