Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm learning about proof by contrapositive and by mathematical induction in a computer science class. I'm banging my head trying to solve this problem and would like some help:

Prove that the sum of the first $n$ even numbers is $n^2 + n$
(a) indirectly by assuming that the sum of the first $n$ odd numbers is $n^2$
(b) directly by mathematical induction.

I have no problem doing (b). But I can't figure out how to do (a) using indirect proof. I can only come up with this:

Sum of first $n$ numbers is $n^2 + n \implies $ numbers are even

Contrapositive: numbers are odd $\implies $ sum of first n numbers is not $n^2 + n$.

This just doesn't seem logical to me. Any hints would be greatly appreciated.

share|improve this question
1  
The picture here may give you some ideas. –  Larry Wang Sep 21 '10 at 0:46

2 Answers 2

up vote 3 down vote accepted

Using the contrapositive isn't the only indirect way of proving a theorem, and I highly doubt it's what your instructors had in mind here. As a hint for part (a): what can you say about the first $n$ even numbers (individually) compared to the first $n$ odd numbers? Can you find some convenient correspondence between, say, the 5th even number and the 5th odd number?

share|improve this answer
    
I've figured out the correspondence: even numbers are 2*i (i=1..n) and odd numbers are 2*i-1(i=1..n). By assuming that the sum of the first n odd numbers is n^2, I was able to conclude that the sum of the first n even numbers is n^2 + n. But I still don't have a proof that the sum of the first n odd numbers is n^2 (without having to resort to induction, that is). It's not clear from the problem statement that I should accept the odd numbers -> n^2 as fact. –  Anonymous Sep 21 '10 at 0:45
    
...but induction is the most elementary way of going about it, Ignorunt. –  J. M. Sep 21 '10 at 0:47
3  
Ignorunt: The statement that you have to accept the sum-of-odd formula as fact is, I suspect, precisely why your instructors called the proof in (a) indirect: because you're proving it from a separate (and by hypothesis already-proved) statement. In effect you're proving the statement 'If the sum of the first n odd numbers is n^2, the sum of the first n even numbers is n^2+n' and then using that, plus the (provided) statement 'The sum of the first n odd numbers is n^2' to derive your conclusion by what's generally called Modus Ponens in logic. –  Steven Stadnicki Sep 21 '10 at 0:52
    
Thanks. I get it now. The problem came from a textbook, but the instructor said to solve it by both induction and contraposition. I think the instructor hasn't yet tried to solve it him/herself. –  Anonymous Sep 21 '10 at 1:03

grid

This diagram should help you see the proper approach to proving this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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