# Is there any way to solve recurrence equations with variable coefficients?

So far I have done some problems that are best solved using generating functions. These mostly contain variable coefficients. A simple one is $H(n) = (n+2)H(n-2)$. I have found solutions to these equations using mathematical induction, which requires a bit of conjecturing (by checking the result for initial values) and then proving it. But what about bigger equations,* is there a definite way of solving them and obtain a simple formula (without resorting to generating functions)?

edit: *Functions like $H(n) =f_1(n)H(n-1) + f_2(n)H(n-2) + \cdots + f_k(n)H(n-k)$. Where $f_1, f_2,\dots, f_k$ are functions of $n$.

-
You might want to describe much more precisely what are the bigger equations which interest you. – Did Jul 23 '12 at 10:24
When each $f_i(n)$ is a polynomial in $n$, the function $H$ is called polynomially recursive (or $P$-recursive) by Stanley. Chapter 6 of Stanley's Enumerative Combinatorics Volume II addresses this, as does his paper Differentiably Finite Power Series''. The results are largely about translating between generating functions that satisfy a differential equation and these sequences, as well as closure properties. It's a nice theory, but not as ambitious as what you seek. Simple formulas in general are unlikely to exist unless you severely restrict the $f_i$'s. – Hugh Denoncourt Jul 23 '12 at 16:47
@HughDenoncourt Thank you for referring me to the book and the paper. I will give it a look. – Andariel Jul 23 '12 at 17:17

$n\to n+2$ :

$H(n+2)=(n+4)H(n)$

$n\to 2n$ :

$H(2n+2)=(2n+4)H(2n)$

$H(2(n+1))=2(n+2)H(2n)$

$H(2n)=\Theta_1(n)\prod\limits_n(2(n+2))$ , where $\Theta_1(n)$ is an arbitrary periodic function with unit period

$H(2n)=\Theta_1(n)2^n\Gamma(n+2)$ , where $\Theta_1(n)$ is an arbitrary periodic function with unit period

$H(n)=\Theta(n)2^{\frac{n}{2}}\Gamma\left(\dfrac{n}{2}+2\right)$ , where $\Theta(n)$ is an arbitrary periodic function with period $2$

-
Sorry but this is not the question. Read again. – Did Sep 13 '12 at 9:24