To use induction, as mentioned, we first check the base case :
true. So we state our induction hypothesis :
Then we would like to add some expression f(n) to each side such that:
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:
Subtracting (1) from (2) yields:
Subtracting (3) from (4) yields:
Subtracting (5) from (6) yields:
Now we have a homogeneous recurrence whose associated characteristic equation is:
We have the root r = 1 of multiplcity 4, thus, the closed-form for will take the form:
We now have the 3X3 system:
and we find:
Therefore, we have:
From (1), noting that the product of two consecutive integers is always even, we know is an integer.