4
$\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
    if it's divisible by 2, then its even.2012-07-18
  • 0
    Remember, a number $n$ is even if $n=2m$ for some $m \in \mathbb{Z}$2012-07-18
  • 3
    You know you don't need induction, do you?2012-07-18
  • 0
    You assume it is true for n and prove that your assumptions holds for n+1.2012-07-18
  • 0
    Yes, the proof is correct, though you might want to say explicitly how the indutive hypothesis is applied if you want to leave no doubt that you understand it (e.g. to convince a grader).2012-07-18
  • 1
    Since n$^2$+n factors to n(n+1) it is the product of consecutive integers so oen must be even. Since it has an even factor it is even. This does not require induction. The argument is independent of n. But if you want my argument above showed n$^2$+n is even then (n+1)$^2$ +n+1 = n$^2$ +2n+1+n+1= (n$^2$+n) +2n+2. This is the sum of 3 even numbers and is therefore even.2012-07-18
  • 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.

  • 4
    +1 It does seem OP wanted to use an inductive proof, even if there are other ways.2012-07-18
  • 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