Prove $n^2(n^4-1)$ is divisible by 60 using Mathematical Induction.

Question

Base step:

p(2)=4 * 15= 60

Inductive Hypothesis: Assuming p(k) = $k^2(k^4-1)$ = 60q

Induction:

p(k+1)= $(k+1)^2[(k+1)^4-1]$ = $(k+1)^2[(k+1)^2 + 1][(k+1)^2 - 1]$ = $(k+1)^2(k^2+2k+2)(k^2+2k+1- 1)$ = $(k+1)^2(k^2+2k+2) k (k+2)$ = $k(k+1)(k+2)(k^2+2k+2)(k+1)$

Now $k(k+1)(k+2)$ is the product of 3 consecutive natural numbers. Their product HAS to be a multiple of 2 and 3 and hence also a multiple of 6. So all that I have to do is prove that $(k^2+2k+2)(k+1)$ is a multiple of 10. But I can't seem to do so. Also through my induction, I have not at all made use of my hypothesis! How do I go about solving this question through the Principle of Mathematical Induction?

Answer 1

Induction is not the easiest way to prove that $\,60\mid f(n) = n^6-n^2.\,$ But if you must use induction then here is one very easy way to proceed. Namely, first we can prove it directly via little Fermat, then we can mechanically transform the proof to inductive form, as follows

$\qquad $ mod $5\!:\,\ n^5\equiv n\,\overset{\large \times n}\Rightarrow\, n^6\equiv n^2$

$\qquad $ mod $3\!:\,\ n^3\equiv n\!\overset{\rm square}\Rightarrow\! n^6\equiv n^2$

$\qquad $ mod $4\!:\,\ n\equiv 1,3\,\Rightarrow\,n^2\equiv 1\overset{\rm cube}\equiv n^6\, $ and $\,n\equiv 0,2\,\Rightarrow\,n^2\equiv 0\overset{\rm cube}\equiv n^6$

Therefore $\,3,4,5\mid n^6-n^2\,\Rightarrow\, 3\cdot 4\cdot 5 = 60\mid n^6-n^2\ $ since $\,{\rm lcm}(3,4,5) = 3\cdot 4\cdot 5.$

We can mechanically transform the above proof into an inductive proof as follows. The base case $\:60\mid f(0) = 0\,$ is clear. Suppose $\ 60\mid \color{#c00}{f(k)}.\,\ $ Next prove $\ 60\mid \color{#0a0}{f(k+1)-f(k)}\,$ using the method above to prove that $\,60\mid \color{#0a0}{f(k)},\ 60\mid \color{#0a0}{f(k+1)}.\,$ Therefore $\,60\mid \color{#0a0}{f(k+1)-f(k)}+\color{#c00}{f(k)} = f(k+1),\,$ completing the inductive step, hence completing the inductive proof.

Since the first method directly proves that $\,60\mid \color{}{f(k)}\,$ for all $k$, it is redundant to repeat those proofs twice to infer $\,60\mid f(k+1)-f(k).\,$ But this is essentially what most "inductive" proofs amount to. Moreover unless such proofs explicitly exploit this redundancy, their arithmetic is often (much) more complicated (e.g see the proof in lab's answer). Often one finds such redundancy in inductive proofs, so a bit of introspection on the inductive process is well-worth the effort, since it can lead to great simplification (esp. in more complex problems). Analogous inductive introspection leads to the powerful method of telescopic induction, which I discuss in many posts on telescopy.

Answer 2

To solve by induction, you need to prove that $$p(k+1)-p(k)=k(k+1)(2k+1)(3k^2+3k+4)$$ is a multiple of $60$. (also that $p(1)=0$ is a multiple of 60).

To do this, you need to prove that it's a multiple of $3,4$, and $5$. For example, we take it mod 3 and get $k(k+1)(-k+1)(1)=k-k^3$, which is always $0$ by Fermat's Little Theorem. Worst case, you can just try the 3/4/5 values to verify that you get $0$ in modular arithmetic.

Answer 3

If $f(n)=n^2(n^4-1)=n^6-n^2$ is divisible by $60$ for $n=k$

$$f(k+1)-f(k)=(k+1)^6-(k+1)^2-\{k^6-k^2\}$$

$$=6k^5+15k^4+20k^3+15k^2+6k-2k$$

which is $\displaystyle6(k^5-k)+15k^4+20k^3+15k^2+10k$ divisible by $5$ as $k^5-k$

Again, $\displaystyle6k^5+15k^4+20k^3+15k^2+4k\equiv2(k^3-k)\pmod3\equiv0$

finally, $\displaystyle6k^5+15k^4+20k^3+15k^2+4k=2k^5-k^4-k^2\pmod4\equiv2k^4(k-1)+k^4-k^2$

$\displaystyle\equiv2k^3 \underbrace{k\cdot(k-1)}_{\text{ even}}+k^2(k-1)(k+1)\pmod4$

If $k$ is even, $\displaystyle4|k^2$ else $2|(k\pm1)\implies 2^2|(k^2-1)$

So, $\displaystyle f(k+1)-f(k)$ will be divisible by lcm$(4,3,5)=60$

Answer 4

Does it have to be by induction?

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

$2$ divides $n(n-1)$ and $n(n+1)$ and so $4$ divides $n^2(n^4-1)$.

$3$ divides $(n-1)n(n+1)$ and so $3$ divides $n^2(n^4-1)$.

Since $60=4\cdot3\cdot5$, it remains to prove that $5$ divides $n^2(n^4-1)=n(n^5-n)$. But this follows from Fermat's little theorem and also by induction.