A binomial sum

[Jaap Spies]

Henry Gould wrote:
> Well the original question actually comes down to this:
> 
> Can we find a closed formula for the binomial coefficient summation
> sum(m=0,n,(-1)^m*binomial(n+m,m))?
> The answer is NO.
> 
> If you omit the alternating signs (-1)^m then it can be done at once of
> course . . .
> See formula No. (1.49), page 7 in my book "Combinatorial Identities, A
> Standardized Set of Tables Listing 500 Binomial Coefficient Summations"
> which I published here in Morgantown, West Virginia in 1972. (By the way my
> book is still available in print)
> 
> Henry Gould
> 
> 
> 

Maybe we can (and maybe we should in this case) accept the definition of "closed form"
from: Petkovsek, Wilf, Zeilberger: "A = B", definition 8.1.1
 > A function f(n) is said to be in 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


Best we can do with Maple's SumTools, there since Maple 8, with implementations
of all algorithms of A=B:

 > with(SumTools[Hypergeometric]);

[AreSimilar, CanonicalRepresentation, ConjugateRTerm, DefiniteSum,
   ExtendedGosper, ExtendedZeilberger, Gosper, IndefiniteSum, IsHolonomic,
   IsHypergeometricTerm, IsProperHypergeometricTerm, IsZApplicable,
   KoepfGosper, KoepfZeilberger, LowerBound, MinimalZpair,
   MultiplicativeDecomposition, PolynomialNormalForm, RationalCanonicalForm,
   SumDecomposition, Verify, WZMethod, Zeilberger, ZeilbergerRecurrence,
   ZpairDirect]

 > T:=(-1)^m*binomial(n+m,m);

                           m
                  T := (-1)  binomial(n + m, m)
 > IsProperHypergeometricTerm(T,n,m);

                               true
 > ZeilbergerRecurrence(T,n,m,F,0..n);


                                     n  n      /    3\
                               6 (-1)  4  GAMMA|n + -|
                                               \    2/
           F(n) - 2 F(n + 1) = -----------------------
                                  (1/2)
                                Pi      GAMMA(n + 2)
 > infolevel[DefiniteSum] := 3:
 > DefiniteSum(T,n,m,0..n);
DefiniteSum:, "try algorithms for definite sum"
Definite:, "Construct the Zeilberger's recurrence"
Definite:, "Solve the recurrence equation ..."
Definite:, "Find hypergeometric solutions"
Definite:, "Find a particular d'Alembertian solution"

DefiniteSum:, "try algorithm for indefinite sum"


                   n
                 -----
                  \
                   )   /    m                   \
                  /    \(-1)  binomial(n + m, m)/
                 -----
                 m = 0

We found a recurrence and indeed no closed form!

Jaap Spies