Non-linear recursion-Generating functions

Question

How would I find the generating function in closed form of a non-linear recursion? Are there any standard tricks that can be applied to non-linear recursions to find their generating functions in closed form?

Any help would be much appreciated.

Answer 1

The standard tricks are these:

• If $f(x)$ is the generating function for $a_n$, then $xf'(x)$ is the generating function for $na_n$.
• If $f(x),g(x)$ are generating functions for $a_n$ and $b_n$, then $f(x)g(x)$ is the generating function for $\sum_{k=0}^n a_k b_{n-k}$.

These are adequate to rewrite this recurrence relation as a differential equation. Be careful: the given recurrence does not hold for $n=0$, so you will have to add or subtract $a_0$ at some point.