Thursday, April 11, 2019

Proof by Induction $n^2+n$ is even



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!


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...