We have to prove that $\displaystyle n(n^2+5)$ is divisible by 6. How do we go about it?

Printable View

- Dec 24th 2011, 08:22 AMcosmonavtInduction - Divisibility
We have to prove that $\displaystyle n(n^2+5)$ is divisible by 6. How do we go about it?

- Dec 24th 2011, 08:49 AMPlatoRe: Induction - Divisibility
- Dec 24th 2011, 09:13 AMWilmerRe: Induction - Divisibility
- Dec 24th 2011, 10:32 AMMarkFLRe: Induction - Divisibility
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)$ - Dec 24th 2011, 10:46 AMQuackyRe: Induction - Divisibility
- Dec 24th 2011, 12:37 PMDevenoRe: Induction - Divisibility
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). - Dec 24th 2011, 12:51 PMAlso sprach ZarathustraRe: Induction - Divisibility
We know that the multaplication of every 3 consecutive numbers is divisible by 6.

n(n+1)(n+2) = n^3+3n^2+2n

Now, n(n^2+5)=n^3+5n

Hence, n^3+5n=n^3+3n^2+2n-(3n^2+3n)=(n^3+3n^2+2n)-3n(n+1)

And 3n(n+1) is divisible by 6. - Dec 24th 2011, 01:54 PMMarkFLRe: Induction - Divisibility
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. - Dec 24th 2011, 02:30 PMDevenoRe: Induction - Divisibility
so far, i count 4 ways to skin this cat. outstanding!

- Dec 24th 2011, 04:53 PMWilmerRe: Induction - Divisibility
https://oeis.org/

enter sequence# A004006 - Dec 24th 2011, 07:19 PMMarkFLRe: Induction - Divisibility
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)$ - Dec 24th 2011, 08:04 PMProve ItRe: Induction - Divisibility