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