# solving a recurrence

given the general recurrence equation $a_{n+1}-a_{n}=f(n)a_{n+2}$ (1)

is this possible to find a function $g(x)$ so $g(x)= \sum_{n=0}^{\infty}a_{n}x^{n}$ ?? where the $a_{n}$ are the solutions of the recurrence (1)

in case $f(n)=const$ i know how to get it but for a non constant function $f(n)$ i have no idea , for $f(n)$ a Polynomial i guess that $g(x)$ will satisfy a differential equation

-
Do you really want the $f(n)$ to go on the $a_{n+2}$ term? If so, a necessary condition for a unique solution is that $f(n) \neq 0$ for all $n$. –  mrf Apr 21 '12 at 9:33

Indeed, when $f$ is a polynomial you will get a differential equation. Define

$$g(x)=\sum_{n=0}^\infty a_n x^n.$$

Then

$$h(x):=\frac{g(x)-a_0}{x}-g(x)=\sum_{n=0}^\infty (a_{n+1}-a_n)x^n=\sum_{n=0}^\infty a_{n+2}f(n) x^n. \tag{1}$$

Now the falling factorials form a $\Bbb Q$-basis for the vector space of rational-coefficient polynomials, thus we can write $f(n)=\sum_k c_k (n)_k$ and obtain

$$h(x) = \sum_k c_k\sum_{n=0}^\infty a_{n+2} (n)_k x^n = \left(\sum_k c_k x^k \frac{d^k}{dx^k}\right)\underbrace{\sum_{n=0}^\infty a_{n+2}x^n}_{\ell(x)}. \tag{2}$$

Note that

$$\ell(x)=\frac{g(x)-a_0-a_1x}{x^2}.$$

Combining $(1)$ and $(2)$ gives the desired differential equation. Similar algebra works when $f$ is a combination of powers and exponentials as well. I'm not sure if there's a general solution to the problem, though...

-
Nice argument, Anon! –  Giuseppe Tortorella Apr 21 '12 at 9:49