Message Boards Message Boards

0
|
4110 Views
|
6 Replies
|
0 Total Likes
View groups...
Share
Share this post:
GROUPS:

Reduce, FindInstance and ReplaceAll give wrong answers on Vandermonde's id.

Posted 10 years ago
All of the following outputs are wrong (in Mathematica 8.0), except for the last one where I plug in concrete values. Can anyone explain this to me? I consider this a rather serious issue because most people would probably rely on the output of Mathematica in any of the three cases when it comes to such an easy and well known identity (which is obviously not true for all integers).

 In[6631]:= Reduce[Sum[Binomial[n, k] Binomial[s, t + k], {k, 0, n}] == Binomial[n + s, n + t], {n, s, t}, Integers]
 
 Out[6631]=
 n \[Element] Integers && s \[Element] Integers && t \[Element] Integers
 
 In[6622]:= FindInstance[Sum[Binomial[n, k] Binomial[s, t + k], {k, 0, n}] != Binomial[n + s, n + t], {n, s, t}, Integers]
 
 Out[6622]= {}
 
In[6632]:= ReplaceAll[Sum[Binomial[n, k] Binomial[s, t + k], {k, 0, n}] == Binomial[n + s, n + t], {n -> 1, s -> -1, t -> -1}]

Out[6632]= True

In[6623]:= n = 1;
s = -1;
t = -1;
Sum[Binomial[n, k] Binomial[s, t + k], {k, 0, n}]
Binomial[n + s, n + t]

Out[6626]= 2

Out[6627]= 1
POSTED BY: Mario Weitzer
6 Replies
Yes, what I meant is that Mathematica commands generally evaluate their arguments first, so since Sum evaluates, the three statements actually are 
Reduce[Binomial[n + s, n + t] == Binomial[n + s, n + t], {n, s, t}, Integers]

FindInstance[
Binomial[n + s, n + t] != Binomial[n + s, n + t], {n, s, t}, Integers]

ReplaceAll[Binomial[n + s, n + t] == Binomial[n + s, n + t], {n -> 1, s -> -1, t -> -1}]
and the answers are then less surprising. That aside, I agree with your point, i.e. Sum possibly should not return an unconditional result in this case.
POSTED BY: Ilian Gachevski
Posted 10 years ago
Yes, you are right, this is most probably the issue.
POSTED BY: Mario Weitzer
I suppose the question isn't really about FindInstance, Reduce or ReplaceAll. They all do what is expected given what Sum evaluates to: 
In[5]:= Sum[Binomial[n, k] Binomial[s, t + k], {k, 0, n}]

Out[5]= Binomial[n + s, n + t]
POSTED BY: Ilian Gachevski
Posted 10 years ago
It does so in general but not for all integers n, s and t. The first point under More Information in the documentation of Reduce says:
"The result of Reduce[expr,vars] always describes exactly the same mathematical set as expr. "
This is not true for this example.
In Applications of the documentation of FindInstance it says:
"Prove that a statement is a tautology:"
As I said: If FindInstance returns the empty set it allegedly means that Mathematica has been able to prove that no instance exists (in the given domain). But such a prove can not exist for all integers, as there is a counterexample which FindInstance should find (or at least it should not claim that there is none).
And for ReplaceAll: The third command tells Mathematica to replace all instances of n by 1 and all of s and t by -1. If you do so the correct output would be False, as this replacement ist exactly the one which is used in the counterexample. But it yields True (probably because it does some incorrect simplification prior to the replacing)
POSTED BY: Mario Weitzer
Posted 10 years ago
Considering the counterexample given in the last input, not those Mathematica gives. The correct output of Reduce would be somewhere in between

n \ Integers && s \ Integers && t \ Integers && n >= 0 && s >= 0 && t >= 0
and
n \ Integers && s \ Integers && t \ Integers (the one Mathematica gives)

FindInstance should find a counterexample like the one given in the last input (as - according to the documentation of FindInstance - an output of the empty set means that Mathematica was able to prove that no instance exists). And ReplaceAll should yield False, as the replacements are the same as in the counterexample.
POSTED BY: Mario Weitzer
What outputs were you expecting?
POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract