2
$\begingroup$

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.

  • 1
    The picture [here](http://math.stackexchange.com/questions/136/why-are-the-differences-between-consecutive-squares-equal-to-the-sequence-of-odd/183#183) may give you some ideas.2010-09-21

2 Answers 2

3

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?

  • 0
    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.2010-09-21
  • 0
    ...but induction is the most elementary way of going about it, Ignorunt.2010-09-21
  • 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.2010-09-21
  • 0
    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.2010-09-21
2

grid

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