Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
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$ :


$n\to 2n$ :



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

According to ,

$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$

share|cite|improve this answer
Sorry but this is not the question. Read again. – Did Sep 13 '12 at 9:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.