<s>[INST] Use mathematical induction to prove an assertion The assertion: $n^3 + 5n$ is divisible by $6$
I have completed the basis step $(n=1)$ and the first part of the induction step $(n=k)$, but I am stuck on the second part $(n=k+1)$.
This is what I have so far:
For $n=k$: $k^3 + 5k = 6t$
For $n= k+1$:
$(k+1)^3 + 5(k+1)$
$= k^3 + 3k^2 + 8k + 6$
$= (k^3 + 5k) + 3k + 3k^2 + 6$
$= 3k^2 + 3k + 6t + 6$
$= ???$
I cannot pull out a $6$ because that would leave halves that cannot be counted as integers. How should I proceed?
 [/INST] Proof by induction
First, show that this is true for $n=1$:
$1^3+5\cdot1=6$
Second, assume that this is true for $n$:
$n^3+5n=6k$
Third, prove that this is true for $n+1$:
$(n+1)^3+5(n+1)=$
$n^3+3n^2+3n+1+5n+5=$
$\color\red{n^3+5n}+3n^2+3n+1+5=$
$\color\red{6k}+3n^2+3n+1+5=$
$6k+3n^2+3n+6=$
$6k+6+3n^2+3n=$
$6(k+1)+3\cdot\color\green{n(n+1)}=$
$6(k+1)+3\cdot\color\green{2m}=$
$6(k+1)+6m=$
$6(k+1+m)$
Please note that the assumption is used only in the part marked red.

Proof by modular arithmetic
Consider the following cases:


*

*$n\equiv0\pmod6 \implies n^3+5n\equiv0^3+5\cdot0\equiv6\cdot 0\equiv0\pmod6$

*$n\equiv1\pmod6 \implies n^3+5n\equiv1^3+5\cdot1\equiv6\cdot 1\equiv0\pmod6$

*$n\equiv2\pmod6 \implies n^3+5n\equiv2^3+5\cdot2\equiv6\cdot 3\equiv0\pmod6$

*$n\equiv3\pmod6 \implies n^3+5n\equiv3^3+5\cdot3\equiv6\cdot 7\equiv0\pmod6$

*$n\equiv4\pmod6 \implies n^3+5n\equiv4^3+5\cdot4\equiv6\cdot14\equiv0\pmod6$

*$n\equiv5\pmod6 \implies n^3+5n\equiv5^3+5\cdot5\equiv6\cdot25\equiv0\pmod6$


Please note that this method is handy only for a relatively small divisor.
</s>