Combinatorics

Date: 08/19/97 at 04:48:09
From: ARIN CHAUDHURI
Subject: Combinatorics

sum((-1)^k*((4n choose 2k)/(2n choose k)) for k = 1 to 2n

Date: 08/25/97 at 16:49:58
From: Doctor Rob
Subject: Re: Combinatorics

The key to summing formulae of this kind is to find a recursion
that the summand satisfies. Call the summand f[n,k].  Call the
sum F[n] = Sum f[n,k] over 0 <= k <= 2*n. Then you can find values
of a, b, c, d, e, and g independent of k such that the relation

   a*f[n,k] + b*f[n,k+1] + c*f[n,k+2] + d*f[n+1,k] + e*f[n+1,k+1] +
      g*f[n+1,k+2] = 0

holds whenever k >= 0.  The spans 1 on n and 2 on k were found by
trial-and-error.  In this case,

  a = -(4*n+3)*(4*n+1)/[8*n*(2*n+1)],  (n nonzero)
  b = -2*a,
  c = a,
  d = 0,
  e = 0,
  g = 1.

Summing this from k = 0 to 2*n-2, you get

  a*(F[n]-f[n,2*n-1]-f[n,2*n]) +
     b*(F[n]-f[n,0]-f[n,2*n]) +
     c*(F[n]-f[n,0]-f[n,1]) +
     (F[n+1]-f[n+1,0]-f[n+1,1]-f[n+1,2*n+1]-f[n+1,2*n+2]) = 0,
  a*(F[n]-[1-4*n]-1) - 2*a*(F[n]-1-1) + a*(F[n]-1-[1-4*n]) +
     (F[n+1]-1-[-3-4*n]-[-3-4*n]-1) = 0,
  a*(F[n]+4*n-2) - 2*a*(F[n]-2) + a*(F[n]+4*n-2) + (F[n+1]+8*n+4) = 0,
  8*n*a + F[n+1] + 8*n + 4 = 0
  F[n+1] = -1/(2*n+1).

Thus F[n] = -1/(2*n-1).

Your sum is almost this, but you leave off the term k = 0, the value 
of which is 1, so your answer is

   F[n] - f[n,0] = F[n] - 1 = -2*n/(2*n-1).

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/