2
$\begingroup$

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer.

I'm supposed to use proof by induction, but I failed at it miserably. So far I have this:

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

Let $n = 2k + 1$ because its always odd. Then

$$\begin{align} &(2k+1)(2k)(2k+1)(2k+2) \\\implies\quad &(2k+1)(2k)(2k+1)2(k+1) \\\implies\quad &(2k+1)2(k)(2k+1)2(k+1) \\\implies\quad &4(2k+1)(k)(2k+1)(k+1) \\\implies\quad &4((2k+1)^2)(k)(k+1) \\\implies\quad &4((2k+1)^2)((k^2)+k) \end{align}$$

Now $(2k+1)^2$ is odd and $k^2 + k$ is always even because

$$\begin{cases} \mathrm{odd}^2 + \mathrm{odd} = \mathrm{even} \\ \mathrm{even}^2 + \mathrm{even} = \mathrm{even} \end{cases}$$

So that means I can take out a $2$ and write $((k^2)+k) = 2X$.

$$\begin{align} &4(2X)((2k+1)^2) \\\implies\quad &8X((2k+1)^2) \end{align}$$

and because there is an $8$ I can say its always divisible by $8$, no matter what odd integer $k$ is? How can this be done using proof by induction?

$\endgroup$
  • $\begingroup$ 4 continuous numbers have multiples of 2,3 and 4. $\endgroup$ – Takahiro Waki Apr 5 '16 at 7:11
3
$\begingroup$

You can do it more simply. Your statement that if $n$ is odd you can express it as $2k+1$ is correct. Then write $n^4-n^2=(2k+1)(2k)(2k+1)(2k+2)=(2k+1)^2(2k)(2k+2)$ Now if $k$ is odd, $2k+2$ has two factors of $2$-it is divisible by $4$. If $k$ is even, $2k$ is divisible by $4$. Either way, $2k(2k+2)$ is divisible by $8$. Another approach is just to check the odd residues $\bmod 8$ Induction was well covered by Zelzy

$\endgroup$
1
$\begingroup$

To do a proof by induction you basically

  1. Show it works for $n = 1$ (which it does because $8$ divides $0$

  2. Assume it works for some $n=2k+1$ (i.e. some odd number)

  3. Show that your assumption implies it works for $n=2k+3$. This is usually the tricky part. But all you really have to do is expand the polynomial, and then you'll basically get something that looks like $8y + (2k+1)^4-(2k+1)^2$ (where $y$ is just some expression of $x$) and then obviously that's divisible by $8$ since $8y$ is clearly divisible by $8$ and the second part $(2k+1)^4-(2k+1)$ is divisible by $8$ by assumption (i.e. step $2$). You should work out the expansion yourself though.

$\endgroup$
1
$\begingroup$

Base step : $8$ divides $0$.

Hypothesis Step : Let $(2k+1)^4 - (2k+1)^2 = 8m$

Induction Step : To show : $(2k+ 3)^4 - (2k+3)^2 = 8j$

Now, the main insight is that you must somehow manipulate the induction step to use the hypothesis. How do we do that ?

$$ \begin{align} &&(2k+1+2)^4-(2k+1+2)^2 \\ &&=(2k+1)^4 +4(2k+1)^3\times 2 + 6(2k+1)^22^2+4(2k+1)2^3 +2^4 - (2k+1)^2 -2(2k+1)2 -4 \\ &&= (2k+1)^4 - (2k+1)^2 + 8(2k+1)^3 + 8(2k+1)^23 + 8(2k+1)2^3 + 2^3\times 2 - 4(2k+1+1)\\ &&=8m + 8a - 8(k+1)\\ &&=8j \end{align} $$

Hence, proved.

The main insights of this proof are ... 1. We try to prove this on $k $ rather than $n$because it allows us to apply induction easier. 2.We write $3 $ as $1 +2$ so that we can use our hypothesis and build on what has already been done.

Simpler alternate proof : $A = n^2(n+1)(n-1)$

$n+1$ and $n-1$ are two consecutive even integers. So, one of them has to be a multiple of 4. This means that $A$ is divisible by 8.

$\endgroup$
0
$\begingroup$

You are almost done in your first step. You showed $$ (n^4)−(n^2)=(n^2)((n^2)−1)=n(n−1)n(n+1). $$ Now $n$ is odd hence $n-1$ and $n+1$ are even, since every second even number is divisible by $4$ either $4k_1 =n-1$ and $2k_2=n+1$ or $4k_1=n+1$ and $2k_2=n-1$ for some $k_1,k_2\in\mathbb{N}$, this is $$ (n^4)−(n^2) = n^2(4k_1)(2k_2). $$

But if you want to prove it by induction you can try this: Let $n$ be odd such that $8|(n^4)−(n^2)$, we will show it for $n+2$.

First note that $8|(n^4)−(n^2)=n^2(n−1)(n+1)$ implies that $8|=(n−1)(n+1)$, hence $\exists k\in\mathbb{N}$ such that $8k=(n-1)(n+1)$, and compute for $n+2$ $$ ((n+1)^4)−((n+2)^2) =(n+2)^2(n+1)(n+3)= (n+2)^2(n+1)((n-1)+4)=(n+2)^2(8k+(n+1)4) $$ since $n$ is odd $n+1$ is even and hence $8|4(n+1)$ and we are done.

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