# How to “Prove” this summation result?

I have this messy function with $n$, $k$, $i$ integers:

$$r(\rm n,k)=\frac{k 2^{1-2 \rm{n}} (2 k)! (-2 k+2 \rm{n}+1) (2 \rm{n}-2 k)!}{(k!)^2 \left(1-4 (i-k)^2\right) ((\rm{n}-k)!)^2}$$

I want to show that if I sum it, letting $i$ take values between $1$ and $\rm n$,

$$\sum_{k=1}^{\rm n} r(\rm n,k) = 1$$

When Mathematica takes a run at it, I have to relax the assumption that $i>0$ due to the $\Gamma(1-i)$ term in the denominator causing it to burp. Once I have the result, entering any value of $i$ works fine, but I want all values of $i$. Here's the solution of the sum... $$\sum_{k=1}^{n}r(n,k)=\frac{(2i-n-1)\Gamma\left(\frac{1}{2}-i\right)(n-i)!} {2 \Gamma(1-i)\Gamma\left(-i+n+\frac{3}{2}\right)}+1$$

Any thoughts on how to close the deal? Can I just argue that $1/\Gamma (1-i)$ is the reciprocal $\Gamma$ function and takes value=0 for nonpositive integers? I'm a little wary...

Here is the code to run...

rnk = (2^(1 - 2*nn)*k*(1 - 2*k + 2*nn)*(2*k)!*(-2*k + 2*nn)!)/
((1 - 4*(i - k)^2)*k!^2*(-k + nn)!^2)

FullSimplify[Sum[rnk, {k, 1, nn}], {Element[k , Integers], Element[nn , Integers]}]


As an oh-by-the-way, the function $r(n,k)$ can equivalently be written (and this was my actual starting point) as

$$r(n,k) =\frac{1}{1-4 (i-k)^2} \frac{(2 k-1)\text{!!} (2n-2 k+1)\text{!!}}{(2 k-2)\text{!!} (2 n-2 k)\text{!!}}$$ Mathematica couldn't work this form, though. Had to be converted to single factorials.

* EDIT *

Maybe I am done? This gives me the answer I'd like. wrap a Limit[ ] function in assumptions where I just assume the limit point $i\to \rm{i0}$ is a positive Integer:

Assuming[{Element[i0,Integers], i0 > 0}, Limit[Sum[rnk, {k, 1, nn}], i -> i0]]


This comes out as desired ( = 1).

• Where is the definition of fs? – JimB Mar 13 '17 at 20:18
• Fixed, should be the messy expression in the sum. – MikeY Mar 13 '17 at 20:25
• MikeY, I do not think you are done! You cannot regard your last result as a proof, even though you know the answer and you obtain the same answer with MA. Even machine generated proofs need to be independently verified. Read about the history of 4-color theorem www-groups.dcs.st-and.ac.uk/history/HistTopics/…. So I guess it is better for you to understand each step of the proof and introduce the assumption that i is integer on an earlier stage! – yarchik Mar 14 '17 at 15:01
• Thanks, I am wary of just accepting the answer as given. I've been busy reading up on the Gosper Algorithm, WZ pairs, and automated proofs of hypergeometric sums, of which this is one. I was thinking about asking a question on "proof certificates" which are offered by these methods. Still getting smart. – MikeY Mar 14 '17 at 22:24

The quickest route is to use the reflection formula for the gamma function for one of the factors in the denominator of your prospective solution:

Assuming[i ∈ Integers && nn ∈ Integers && 1 <= i <= nn,
FullSimplify[1 + ((2 i - nn - 1) Gamma[1/2 - i] (nn - i)!)/
(2 (π Csc[π i]/Gamma[i]) Gamma[3/2 - i + nn])]]
1

• Thanks, JM...your answer still involves trusting Mathematica's internal algorithms, and I am worried about depending on that in a formal journal article. Trust but verify? – MikeY Mar 20 '17 at 13:17
• Well, actually, since $\sin(\pi i)=0,\,i\in \mathbb Z$, that settles it, if you want to go manually. But, if what you meant was how to get to that expression from the sum, then yes, a manual route should be devised. – J. M. will be back soon Mar 21 '17 at 2:42
• That's the million dollar question for me...when do I accept Mathematica's output, and when (and how) do I verify it? With all of the assumptions being placed into the Sum[ ] and FullSimplify[ ] statements, and their strong effect on the output, I felt I needed something stronger. This appears to be a deep, running issue in the math world - rightly so. – MikeY Mar 21 '17 at 16:18

Edited to show problem completion...

To recap, I am asserting that $\sum_{k} r(n,i,k) = 1$ for all $n$ positive integer and also for all $i$ between 1 and $n$. I made the $i$ explicit here.

Solution approach is induction on both $n$ and $i$, in that order. Induce on $n$ first. Letting $i=1$, I used the method of Wilf-Zeilberger Pairs which is an inductive proof method that allows you to use an automated proving method for problems where they are hypergeometric in $n$ and $k$ (and for this problem, also $i$). (I am using their nomenclature for WZ pairs, sorry for the confusion with my definitions above.) Start with the summand after fully simplifying using Mathematica, $$F(n,k)=-\frac{\Gamma \left(k-\frac{3}{2}\right) \Gamma \left(-k+\text{nn}+\frac{3}{2}\right)}{\pi \Gamma (k) \Gamma (-k+\text{nn}+1)}$$ and came up with a proof certificate of

$$R(n,k)=\frac{-2 k^2+2 k \text{n}+5 k-2 \text{n}-3}{2 \text{n} (k-\text{n}-1)}$$ and a function $G(n,k)$ that is defined as $$G(n,k) = R(N,k) F(n,k-1) = \frac{\Gamma \left(k-\frac{3}{2}\right) \Gamma \left(-k+\text{nn}+\frac{5}{2}\right)}{\pi \text{nn} \Gamma (k-1) \Gamma (-k+\text{nn}+2)}$$ Then checking that $$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$ and $$\lim_{k \to +/- \infty} G(n,k)=0$$ This takes a few seconds to run, and I've also run it for $i=n$ and for the midpoint $i=(n+1)/2$ and for lots of values of $i=1,2,3,...n-3,n-2,n-1$ and it works fine. However, when I try to run it for the generic $i$, I get a messy expression.

So the second induction step, on $i$, remains unfinished.

EDIT

Using the fastZeil.m package from Peter Paule, Markus Schorn and Axel Riese, and their implementation of the Zeilberger Algorithm, and defining

$$\sum_{k} r(k,n,i) = \sum_{k} F(k,i) = \text{SUM[i]}$$ was able to show the recurrence

$$(-4 i^2+4 i n-4 i+3 n-3) \text{SUM[i+1]}+i (2 i-2 n-1) \text{SUM[i]}+(2 i+3) (i-n+1) \text{SUM[i+2]}==0$$ with the proof certificate $$R(k,i)=\frac{4 (k-1) (-2 i+2 k+1) (-2 k+2 \text{n}+3)}{(-2 i+2 k-5) (-2 i+2 k-3)}.$$ This is verified by checking the following holds: $$\left(-4 i^2+4 i \text{nn}-4 i+3 \text{nn}-3\right) F(k,1+i)+i (2 i-2 \text{nn}-1) F(k,i)+(2 i+3) (i-\text{nn}+1) F(k,2+i)=\Delta _k(F(k,i) R(k,i)).$$ Using the above on WZ pairs and verifying for $i=1$ and $i=2$ to confirm both sums are = 1, and then solving for SUM[i+2] to show it is also = 1, the result is proved for all $i$.