# Indirect proof that sum of first n even numbers is $n^2 + n$

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.

-
The picture here may give you some ideas. – Larry Wang Sep 21 '10 at 0:46

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?

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

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

-