5
$\begingroup$

I'm supposed to prove this by induction, and I get that if I assume $n$ is odd such that $n^2$ gives a remainder of 1, then $n^2=4m+1$ for a number $m$ where $m \in \mathbb{Z}$, but I honestly can't get any further than that. Could someone complete the proof for me so that I can get a proper idea of how I can do this?

$\endgroup$
3
16
$\begingroup$

If you still want to use induction: let $P(n)$ be the statement $n^2 \equiv 1 \pmod 4$.

Consider $n=1$, $1^2 \equiv 1\pmod 4$, so $P(1)$ is true.

Assume $P(k)$ is true for some $k\in\mathbb Z$. $$k^2\equiv 1 \pmod 4$$

Consider $n = k+2$,

$$(k+2)^2 = k^2+4k+4 \equiv k^2\equiv1\pmod4$$

So $P(k+2)$ is true.


For negative odd $n$, $n^2 = (-n)^2 \equiv 1\pmod 4$.

$\endgroup$
2
  • $\begingroup$ First of all, this is the approach that I would've taken. However, aren't we supposed to prove that the statement holds for $n = k + 1$ and not $n = k + 2$? $\endgroup$ – Obinna Nwakwue Jun 4 '17 at 18:33
  • 7
    $\begingroup$ Oh, my bad, I realize now. $\endgroup$ – Obinna Nwakwue Jun 4 '17 at 18:35
14
$\begingroup$

Let $n=2k+1$ where $k\in [0,\infty) $ then $n^2=(2k+1)^2=4k^2+4k+1=4 (k^2+k)+1$ thats it.

$\endgroup$
3
  • 1
    $\begingroup$ "... by induction". -1. $\endgroup$ – Nij Jun 4 '17 at 20:17
  • 6
    $\begingroup$ @Nij Call the above "Proposition X". Then the following is a very legitimate proof by induction: (a) base step $n=1$ follows from Proposition X, (b) induction step follows from Proposition X, Q.E.D. That's not entirely serious, of course (though it is technically correct), but I don't see the point of your downvote. $\endgroup$ – dxiv Jun 5 '17 at 1:11
  • $\begingroup$ This is a much simpler solution than any induction proof but teachers gonna teach. $\endgroup$ – Devsman Jun 5 '17 at 13:44
6
$\begingroup$

we have $$x\equiv 0,1,2,3\mod 4$$ then $$x^2\equiv 0,1,0,1\mod 4$$

$\endgroup$
1
  • 3
    $\begingroup$ "... by induction". -1. $\endgroup$ – Nij Jun 4 '17 at 20:18
4
$\begingroup$

Well AFAIK, induction is defined in the context of natural numbers. You have a base step and an inductive step in the procedure of proving a statement using induction.

So, If you are proving something using Induction, you assume the truth of $P(n)$ and the try to establish the truth of $P(n+1)$ using $P(n)$. Now, in your case, you need to formulate the situation in such a way so that you prove the truth of $P(n+1)$ not the $P(n+2)$ after assuming that $P(n)$ is true. {Note that two consecutive odd numbers differ by $2$}

Notice that $P(n): (2n-1)^2$ leaves $1$ as reminder when divided by $4$.

Now, as obvious $P(1)$ is true sice $1^2\equiv 1\mod4$.

Assume that $P(n)$ is true i.e. $(2n-1)^2\equiv 1\mod 4$.

Then, $(2(n+1)-1)^2=(2n+1)^2=(2n-1)^2+4n.$ Since $(2n-1)^2\equiv 1\mod4$ and $4n\equiv 0\mod 4$ thus $(2(n+1)-1)^2=(2n+1)^2=(2n-1)^2+4n\equiv 1+0=1\mod 4$.

So, $P(n+1)$ is also true. Hence $P(n+1)$ is true for every natural number $n$.

$\endgroup$
2
$\begingroup$

Here is a proof that doesn't require induction:

We want to show that $n^2 - 1 \equiv 0 \mod{4}$ for $n$ odd.

Assume n is odd. Note that $n^2 = (n-1)^2 + 2(n-1) + 1$, or, visually for n =5: enter image description here

Since $n$ is odd, $n-1$ is even and can be written as $2k$ for some $k$. So we have that: $$\begin{align} n^2 - 1 &= (n-1)^2 + 2(n-1) \\ &= (2k)^2 + 2(2k) \\ &= 4k^2 + 4k \\ &= 4(k^2 + k) \end{align}$$

So we have shown that $n^2 -1$ is a multiple of 4, so by definition $n^2 - 1 \equiv 0 \mod{4}$ or $n^2 \equiv 1 \mod{4}$ $\blacksquare$

Unfortunately, some professors require a certain type of proof even when many are valid. We can try to turn this reasoning into an induction proof. First, we prove the claim for the base case:

Let $n = 1$. Then $1^2 = 1 \equiv 1 \mod{4}$, so the claim holds for the base case. Now, we move to prove the inductive step. Assume the claim holds for some odd n. We want to show that it holds for $n+2$ (the next odd n). See the figure below to visualize this.

enter image description here

What we are saying is that $\color{red} n^2 \color{black} \equiv 1 \mod{4}$, so we want anything we add in to get to $(n+2)^2$ to be equivalent to 0 mod 4. That is, we need to check that $$ 2\color{blue}n + 2\color{orange}{(n+1)}\color{black} + \color{purple} 2 \color{black} \equiv 0 \mod{4} $$

Well, we see this must be the case because $$\begin{align} 2n + 2(n+1) + 2 &= 2n + 2n + 2 + 2 \\ &= 4n + 4 \\ &= 4(n+1) \\ \end{align}$$

is a multiple of four, so $2n + 2(n+1) + 2 \equiv 0 \mod{4}$. So putting this together we get that: $$ (n+2)^2 = n^2 + 2n + 2(n+1) + 2 \equiv 1 \mod{4} $$ as desired. $\blacksquare$.

The other proofs here are perfectly valid, I was hoping only to give a little perspective.

$\endgroup$
1
$\begingroup$

This is a more straight-forward proof by induction than it appears to be.

The condition to be satisfied is $n^2 = 4k + 1$

The basis case would be $n = 1$.

if $n = 1$, then

$$n^2 = 1 = 4 \times 0 + 1$$

So the basis case is proven.

Now to prove that for any $n$ in which the condition holds, the condition also holds for the next consecutive valid $n$. Keeping in mind that if $n$ is odd, the next odd number is $n + 2$ and not $n + 1$,

$$(n + 2)^2 = n^2 + 4n + 4$$

See if you can figure it out from there. If not:

Substituting the condition $n^2 = 4k + 1$,
$$(n + 2)^2 = 4k + 1 + 4n + 4$$
$$= 4k + 4n + 4 + 1$$
$$=4(k + n + 1) + 1$$
$$=4k_2 + 1$$
Where $k_2$ is a constant equal to $k + n + 1$.

$\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.