4
$\begingroup$

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

  • 1
    You might want to describe much more precisely what are the *bigger equations* which interest you.2012-07-23
  • 4
    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.2012-07-23
  • 0
    @HughDenoncourt Thank you for referring me to the book and the paper. I will give it a look.2012-07-23

1 Answers 1