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