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).

  • $\begingroup$ Where is the definition of fs? $\endgroup$
    – JimB
    Commented Mar 13, 2017 at 20:18
  • $\begingroup$ Fixed, should be the messy expression in the sum. $\endgroup$
    – MikeY
    Commented Mar 13, 2017 at 20:25
  • 1
    $\begingroup$ 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! $\endgroup$
    – yarchik
    Commented Mar 14, 2017 at 15:01
  • $\begingroup$ 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. $\endgroup$
    – MikeY
    Commented Mar 14, 2017 at 22:24

2 Answers 2


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])]]
  • $\begingroup$ 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? $\endgroup$
    – MikeY
    Commented Mar 20, 2017 at 13:17
  • $\begingroup$ 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. $\endgroup$ Commented Mar 21, 2017 at 2:42
  • $\begingroup$ 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. $\endgroup$
    – MikeY
    Commented Mar 21, 2017 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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.