3
$\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$
1
  • $\begingroup$ 4 continuous numbers have multiples of 2,3 and 4. $\endgroup$ Commented Apr 5, 2016 at 7:11

4 Answers 4

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$
0
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .