## “Closed” form for Motzkin and related numbers

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.

-
 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 2010 at 11:54 Do I understand correctly that formula (10) at mathworld.wolfram.com/MotzkinNumber.html for the $n$th Motzkin number as a hypergeometric $\textit{function}$ is a sum of $n/2$ hypergeometric $\textit{terms}$? – Victor Protsak Jun 3 2010 at 12:04 Victor, yes you do, but finite number of hypergeometric terms means finite and independent of $n$. – Wadim Zudilin Jun 3 2010 at 12:09

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.

-
 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 2010 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 2010 at 14:04 You are welcome, Martin! $A=B$ is a helpful source. To everybody. – Wadim Zudilin Jun 3 2010 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 coeﬃcients, 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 2010 at 14:50