CombinatoricsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/