3

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?

Niharika
  • 1,051

4 Answers4

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.

vadim123
  • 82,796
  • 1
    Some students don't like it that $0$ is a multiple of every number, but it's still true. In fact, you could use base case $p(0)=0$. – vadim123 Apr 27 '14 at 14:40
  • Well, since this function is defined for all non negative integral values of n, it would be valid to use $p(0)$ as the base case. But some part of me cringes (for no valid reason) to use either $p(0)$ or $p(1)$ as the base case. – Niharika Apr 27 '14 at 14:45
  • 1
    After you've proved (by induction) for $n\in\mathbb{N}$, you can observe that $f(-n)=f(n)$ and hence your statement is true for all $n\in\mathbb{Z}$. :-) – vadim123 Apr 27 '14 at 15:07
  • Yes! Since n is raised to even powers the domain is Z. – Niharika Apr 27 '14 at 15:13
2

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.

Community
  • 1
Bill Dubuque
  • 272,048
1

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$

lab bhattacharjee
  • 274,582
  • Remark that this is essentially a (mechanical) transformation of a non-inductive proof using Fermat's little Theorem, and the proof is simpler when presented that way - see my answer. – Bill Dubuque Apr 27 '14 at 16:36
  • @BillDubuque, What can be more natural and inductive method? – lab bhattacharjee Apr 27 '14 at 16:44
  • Above proves $,5\mid f(k+1)-f(k) = (k+1)^6-(k+1)^2-(k^6-k^2),$ by expanding it to get $,6(k^5-k) + 5g(k),$ and using $,5\mid k^5-k,$ for all $,k.,$ But if we assume that then also $,5\mid k^6-k^2,$ for all $,k,$ so $,5\mid (k+1)^6-(k+1)^2,,$ so $,5,$ divides their difference $,f(k+1)-f(k).,$ So there was no need to do the messy expansion etc. My answer explains how this is an instance of a mechanical way of transforming a non-inductive proof into an inductive proof. – Bill Dubuque Apr 27 '14 at 16:57
1

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.

lhf
  • 216,483
  • It does. I was trying to solve the question and I ended up with your solution, but I haven't used my hypothesis at all to prove it so it wouldn't be following the steps of verification through Induction. – Niharika Apr 27 '14 at 15:00
  • @Niharika You can easily transform this (or any) direct proof into an inductive proof using the method described in my answer. – Bill Dubuque Apr 27 '14 at 16:18