5
$\begingroup$

I'm not entirely sure if I'm going about proving $n^2+n$ is even for all the natural numbers correctly.

$P(n): = n^2+n$

$P(1) = 1^2+1 = 2 = 0$ (mod $2$), true for $P(1)$

Inductive step for $P(n+1)$:

$\begin{align}P(n+1) &=& (n+1)^2+(n+1)\\ &=&n^2+2n+1+n+1\\ &=&n^2+n+2(n+1)\end{align}$

Does this prove $n^2+n$ is even as it's divisible by $2$? Thanks!

  • 0
    $n^2+n \equiv 0 \pmod2$ by Fermat's little theorem.2012-07-18

4 Answers 4

12

I see other answers provide different (possibly simpler) proofs. To finish off your proof:

by the induction hypothesis $n^2+n$ is even. Hence $n^2 + n = 2k$ for some integer $k.$ We have $n^2+n+2(n+1) = 2k + 2(n+1) = 2(k+n+1) = 2\times\text{an integer} = \text{even}.$

Does this prove $n^2+n$ is even as it's divisible by $2$?

The key here is to remember stating & using the induction hypothesis.

  • 1
    It's worth noting that it should be $n+1$ in the parentheses, not $n+2$. The OP made an arithmetic error.2012-07-18
9

Or this....

$n^2 + n = n(n+1).$ One of $n$ or $n+1$ is even so the product is even.

4

You could also note the following:

The product of two odd numbers is odd, the product of two even numbers is even.

The sum of two even numbers is even, the sum of two odd numbers is even.

If $n$ is odd, then $n^2$ is odd, and $n^2+n$ is even. If $n$ is even, then $n^2$ is even, and $n^2+n$ is even.

No need for induction.

2

Yes, you could then say $n^2+n$ is even implies $(n+1)^2+(n+1)$ is even due to the factor $2$ in the last line. A nice writeup of how to think about induction and how to write a proof is given in this response by Arturo Magidin