Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/

Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search