I am currently finishing up my Discrete Math course, and I just wanted to clear something up that has confused me for the past few days. My teacher posts answer keys to assigned homework problems online, and one of his recent solutions to one of these problems confused me. The problem was "Prove the following used the method of contradiction: The sum of two consecutive integers is always odd."

I thought this proof would be a straightforward direct proof. So, the contradiction would be "The sum of two integers is always even." Sparing the rigorous details: an integer n added to another integer (n+1) leads to (2n+1), which contradicts the statement, since 2n+1 is the representation of an odd number.

My teacher, however, proved this with two cases. The first case: a direct proof, using my strategy above, for n + (n+1). The second case, basically a similar proof to the one in the first case but now using (n-1) + n. This second case is what has confused me. Isn't this step a bit redundant? Is it necessary? Does it enhance the proof, or just add superfluous information to it?

  • $\begingroup$ The negation of "the sum of two consecutive integers is always odd" is not "the sum of two [consecutive] integers is always even" but rather "there are two consecutive integers whose sum is even." $\endgroup$ – Andreas Blass Dec 13 '13 at 14:45
  • 2
    $\begingroup$ Notice also that the "proof by contradiction" aspect of your argument is a red herring. You showed that, for any two consecutive integers $n$ and $n+1$, the sum is $2n+1$, which is odd. So you proved the desired result directly. Adding "Suppose the result is false" at the beginning and adding "contradiction" at the end just makes it look more complicated than it is. $\endgroup$ – Andreas Blass Dec 13 '13 at 14:47

If you stick strictly with a direct proof (denoting two consecutive integers by $n$ and $n+1$, summing them to get $2n + 1$, therefore odd), you'll be fine.

  • For one thing, your assumed contradiction, the negation of "the sum of two consecutive numbers is always odd" is not correctly stated; its negation needs to be "it is not the case that that the sum of two consecutive numbers is always odd", which means, "there exists two consecutive integers whose sum is even."

  • Proof by contradiction here turns out to be much more work than simply using a direct proof.

Your teacher may have chosen to represent two cases, in the event some students designated the two consecutive integers as $(n - 1)$ and $n$, while others, like you, denoted these consecutive integers as $n$ and $(n+1).$

As you note, the proof proceeds the same, in either case, but given that your teacher was providing an answer key, he or she may have simply tried to cover all the bases: all the approaches students may have used.

But to answer your question, aside from this pedagogical concern your teacher may have had, the proof does not require a proof by cases. So I do not believe your teacher expected you or any other student to provide both cases. Doing so does not add any more information, is rather redundant, etc, save for the pedagogical concerns your teacher may have had.

  • $\begingroup$ But shouldn't the first statement of his proof,as noted by Andreas Blass,be 'Let there exist two consecutive integers whose sum is even'?Moreover,the question states that'. . .sum of two consecutive integers is always odd'.Therefore the negation should also include the possibility that the sum of 2 consecutive integers is sometumes even and sometimes odd.However,the OP's first statement goes as follows'sum of two integers is always even'.Isn't this wrong? $\endgroup$ – rah4927 Dec 13 '13 at 17:45
  • $\begingroup$ @rah4927 That's why I suggested leaving out the "contradiction" sentence. There's no need for a proof by contradiction. $\endgroup$ – amWhy Dec 13 '13 at 17:48
  • $\begingroup$ But the question stipulates using proof by contradiction.There does not seem to be any point in using contradiction,apart from the fact that it will teach the students about this method,and the negation of the statement is exactly where students will make a mistake. $\endgroup$ – rah4927 Dec 13 '13 at 17:51
  • $\begingroup$ @rah4927 Yes, I understand that. I edited to clarify exactly what the negation of the proposition looks like. As for the necessity of proof by contradiction: It seems that the teacher's answer key used a direct approach, so "proving by contradiction" seems not to have been a requirement. $\endgroup$ – amWhy Dec 13 '13 at 17:57

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.