MathOverflow is a question and answer site for professional mathematicians. 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

I wonder whether it is impossible to write the nth Motzkin number as a sum of a fixed number of, say, hypergeometric terms. To illustrate what I mean: $n!+(2n)!$ is not a hypergeometric term, but it is written as a sum of two hypergeometric terms.

I'd also appreciate other examples, especially if they come from counting weighted Motzkin paths.

share|cite|improve this question
Martin, I added the tag. The simplest formula I found for your numbers is $a_n=\dfrac1{n+1}\sum_i \dfrac{(n+1)!}{i!(i+1)!(n-2*i)!}$. But there are so many other examples (practically everything I know! :-) ), like Apery's numbers $\sum_k{\dbinom{n+k}{k}}^2{\dbinom{n}{k}}^2$, or Domb numbers, or whatever. Proving that there is no finite hypergeometric sum is the subject of Petkovcek's algorith in $A=B$. – Wadim Zudilin Jun 3 '10 at 11:54
Do I understand correctly that formula (10) at for the $n$th Motzkin number as a hypergeometric $\textit{function}$ is a sum of $n/2$ hypergeometric $\textit{terms}$? – Victor Protsak Jun 3 '10 at 12:04
Victor, yes you do, but finite number of hypergeometric terms means finite and independent of $n$. – Wadim Zudilin Jun 3 '10 at 12:09
up vote 3 down vote accepted

Chapter 8 of Petkovsek--Wilf--Zeilberger $A=B$ starts as follows:

"If you want to evaluate a given sum in closed form, so far the tools that have been described in this book have enabled you to find a recurrence relation with polynomial coefficients that your sum satisfies. If that recurrence is of order 1 then you are finished; you have found the desired closed form for your sum, as a single hypergeometric term. If, on the other hand, the recurrence is of order $\ge2$ then there is more work to do. How can we recognize when such a recurrence has hypergeometric solutions, and how can we find all of them?"

"In this chapter we discuss the question of how to recognize when a given recurrence relation with polynomial coefficients has a closed form solution. We first take the opportunity to define the term closed form."

"A function $f(n)$ is said to be of closed form if it is equal to a linear combination of a fixed number, $r$, say, of hypergeometric terms. The number $r$ must be an absolute constant, i.e., it must be independent of all variables and parameters of the problem."

"Take a definite sum of the form $f(n) = \sum_k F(n; k)$ where the summand $F(n; k)$ is hypergeometric in both its arguments. Does this sum have a closed form? The material of this chapter, taken together with the algorithm of Chapter 6, provides a complete algorithmic solution of this problem."

There are many examples in this chapter which illustrate the algorithm, like Ap\'ery's numbers $$ \sum_k{\binom{n+k}k}^2{\binom{n}k}^2. $$ Your particular sequence $$ \sum_k\frac{n!}{i!(i+1)!(n-2i)!} $$ falls into the group covered by the algorithm of Chapter 8.

share|cite|improve this answer
And the 3-term relation, as far as I follow the OEIS link, is $(n+2)a_n=(2n+1)a_{n-1}+(3n-3)a_{n-2}$. – Wadim Zudilin Jun 3 '10 at 13:34
thanks a lot for that very precise answer! I admit I'm a little embarassed - I guess I haven't done my homework properly :-) Up to today I thought that hyper only (dis)proves that something is a hypergeometric term... Again, many thanks! – Martin Rubey Jun 3 '10 at 14:04
You are welcome, Martin! $A=B$ is a helpful source. To everybody. – Wadim Zudilin Jun 3 '10 at 14:14
Meanwhile I realised what I should have learnt a long time ago, but didn't, namely Theorem 8.7.1 of A=B: Let L be a linear recurrence operator with polynomial coefficients, and h ∈ L(H_K) such that Lh = 0. If h = sum h_i where h_i are pairwise dissimilar hypergeometric terms then Lh_i = 0, for i = 1, 2, ..., k. – Martin Rubey Jun 3 '10 at 14:50

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.