3

So I am looking at some induction questions and I am trying to solve them on my own but I am getting stumped and frustrated. There was a previous question question that was answered, but I changed it to see if I could solve it. I am not getting that far.

How do I show by mathematical induction that $2$ divides $n^2+n$ for all $n$ belonging to the set of Natural Numbers. Here is what I have so far. Could I be pointed in the right direction? You can see below where I am stumped. This is where I am having the issue.

Basis: $n=1, \qquad P(1)$ is true, 2 divides $1^2+1 = 2$

Induction Hypothesis: 2 divides $(k+1)^2+(k+1)$ for some $k \in \mathbb{Z} \geq 1$

Induction Step: $(k+1)^2+(k+1)=k^3+3k^2+3k+1=$

Community
  • 1
CS Studentzzz
  • 97

2 Answers2

2

Alright, so our inductive hypothesis is that $k^2 + k$ is a multiple of $2$ for some $k$. Then consider $(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = (k^2 + k) + 2k + 2 = (k^2 + k) + 2(k + 1)$.

By our inductive hypothesis, $k^2 + k$ was an even number: because we are adding an even number, $2(k+1)$, to it, we still have an even number.

Therefore, $(k+1)^2 + (k+1)$ must be even as well. This completes our proof.

Ashkay
  • 1,821
  • However, a much easier way is that because for any integer $n$, either $n$ or $n+1$ is even, we must have $n(n+1)$ be even. :) – Ashkay Jun 15 '15 at 17:53
  • i do not understand this at all, it seems so easy. I feel like i am missing a step. – CS Studentzzz Jun 15 '15 at 18:02
  • how can any integer be even? if $n=2$ then $n+1=3$ right? – CS Studentzzz Jun 15 '15 at 18:10
  • This problem is indeed a rather basic induction exercise. We simply show that by adding an even number to an even number, we get another even number. My first comment shows the simplest way to prove that $n(n+1)$ is even. – Ashkay Jun 15 '15 at 18:11
  • It is very basic, but i am very new to this. So i = basic. :) – CS Studentzzz Jun 15 '15 at 18:11
  • @Jkoz, if $n$ is even, then $n+1$ is odd. If $n$ is odd, then $n+1$ is even. Because one of $n$ and $n+1$ is always even, we must have $n(n+1)$ be even as well. This isn't an inductive proof, but it is extremely simple. – Ashkay Jun 15 '15 at 18:12
  • No worries! Induction is rather hard to grasp the first time - after a couple more practice problems, you'll definitely get the hang of it. – Ashkay Jun 15 '15 at 18:12
  • Pardon my ignorance, but your first answer you gave me, is this an example on where i need to go with this or is it done? – CS Studentzzz Jun 15 '15 at 18:13
  • The initial answer I gave to this question shows how the inductive step would go. Combined with your base case, this completes the proof. We assumed that $k^2 + k$ was even, and showed that $(k+1)^2 + (k+1)$ was even as well. Therefore, if this fact works for one number, then it works for the next number. Because your base case shows that $1^2 + 1$ is even, it follows that $2^2 + 2$ is even by the inductive step. Then, it follows from this that $3^2 + 3$ is even, and so on. Because we proved the base case and this inductive step, we have shown it works for all possible values of $n$. – Ashkay Jun 15 '15 at 18:16
  • ok now i am understanding this. Kinda, i will get it though. – CS Studentzzz Jun 15 '15 at 18:17
0

Maybe we can say in Induction Step: k(k+1) whereas k(k+1) is an even number so any even number is divisible by 2 .

asrar aljohiny
  • 1