Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.

I've started by letting $P(n) = n^3+11n$

$P(1)=12$ (divisible by 6, so $P(1)$ is true.)

Assume $P(k)=k^3+11k$ is divisible by 6.

$P(k+1)=(k+1)^3+11(k+1)=k^3+3k^2+3k+1+11k+11=(k^3+11k)+(3k^2+3k+12)$

Since $P(k)$ is true, $(k^3+11k)$ is divisible by 6 but I can't show that $(3k^2+3k+12)$ is divisible by 6

For any positive integer $n$, let $S(n)$ denote the statement $$ S(n) : 6\mid (n^3+11n). $$

Base step: For $n=1, S(1)$ gives $1^3+11(1) = 12 = 2\cdot 6$. Thus, $S(1)$ holds.

Inductive step: Let $k\geq 1$ be fixed, and suppose that $S(k)$ holds; in particular, let $\ell$ be an integer with $6\ell = k^3+11k$. Then \begin{align} (k+1)^3 + 11(k+1) &= (k^3+3k^2+3k+1) + (11k+11)\tag{expand}\\[0.5em] &= \color{red}{k^3+11k}+3k^2+3k+12\tag{rearrange}\\[0.5em] &= \color{red}{6\ell} + 3k(k+1)+2\cdot 6.\tag{by ind. hyp.} \end{align} Since one of $k$ and $k+1$ is even, the term $3k(k+1)$ is divisible by $6$, and so the last expression above is divisible by $6$. This proves $S(k+1)$ and concludes the inductive step $S(k)\to S(k+1)$.

By mathematical induction, for each $n\geq 1$, the statement $S(n)$ is true. $\blacksquare$

$$3k^2 + 3k + 12=3(k^2 + k +4)= 3(k(k+1)+4)$$

Can you see why $k(k+1)$ and $4$ are each divisible by $2$?

At least one of $k, k+1$ is even, as is $4$, hence $2$ divides $(k(k+1)+4)$, and with three as a factor of $\color{blue}{3}(k(k+1)+ 4)$, we have $$2\cdot 3 = 6\mid (3k^2 + 3k + 12).$$

First, show that this is true for $n=1$:

$1^3+11=6\cdot2$

Second, assume that this is true for $n$:

$n^3+11n=6k$

Third, prove that this is true for $n+1$:

$(n+1)^3+11(n+1)=$

$n^3+3n^2+14n+12=$

$\color{red}{n^3+11n}+3n^2+3n+12=$

$\color{red}{6k}+3n^2+3n+12=$

$6k+3n(n+1)+12=$

• $2 |n\implies6|3n \implies6|3n(n+1)\implies3n(n+1)=6m$
• $2\not|n\implies2|n+1\implies6|3n(n+1)\implies3n(n+1)=6m$

$6k+6m+12=$

$6(k+m+2)$

Please note that the assumption is used only in the part marked red.

Alternatively, consider the following options:

• $n\equiv0\pmod6 \implies n^3+11n\equiv 0+ 0\equiv6\cdot 0\equiv0\pmod6$
• $n\equiv1\pmod6 \implies n^3+11n\equiv 1+11\equiv6\cdot 2\equiv0\pmod6$
• $n\equiv2\pmod6 \implies n^3+11n\equiv 8+22\equiv6\cdot 5\equiv0\pmod6$
• $n\equiv3\pmod6 \implies n^3+11n\equiv 27+33\equiv6\cdot10\equiv0\pmod6$
• $n\equiv4\pmod6 \implies n^3+11n\equiv 64+44\equiv6\cdot18\equiv0\pmod6$
• $n\equiv5\pmod6 \implies n^3+11n\equiv125+55\equiv6\cdot30\equiv0\pmod6$

Since $n^{3} + 11n = 6m$ for some integer $m,$ we have $$(n+1)^{3} + 11(n+1) = 6m + 3n^{2} + 3n + 12 = 6m + 12 + 3(n^{2} + n).$$ It suffices to prove that $3(n^{2} + n)$ is a multiple of $6$. But, since if $n$ is odd then $n^{2} + n = 2m'$ for some integer $m'$ and if $n$ is even then of course $n^{2} + n = 2m''$ for some integer $m'',$ it follows that $6$ is indeed a multiple of $3(n^{2}+n),$ qed.

I want to give a direct proof:

$n^3+11n=(n-1)n(n+1)+12n$

Note: a product of three consecutive integers needs to divisible by 6.