1
$\begingroup$

Prove that $n(n+1)$ is even using induction

The base case of $n=1$ gives us $2$ which is even.

Assuming $n=k$ is true,

$n=(k+1)$ gives us $ k^2 +2k +k +2$

while $k(k+1) + (k+1)$ gives us $k^2+2k+1.$

whats is the next step to prove this by induction? I can't seem to show

$ k^2 +2k +k +2$ = $k^2+2k+1$

$\endgroup$
  • 1
    $\begingroup$ $n(n+1) = n(n-1)+2n$. By induction, $n(n-1)$ is even. Adding another even number $2n$ gives another even number. $\endgroup$ – angryavian Nov 27 '15 at 3:19
  • $\begingroup$ $k(k+1) = k^2 + k$ and $(k+1)(k+2) = k^2 + 3k + 2= k^2 + k + (2k+2) = k(k+1) + 2(k+1)$. "while k(k+1)+(k+1) gives us..." where did k(k+1)+ (k+1) (which is $(k+1)^2$) come from? $\endgroup$ – fleablood Dec 11 '17 at 17:01
2
$\begingroup$

Hint: $$(n+1)((n+1)+1)=(n+1)(n+2)=n(n+1)+2(n+1)$$

$\endgroup$
1
$\begingroup$

What you wrote in the second line is incorrect.

To show that $n(n+1)$ is even for all nonnegative integers $n$ by mathematical induction, you want to show that following:

Step 1. Show that for $n=0$, $n(n+1)$ is even;

Step 2. Assuming that for $n=k$, $n(n+1)$ is even, show that $n(n+1)$ is even for $n=k+1$.


[Added:] In Step 2, what you really need to show is the following implication:

if $k(k+1)$ is even, then $(k+1)(k+2)$ is even.

$\endgroup$
  • $\begingroup$ I see, so simply show that n=k+1 is even? $\endgroup$ – Noah Deng Nov 27 '15 at 3:22
  • $\begingroup$ Exactly because that would show $n=1$ is also even, which would show $n=2$ is also even, which would show $n=3$ is also even,.... $\endgroup$ – Ahmed S. Attaalla Nov 27 '15 at 3:23
  • 2
    $\begingroup$ Well, it is not that "$n=k+1$ is even", but that "when $n=k+1$, $n(n+1)$ is even". $\endgroup$ – Jack Nov 27 '15 at 3:23
  • $\begingroup$ I've ended up with $k^2 +k +2(k+1)$, we know that 2(k+1) is even, however it is ok to simply assume $k^2 +k$ is also even? $\endgroup$ – Noah Deng Nov 27 '15 at 3:29
  • $\begingroup$ (use your inductive hypothesis) $\endgroup$ – Morgan Rodgers Nov 27 '15 at 7:38
0
$\begingroup$

From $k^2$ + $3k$ + 2, you could do cases for k.

Case 1: If k is even, then let k = 2c for some integer c. Then you get $(2c)^2 $+ $3(2c)$ +2 , which could be written as 2(2cc) + 2(3c) +2 or 2(2cc + 3c + 1), which is even.

Case 2: If k is odd, then let k = 2c+1 for some integer c. Then you get $(2c+1)^2 $+ $3(2c+1)$ +2 , which could be written as $4c^2$ + $4c$ + 1 + $2c$+ + 1 + 2 , where you can simplify the expression down to 2 ($2c^2$ + $3c$ + 2). The factored out 2 indicates that it is even.

$\endgroup$
  • $\begingroup$ To finish of the proof, you would say that since n=1 makes n(n+1) even and since n=k+1 makes the expression n(n+1) even, then by the principle of induction, for all n greater than equal to 1, n(n+1) is even. $\endgroup$ – sdggsgehse Nov 27 '15 at 3:53
  • $\begingroup$ A proof by cases applied to $n(n+1)$ is essentially the best proof all by itself. Your answer tacks on induction only because the OP was required to use induction. (I disapprove of questions that force you to use an inappropriate technique just to practice the technique.) $\endgroup$ – Ethan Bolker Dec 11 '17 at 17:00
0
$\begingroup$

Claim:

P(n): n(n+1) is even $\forall n \in \mathbb{N}$

Base case:

P(0): 0(1) = 0. Since 0 can be written in the form 2t, t $\in \mathbb{Z}$, 0 is even. The base case holds.

Alternative base case if you want to start at 1:

P(1): 1(2) = 2. Since 2 can be written in the form 2t, t $\in \mathbb{Z}$, 0 is even. The base case holds.

inductive hypothesis:

Suppose P(n) is true for some k $\in \mathbb{N}$. That is k(k+1) is even. Or $k^{2} + k$ is even.

inductive step:

P(k+1): $$(k+1)((k+1)+1) = (k+1)(k+2) $$ $$= k^{2} + 2k + k + 2$$ $$= (k^{2} + k) + (2k+2)$$ $$= (k^{2} + k) + 2(k+1) $$

By IH $k^{2} + k$ is even and since 2(k+1) is even by definition then P(k+1) is even. By principle of induction P(n) holds $\forall n \in \mathbb{N}$.

Note that it may require proof that even + even = even. Very simple proof however.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.