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?
 A: write $$n^3+5n$$ in the form $$(n-1)n(n+1)+6n$$ and this is the proof.
A: You can complete your work this way:
$$
(k+1)^3 + 5(k+1)=(k^3 + 5k) + 3k + 3k^2 + 6=6t+3k+3k^2+6=6 \left(t+1+\frac{k(k+1)}{2} \right)
$$
and note that $k$ or $k+1$ is even.
A: Hint: Note, $3k+3k^2=3k(k+1)$. As you want to show divisibility by $6$ and $3$ is a factor you only need to show that it is divisible with $2$. What is $k(k+1)$ if $k$ is even? What happens if $k$ is odd?
A: Alternatively. Putting $n=k+1$ into your given expression $n^3+5n$ gives $(k+1)^3+5(k+1)$ (Induction) and that expands to $k^3+3k^2+2k+6k+6$ which can be rewritten as $k(k+1)(k+2)+6(k+1)$. Both terms are divisible by $6$ (why?) and from here I essentially concur with Sonnhard
A: 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.
