Question: Prove $\forall n\geq 2,n\in\mathbb{Z}$, $(n+1)\mid(n^3+1)$
I know that it is possible to solve by factoring $n^3+1$ and showing that $n+1$ is a multiple, but I would like to show this via induction.
Attempt: Using induction:
Let $n=2:3\mid 9$, so true for $n=2$
(1) Assume true for $n=k:(k+1)\mid(k^3+1)$, so $(k+1)r=k^3+1$ for some $r\in\mathbb{Z}$
(2) Let $n=k+1:(k+2)\mid(k+1)^3+1$, so $(k+2)s=(k+1)^3+1$ for some $s\in\mathbb{Z}$
From (2) we have $(k+1)s+s=(k+1)^3+1$, subbing (1) into (2), I get $k^3+1+s=(k+1)^3+1$
Therefore $k^3+s=(k+1)^3$.
Setting $s=3k^2+3k+1$, this holds.
Where am I going wrong, is the proof valid, any help would be greatly appreciated.
The easiest way is just to factorise $n^3+1,$
giving: $n^3+1=(n+1)(n^2-n+1)$
so $(n+1)$ divides $n^3+1$ as required.