0

By using the principle of Mathematical Induction, prove that: $P(n)=n(n+1)(2n+1)$ is divisible by $6$.

My Attempt: Base Case: $n=1$ $$P(1)=1(1+1)(2\times 1+1)$$ $$=2\times 3$$ $$=6$$, Which is divisible by $6$. $P(1)$ is divisible by $6$

Induction Hypothesis: $(n=k)$ $P(k)=k(k+1)(2k+1)$

Now, how.should I move on?

Gerry Myerson
  • 179,216
pi-π
  • 7,416
  • With the inductive step, what you do first is assume that whatever you are trying to prove is true for $n=k$, then attempt to use that assumption to show it holds true for $n=k+1$ – tzamboiv Oct 10 '16 at 06:13
  • 2
    Hint: write down $P(k+1)-P(k)$. – dxiv Oct 10 '16 at 06:16
  • @Dxiv, in which step? And how? Please elaborate a bit. – pi-π Oct 10 '16 at 06:18
  • (Just for interest) Apart from induction, another way to prove it is to consider the formula for the sum of squared natural numbers (Faulhaber formula for $n=2$). – Deepak Oct 10 '16 at 06:31
  • @Ramanujan, What does that mean? – pi-π Oct 10 '16 at 06:54

3 Answers3

2

The induction hypothesis - $P(k): k(k+1)(2k+1)$ is divisible by $6$, i.e. $k(k+1)(2k+1)=6m$ for some $m$.

Now, $$\begin{align} &(k+1)\{(k+1)+1\}\{2(k+1)+1\} \\ = & (k+1)(k+2)(2k+3) \\ = & k(k+1)(2k+3)+2(k+1)(2k+3) \\ = & k(k+1)(2k+1)+2k(k+1)+2(k+1)(2k+3) \\ = & 6m+(k+1)(2k+4k+6) \\ = & 6m+6(k+1)^2 \end{align}$$

So $(k+1)\{(k+1)+1\}\{2(k+1)+1\}$ is divisible by $6$ i.e. $P(k+1)$ is true.

Hope this helps you.

SchrodingersCat
  • 24,472
1

Since by induction hypothesis $P(k)$ is divisible by $6$ then $P(k+1)$ is divisible by $6$ iff the difference $P(k+1)-P(k)$ is divisible by $6$. Now $$P(k+1)-P(k)=(k+1)(k+2)(2k+3)-k(k+1)(2k+1)\\ =(k+1)\left[(k+2)(2k+3)-k(2k+1)\right]=6(k+1)^2.$$

Robert Z
  • 145,942
1

Hint: assume by the induction hypothesis that $P(k)$ is divisible by $6$. Then note that:

$$ \begin{align} P(k+1)-P(k) & =(k+1)(k+2)(2k+3)-k(k+1)(2k+1) \\ & = (k+1)(2k^2 + 7k + 6 - 2k^2 - k) \\ & = (k+1)(6k+6) = 6(k+1)^2 \end{align} $$

is divisible by $6$ as well.

dxiv
  • 76,497
  • Why did you.subtract $P(k)$? – pi-π Oct 10 '16 at 06:32
  • Because if $P(k)$ is a multiple of $6$ (by the induction hypothesis) and $P(k+1)-P(k)$ is a multiple of 6 (as proved above), then their sum $P(k+1)$ will be a multiple of $6$ which concludes the induction step. – dxiv Oct 10 '16 at 06:34
  • $P(k+1)-P(k)$ then, is your induction step? – pi-π Oct 10 '16 at 06:39
  • That's the intermediate step to prove that $P(k+1)=P(k) + (P(k+1)-P(k))$ is a multiple of $6$ which is technically the induction step. – dxiv Oct 10 '16 at 06:44