Stuck on mathematical induction proof at inductive step

Question

Here's the problem: Use induction to prove: For every integer $n\geq 1$, the number $n^5 − n$ is a multiple of 5.

This is what I have so far:

Basis: $ n= 1$, $n^5-n = 1-1 = 0 = (5)(0)$ so $1^5 - 1$ is a multiple of 5.

Inductive step: Suppose $n^5 -n$ is a multiple of 5 for some $n\geq 1$, then

$(n+ 1)^5 - (n + 1)$

I'm not sure how to proceed and I'm feeling a little lost on this one...

Answer 1

Don't be afraid to expand it.

$$(n + 1)^5 - (n + 1) = (n^5 + 5 n^4 + 10 n^3 + 10 n^2 + 5 n + 1) - (n + 1)$$

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

But $4 n = -n + 5 n$ so

$$(n + 1)^5 - (n + 1) = (n^5 - n) + 5 \underbrace{(n^4 + 2 n^3 + 2 n^2 + 2 n)}$$

The underbraced part is an integer, so when multiplied by $5$ is obviously a multiple of $5$. And $n^5 - n$ is a multiple of $5$ by hypothesis.

Answer 2

An alternative way of using induction, applied to this problem is :

• Let $~P(n)~$ denote that the assertion is true for $~n ~: ~n \in \Bbb{Z^+}.$

• Instead of manually checking a base case, such as $~P(1),~$ manually check multiple base cases.
  In this problem, you would manually check that $~P(n),~$ for each element in $~\{1,2,3,4,5\}.$

• Then, instead of proving that $~[ ~P(n) \implies P(n+1) ~],$ prove that $~[ P(n) \implies p(n+5) ~].$

• So, since $~P(n)~$ holds for each element in $~\{1,2,3,4,5\},~$ this would imply that $~P(n)~$ holds for each element in $~\{6,7,8,9,10\}.~$ Then, this would imply that $~P(n)~$ holds for each element in $~\{11,12,13,14,15\},~$ and so forth.

---

So,

• $5 ~| ~(1^5 - 1) = 0.$

• $5 ~| ~(2^5 - 2) = 30.$

• $5 ~| ~(3^5 - 3) = 240.$

• $5 ~| ~(4^5 - 4) = 1020.$

• $5 ~| ~(5^5 - 2) = 3120.$

Now, suppose that

$$5 | n^{5} - n ~: ~n \in \Bbb{Z^+}.$$

You also have, by binomial expansion, that for any $~n \in \Bbb{Z^+}$:

$$(n+5)^5 = n^5 + 5n^4(5) + 10n^3(5^2) + 10n^2(5^3) + 5n^1(5^4) + (5^5).$$

This implies that

$$5 ~| ~(n+5)^5 - n^5.$$

Here, if $~5 ~| ~A~$ and $~5 ~| ~B, ~$ then $~5 ~| ~(A+B).$

So:

$$\{ ~5 ~| ~[(n+5)^5 - n^5] ~~\text{and}~~ ~5 ~| ~[n^5 - n] ~\} \implies ~5 | (n+5)^5 - n.$$

Therefore, $~P(n) \implies P(n+5),~$ as required.

Note
Actually, this particular (convoluted) use of induction is not actually necessary, for this problem. This is because, as another answer has indicated, similar analysis is available by examining the binomial expansion of $~(n+1)^5 - n^5.$

However, this particular (convoluted) use of induction will often be very handy, for other Math problems, such as modulo Arithmetic problems.

---

As a simple example, suppose that you wanted to prove that for each $~n \in \Bbb{Z^+},~$ that $~(n^2 - 2)~$ is not a multiple of $~3.$

Using the convoluted induction, you would first manually check whether the assertion is true for each element in $\{1,2,3\}.$

Then, you could use binomial expansion to show that $~(n+3)^2 - n^2~$ is a multiple of $~3.$

This would establish that since the assertion is true for each element in $~\{1,2,3\},~$ it is also true for each element in $~\{4,5,6\},~$ which would establish that it is true for each element in $~\{7,8,9\},~$ and so forth.