most recent 30 from http://mathoverflow.net 2013-06-19T22:59:37Z http://mathoverflow.net/feeds/question/26912 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26912/closed-form-for-motzkin-and-related-numbers Martin Rubey 2010-06-03T11:41:23Z 2010-06-03T12:36:50Z

<p>I wonder whether it is impossible to write the nth <a href="http://www.research.att.com/~njas/sequences/A001006" rel="nofollow">Motzkin number</a> 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.</p> <p>I'd also appreciate other examples, especially if they come from counting weighted Motzkin paths.</p>

http://mathoverflow.net/questions/26912/closed-form-for-motzkin-and-related-numbers/26918#26918 Wadim Zudilin 2010-06-03T12:36:50Z 2010-06-03T12:36:50Z

<p>Chapter 8 of Petkovsek--Wilf--Zeilberger $A=B$ starts as follows:</p> <p>"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?"</p> <p>"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 <em>closed form</em>."</p> <p>"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."</p> <p>"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."</p> <p>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.</p>