For every integer $n$, the quantity $n^2 + 2n \equiv 0\pmod 4$ or $n^2 + 2n \equiv 3\pmod 4$

Question

I'm trying to prove this question using induction

So far I have

Base Case

Let $n = 1$, $(1^2 + 2)\equiv 3 \pmod 4 $

Claim holds for base case

Induction

Assume $n = k$ holds, that is $k^2 + 2k \equiv 0\pmod 4$ or $k^2 + 2k \equiv 3\pmod 4$

Let $n = k+1$ such that

$${(k+1)^2 + 2(k+1)}\equiv {k^2 + 2k + 1 + 2k + 2}\pmod 4$$

Then I substitute $k^2 + 2k$ with both $0$ or $3$ from the earlier assumption.

So we have

$$(0 + 2k + 3) \equiv (2k + 3) \pmod 4$$ Or, $$(3 + 2k + 3) \equiv (2k + 6) \pmod 4$$

Where do I go from here?

Answer 1

Separate cases for $n$ even and $n$ odd.

If $n$ is even, than it is $n=2m$.

We get: $(2m)^2+2(2m)=4m^2+4m=4(m^2+m)\equiv 0\mod 4$

If $n$ is odd, then it is $n=2m+1$.

We get: $(2m+1)^2+2(2m+1)=4m^2+4m+1+4m+2=4(m^2+2m)+3\equiv 3\mod 4$

Answer 2

From where you are stuck, we can do the following case distinction:

Case 1: $k^2+2k \equiv 0 \mod 4$. Notice that in this case $k$ cannot be an odd number. And any even $k$ satisfies this (can be proven by induction). Therefore $k = 2m$ for some integer $m$. Then, $$2k+3 = 4m+3 \equiv3 \mod 4$$

Case 2: $k^2+2k \equiv 3 \mod 4$. Notice that in this case $k$ cannot be an even number. And any odd $k$ satisfies this (can be proven by induction). Therefore $k = 2m+1$ for some integer $m$. Then, $$2k+6 = 4m+9 \equiv1 \mod 4$$

But instead of doing this, Cornman's answer is shorter and better since we are doing the case distinction anyway so why would we have to do an additional induction when a case distinction itself can be done for proving? I'm posting this just to complete your solution. So I refer to Cornman's answer.

Answer 3

You only need one equation.

$\begin{array}\\ (n+2)^2+2(n+2) -(n^2+2n) &=n^2+4n+4+2n+4 -(n^2+2n)\\ &=4n+8\\ \end{array} $

which is divisible by $4$, so whatever remainder $n$ has mod 4, $n+2$ also has.

Since $n=0 \implies n^2+2n = 0$, all even numbers have a remainder of 0 mod 4.

Since $n=1 \implies n^2+2n = 3$, all odd numbers have a remainder of 3 mod 4.

Answer 4

$$n^2+2n=(n+1)^2-1$$

Now $n+1\equiv0,\pm1,2\pmod4$

$\implies(n+1)^2\equiv0,1\pmod4$

$(n+1)^2-1\equiv?,?$