2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Where is the definition of fs? $\endgroup$ – JimB Mar 13 '17 at 20:18
  • $\begingroup$ Fixed, should be the messy expression in the sum. $\endgroup$ – MikeY Mar 13 '17 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 Mar 14 '17 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 Mar 14 '17 at 22:24
2
$\begingroup$

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
$\endgroup$
  • $\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 Mar 20 '17 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$ – J. M. will be back soon Mar 21 '17 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 Mar 21 '17 at 16:18
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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