2
$\begingroup$

Can anyone give a reference, a proof, or a reference that explains why Maple can evaluate this identity mathematically correctly:

$$n-i-1=(d-1)\sum_{l=1}^{n-i-1}\frac{\binom{n-i-1}{l}}{\binom{n-i+d-3}{l}}$$

$\endgroup$
6
  • 2
    $\begingroup$ I recommend rewriting your question so that it makes more sense. Writing t for n-i-1 would be a good start, as well as asking what you really want, rather than a reference to why Maple does things correctly. Gerhard "Ask Me About System Design" Paseman, 2011.11.30 $\endgroup$ Commented Nov 30, 2011 at 16:50
  • $\begingroup$ I don't get your question: do you mean that you are surprised that Maple can do something correctly? Or, rather than why, are you asking how does Maple derive the identity. $$ $$ Anyway, the question is not clear as is, it needs motivation. See: mathoverflow.net/howtoask $\endgroup$ Commented Nov 30, 2011 at 17:20
  • $\begingroup$ A possible explanation, a bit tautological: Maple is able to make a number of formal simplifications on expressions like yours, so as to reduce them to some of the thousands of standard identities that it contains in its memory. $\endgroup$ Commented Nov 30, 2011 at 17:25
  • 1
    $\begingroup$ You can get Maple to show the steps it is taking . That may or may not give a satisfying result (if that is what you really want to know). Improve your notation and try the cases $d=1,2,3,4$ to get some insight. $\endgroup$ Commented Nov 30, 2011 at 17:52
  • $\begingroup$ I am curious about why anyone would down vote this?! It is a perfectly reasonable question. $\endgroup$
    – Igor Rivin
    Commented Nov 30, 2011 at 19:14

2 Answers 2

3
$\begingroup$

The canonical reference for this sort of thing is Petkovsek and Zeilberger's book "A=B". Maple (almost certainly) uses the Zeilberger-Wilf algorithm for hypergeometric summation (which really goes back to Bill Gosper). You can also read the Wilf-Zeilberger paper (Inventiones, around 1990).

$\endgroup$
0
$\begingroup$

As Gerhard Paseman suggested, it look better to replace $m=n-i-1$ and also $x=d-2$. With this the question takes the form $S:=\sum_{\ell=1}^m\binom{m}{\ell}\binom{m+x}{\ell}^{-1}\frac{x+1}m$ and we show $S\equiv1$. Let $$F(m,\ell):=\binom{m}{\ell}\binom{m+x}{\ell}^{-1}\frac{x+1}m \qquad \text{and} \qquad G(m,\ell):=-\binom{m}{\ell}\binom{m+x+1}{\ell}^{-1}\frac{m+x+1}m.$$ It's easy to check $$F(m,\ell)=G(m,\ell+1)-G(m,\ell), \tag1$$ say by dividing through with $F(m,\ell)$ and simplifying. Summing (1) over integers $\ell\geq0$ gives $$\sum_{\ell=0}^mF(m,\ell) =\sum_{\ell\geq0}G(m,\ell+1)-\sum_{\ell\geq0}G(m,\ell)=-G(m,0)=\frac{x+m+1}m.$$ Therefore, we arrive at $$S=\sum_{\ell=1}^mF(m,\ell)=\sum_{\ell=0}^mF(m,\ell)-F(m,0)=\frac{x+m+1}m-\frac{x+1}m=1$$ which is what aimed for.

$\endgroup$

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.