We have to prove that $\displaystyle n(n^2+5)$ is divisible by 6. How do we go about it?
To use induction, as mentioned, we first check the base case $\displaystyle P_1$:
$\displaystyle 1\left(1^2+5\right)=1(6)=6(1)$ true. So we state our induction hypothesis $\displaystyle P_n$:
$\displaystyle n\left(n^2+5\right)=6k_n$ where $\displaystyle k_n\in\mathbb Z$
Then we would like to add some expression f(n) to each side such that:
$\displaystyle n\left(n^2+5\right)+f(n)=(n+1)\left((n+1)^2+5 \right)$
there is another proof, which does not use induction (there is always more than one way to skin a cat, although a skinning knife is recommended).
suppose n is odd. then n = 2k+1. so n^2 = (2k+1)(2k+1) = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, so n^2 is odd.
then, n^2 + 5 is even, so n(n^2 + 5) is even.
on the other hand, if n is even, then so is n(n^2 + 5). so in all cases (n even or odd), n(n^2 + 5) is even. so 2 divides n(n^2 + 5).
now if 3 divides n, then both 2 and 3 divide n(n^2 + 5), so 6 must divide n(n^2 + 5), since 2 and 3 are relatively prime.
but...3 may not divide n. there are two ways this could happen:
n = 3k - 1, or n = 3k + 1. we will look at each, in turn.
if n = 3k - 1, then n(n^2 + 5) = (3k - 1)((3k - 1)^2 + 5) = (3k - 1)(9k^2 - 6k + 1 + 5)
= (3k - 1)(9k^2 - 6k + 6) = 3[(3k - 1)(3k^2 - 2k + 2)], so in this case, as well, 3 divides n(n^2 + 5).
if n = 3k + 1, then n(n^2 + 5) = (3k + 1)((3k + 1)^2 + 5) = (3k + 1)(9k^2 + 6k + 1 + 5)
= (3k + 1)(9k^2 + 6k + 6) = 3[(3k + 1)(3k^2 + 2k + 2)], which is certainly divisible by 3.
so, in all cases (no matter if n is even, or odd, a multiple of 3, one less than a multiple of 3, or 1 more than a multiple of 3),
n(n^2 + 5) is divisible by both 2 and 3, and so is divisible by 6.
(the astute reader will notice that the above proof can be simplified greatly using modular arithmetic).
Just for fun, we could begin with the non-homogeneous recurrence:
(1) $\displaystyle S_{n+1}=S_{n}+\frac{n(n+1)}{2}+1$ where $\displaystyle S_0=0$
(2) $\displaystyle S_{n+2}=S_{n+1}+\frac{(n+1)(n+2)}{2}+1$
Subtracting (1) from (2) yields:
(3) $\displaystyle S_{n+2}=2S_{n+1}-S_{n}+n+1$
(4) $\displaystyle S_{n+3}=2S_{n+2}-S_{n+1}+(n+1)+1$
Subtracting (3) from (4) yields:
(5) $\displaystyle S_{n+3}=3S_{n+2}-3S_{n+1}+S_{n}+1$
(6) $\displaystyle S_{n+4}=3S_{n+3}-3S_{n+2}+S_{n+1}+1$
Subtracting (5) from (6) yields:
$\displaystyle S_{n+4}=4S_{n+3}-6S_{n+2}+4S_{n+1}-S_{n}$
Now we have a homogeneous recurrence whose associated characteristic equation is:
$\displaystyle r^4-4r^3+6r^2-4r+1=0$
$\displaystyle (r-1)^4=0$
We have the root r = 1 of multiplcity 4, thus, the closed-form for $\displaystyle S_n$ will take the form:
$\displaystyle S_n=k_1+k_2n+k_3n^2+k_4n^3$
$\displaystyle S_0=0\:\therefore\:k_1=0$
Computing:
$\displaystyle S_1=1$
$\displaystyle S_2=3$
$\displaystyle S_3=7$
We now have the 3X3 system:
$\displaystyle k_2+k_3+k_4=1$
$\displaystyle 2k_2+4k_3+8k_4=3$
$\displaystyle 3k_2+9k_3+27k_4=7$
and we find:
$\displaystyle k_2=\frac{5}{6}$
$\displaystyle k_3=0$
$\displaystyle k_4=\frac{1}{6}$
Therefore, we have:
$\displaystyle S_n=\frac{5n}{6}+\frac{n^3}{6}=\frac{n\left(n^2+5 \right)}{6}$
Thus:
$\displaystyle n\left(n^2+5\right)=6S_n$
From (1), noting that the product of two consecutive integers is always even, we know $\displaystyle S_n$ is an integer.
https://oeis.org/
enter sequence# A004006
In a method very similar to that of Also sprach Zarathustra, we know:
$\displaystyle (n-1)n(n+1)$ is divisible by 6, and so must:
$\displaystyle (n-1)n(n+1)+6n$ be divisible by 6.
$\displaystyle (n-1)n(n+1)+6n=n\left(n^2-1\right)+6n=n\left(n^2-1+6\right)=n\left(n^2+5\right)$