From: "J.P. Grossman" <jpg@alum.mit.edu> To: wclark@mail.usf.edu, math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] A sum

--JP Grossman's proof makes it clear that the sum 4^(-k) * sum( (-1)^j * (D+1+2*k-2*j)^(2*k+1) * (D+k-j)! / ((k-j)! * j! * (2*k+1+D-j)!), j, 0, k ) = 1 is just a (heavily disguised) result of the fact that the Qth difference of a polynomial of degree <= Q, is a constant, and specifically, the Qth difference of x^Q is Q!. (I'd actually had that idea myself, but managed to confuse myself & fail...) I'm also interested in the same sum, except with the (-1)^j sign factor removed. For that I do not know the answer, albeit when D is large with k fixed it appears the answer is asymptotic to (D/2)^k / k!. I'll show this [to within a polynomial(k) factor] below. Trying to generalize still further we could consider the sum with the (-1)^j replaced by s^j. Then for Grossman's approach, we can start with the generalized lemma that sum( (n choose j) * s^j * j^m, j,0,n ) is what you get by applying the operator s*(d/ds) m consecutive times to sum( (n choose j) * s^j, j,0,n ) = (1+s)^n.

Lemma:

sum_{j = 0..n} ( (n choose j) (-1)^j j^m ) = 0 for m < n = (-1)^n n! for m = n

Proof: Take the m^th derivative of (1-x)^n, set x = 1, and use induction.

Corollary: Let p(j) be a polynomial of degree n with leading coefficient C. Then sum_{j = 0..n} ( (n choose j) (-1)^j p(j) ) = C * (-1)^n * n!

Proceeding onward, Grossman's main proof transmogrifies thus: Main proof: Let n = 2k+1+D, and rewrite 4^k*2*n!*(sum at top) as sum_{j = 0..k} ( (n choose j) s^j (D+k-j)!/(k-j)! (n - 2j)^(2k+1) ) = D! * sum_{j = 0..k} ( (n choose j) s^j (D+k-j choose k-j) (n - 2j)^(2k+1) ) = D! * sum_{j = 0..n} ( (n choose j) s^j (D+k-j choose k-j) (n - 2j)^(2k+1) ) = D! * sum_{j = 0..n} ( (n choose j) s^j (n-k-1-j choose k-j) (n - 2j)^(2k+1) ) = at which point the stuff to the right of the s^j is a polynomial in j of degree n. If s = -1 then that is nicely handled via lemma, but for any other value of s, it's kind of a mess trying to apply the generalized lemma. But if 0<=s, and D,n are huge with k>0 fixed, then plainly the summand is positive and increases then decreases with max occurring approximately when the ratio of successive terms is 1, i.e. when j[max] = (2sk+s-1) / (2s+2) when s=1 this is just j[max] = k/2. In the s=1 case if we approximate the sum by its largest term, then, in the limit D,n large, k fixed, we get D! * (n choose k/2) * (D+k/2 choose k/2) * (D+3k/2)^(2k+1) which for the sum up top simplifies in this limit to (1/2) * (D/4)^k / (k/2)!^2. This is indeed about (D/2)^k / k! if we ignore factors of order sqrt(k).

Observe that the summand is zero if we take j = k+1, k+2, ..., k+D, and it is unchanged by the substitution j := 2k+1+D-j, so we can extend the sum up to n and the equation becomes

sum_{j = 0..n} ( (n choose j) (-1)^j (D+k-j)!/(k-j)! (n - 2j)^(2k+1) ) = 2^(2k+1) n!

But (D+k-j)!/(k-j)! (n - 2j)^(2k+1) is a polynomial in j of degree n with leading coefficient (-1)^n 2^(2k+1), so by the corollary the sum is equal to

(-1)^n * 2^(2k+1) * (-1)^n * n! = 2^(2k+1) n!

as required.

J.P.