induction to prove $n^2 - 1$ is divisible by 4 by changing variables

Question

I have to prove $n^2 - 1$ is divisible by $4$, where $n\in\mathbb{O}_{>0}$.

It says, "You cannot prove this by induction on $n$. Rewrite $n^2 - 1$ in terms of a variable on which you can do induction."

Why is it not possible to do this by induction on $n$ and how would I change the variable?

All help is appreciated.

Answer 1

The text you are using takes a pretty narrow view of what it means to prove by induction. The statement is: $1^2-1$ is divisible by $4$, and if $k^2-1$ is divisible by $4$ where $k$ is odd, so is the next odd number ($k+2$). But \begin{equation*} (k+2)^2-1 = k^2+4k+4-1 = (k^2-1) + 4(k+1), \end{equation*} which is divisible by $4$ since $k^2-1$ is by the inductive hypothesis.

I assume that what the text means is that since we are assuming $n$ is odd, we should instead use the statement $(2k+1)^2-1$ is divisible by $4$ if $k$ is a nonnegative integer. That is proven in much the same way: true for $k=0$, and if true for $k$, then \begin{equation*} (2(k+1)+1)^2-1 = 4k^2 + 12k+9-1 = 4k^2+4k+4 + 8k+5 = (2k+1)^2 - 1 + 4(1+2k). \end{equation*}

Answer 2

If $f(n)=n^2-1$

$f(m+2)-f(m)=(m+2)^2-m^2=4(m+1)$

$\iff4\mid f(m+2)\iff4\mid f(m)$

Now $f(1)=?$

Answer 3

Put $\;n=2k-1\;,\;\;k\in\Bbb Z\;$ , so

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

and clearly the rightmost term is divisible by $\;4\;$ so we're done.