# How to show that $n(n^2 + 8)$ is a multiple of 3 where $n\geq 1$ using induction?

I am attempting a question, where I have to show $n(n^2 + 8)$ is a multiple of 3 where $n\geq 1$.

I have managed to solve the base case, which gives 9, which is a multiple of 3.

From here on,

I have $(n+1)((n+1)^2 + 8)$

$n^3 + 3n^2 + 11n + 9$

$n(n^2 + 8) + 3n^2 + 3n + 9$

How can I show that $3n^2 + 3n + 9$ is a multiple of 3?

-
"How can I show that $3n^2 + 3n + 9$ is a multiple of 3?". Come on. Think about it... – Ragib Zaman May 27 '12 at 17:08
@Ragib: I can prove that by induction. – TonyK May 27 '12 at 17:26
Owow, seven answers. Setting a new Guinness World Record. – Gigili May 27 '12 at 17:30
@Gigili haha for what? – AkshaiShah May 27 '12 at 17:32
@akshai5050: Seven answers for a not-so-difficult question. I assume they're all saying the same thing! – Gigili May 27 '12 at 17:35

You've already solved the case $n=1$, so I'll not repeat that there.

Assuming as the induction hypothesis that $n$ has the property that $3|n(n^2+8)$, we can rewrite $(n+1)((n+1)^2+8)$ to obtain $$\begin{split} (n+1)((n+1)^2+8) & = (n+1)(n^2+2n+1+8)\\ & =n(n^2+8)+n(2n+1)+((n+1)^2+8)\\ & = n(n^2+8)+3n^2+3n+9 \end{split}$$ In the latter, all the terms are divisible by $3$, hence it follows that $(n+1)((n+1)^2+8)$ is also divisible by $3$. This finishes the induction proof, so we may conclude that $n(n^2+8)$ is divisible by $3$ for all $n\geq 1$.

-

Without induction:

Since $8=-1\pmod{3}$, $n(n^2+8)=n(n^2-1)=(n-1)n(n+1)\pmod{3}$. Since $n-1$, $n$ and $n+1$ are three consecutive integers, at least (and in fact, exactly) one of them is a multiple of $3$, hence their product is a multiple of $3$.

-
I have to use induction – AkshaiShah May 27 '12 at 16:58
Any idea why? This only seems to make things more complicated... – Did May 27 '12 at 17:17
It's a past exam paper – AkshaiShah May 27 '12 at 17:22

Hint $\rm\ n\:\!(n^2\!-\!1+9) = (n\!-\!1)\:\!n\:\!(n\!+\!1) + 9\:\!n\:$ so it suffices to show $3$ divides one of $\rm\:\!n\!-\!1, n, n\!+\!1.$

The base case $\rm\:n=1\:$ is true since $3$ divides $\rm\:n\!-\!1 = 0.\:$ For the induction step notice that

$\quad 3$ divides one of $\rm\: n\!-\!1, n, n\!+\!1\:\Rightarrow\: 3$ divides one of $\rm \:n,n\!+\!1,n\!+\!2\:\$ by $\rm\:\ n\!+\!2\:\! =\:\! n\!-\!1 + 3$

For more general methods see my many posts on telescopy.

-

You start by supposing that $n(n^2+8)$ is a multiple of 3, and you need to show that $(n+1)((n+1)^2 + 8)$ is also a multiple of 3. I would start by simplifying the latter expression.

Then manipulate the expression until it is a sum of things that are multiples of 3. This includes expressions like $3a$, which is always a multiple of 3 for any $a$, and $n(n^2+8)$, by the induction hypothesis.

-

If $n\equiv 0\pmod 3$ Ok. If $n\equiv 1\pmod 3$, we have $$n^{2} + 8 \equiv 1^{2} + 2\equiv 0\pmod 3.$$ If $n \equiv 2\pmod 3$ we have $$n^{2} + 8 \equiv 2^{2} + 2\equiv 6 \equiv 0\pmod 3.$$

-

Using induction it is obvious that the statement is true for $n=1$. Now suppose that it is true for $n=k$, then we have $k(k^2+8)=3m$, where m is an integer. Considering the case where $n=k+1$, we have; $$(k+1)[(k+1)^2+8]=k(k^2+2k+9)+k^2+2k+9$$ $$=k(k^2+8+2k+1)+k^2+2k+9=k(k^2+8)+k(2k+1)+k^2+2k+9$$ $$=k(k^2+8)+3k^2+3k+9=3m+3k^2+3k+9=3(m+k^2+k+3)$$

-

Since you have proven that this formula is available for $n=1$ we suppose that formula is available for all natural numbers n=k $$k(k^2+8)$$ then according to axiomme of mathematical induction we need to prove that formula is valid for $n=k+1$ or

$$(k +1)((k+1)^2+8)$$ is multiple of 3

now we have

$$(k+1)((k+1)^2+8)=(k+1)(k^2+2k+1+8)=k^3+3k^2+11k+9=(k^3+8k)+(3k^2+3k+9)=k(k^2+8)+3(k^2+k+3)$$ first part of expression is factor of 3 by assumption an second part evidently is factor of 3

-

If $(n+1)((n+1)^2+8)=(n+1)(n^2+2n+9)$ then if $(n+1)= 0\ mod\ 3$, we're done. If not, than $(n+1)=1\mod 3$ or $(n+1)= 2\mod 3$. So if $n+1=1\mod 3$ then $n=0\mod 3$ so $3|(n^2+2n+9)$, and if $n+1=2\mod 3$ then $n^2=n=1\mod 3$ now let $n^2=3k+1$ and $n=3l+1$ so we have $(n^2+2n+9)=(3k+1+6l+2+9)=3(k+2l+1+3)$.

-

Quote: How can I show that $3n^2 + 3n + 9$ is a multiple of $3$? End of quote

I'm surprised at the complexity of some of the answers.

$$3n^2 + 3n + 9 = 3(n^2 + n + 3) = (3\cdot\text{something}).$$

A "multiple of $3$" is anything that is $3$ times something (where "something" means of course an integer).

-
Some of the answers were before I edited the question with that part. Thanks though – AkshaiShah May 27 '12 at 18:11