# Induction - Divisibility

• Dec 24th 2011, 08:22 AM
cosmonavt
Induction - Divisibility
We have to prove that $n(n^2+5)$ is divisible by 6. How do we go about it?
• Dec 24th 2011, 08:49 AM
Plato
Re: Induction - Divisibility
Quote:

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

Do it for the base case: $n=1$.

Suppose that it is true for $n=k$ then look at the expansion of $(k+1)((k+1)^2+5)$
• Dec 24th 2011, 09:13 AM
Wilmer
Re: Induction - Divisibility
Quote:

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

n^3 + 5n - 6k = 0 where k is any integer

n = m - 5/(3m)
where:
m = {[SQRT(243k^2 + 125)] / 3^(3/2) + 3k}^(1/3)

Thassa hint?!
• Dec 24th 2011, 10:32 AM
MarkFL
Re: Induction - Divisibility
To use induction, as mentioned, we first check the base case $P_1$:

$1\left(1^2+5\right)=1(6)=6(1)$ true. So we state our induction hypothesis $P_n$:

$n\left(n^2+5\right)=6k_n$ where $k_n\in\mathbb Z$

Then we would like to add some expression f(n) to each side such that:

$n\left(n^2+5\right)+f(n)=(n+1)\left((n+1)^2+5 \right)$
• Dec 24th 2011, 10:46 AM
Quacky
Re: Induction - Divisibility
Quote:

Originally Posted by MarkFL2
To use induction, as mentioned, we first check the base case $P_1$:

...etc...

Thus, we have derived $P_{n+1}$ from $P_n$ thereby completing the proof by induction.

...Which the OP would have been able to try themselves had they followed Plato's advice, which was rendered obsolete by your full solution.
• Dec 24th 2011, 12:37 PM
Deveno
Re: 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 PM
Also sprach Zarathustra
Re: 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 PM
MarkFL
Re: Induction - Divisibility
Just for fun, we could begin with the non-homogeneous recurrence:

(1) $S_{n+1}=S_{n}+\frac{n(n+1)}{2}+1$ where $S_0=0$

(2) $S_{n+2}=S_{n+1}+\frac{(n+1)(n+2)}{2}+1$

Subtracting (1) from (2) yields:

(3) $S_{n+2}=2S_{n+1}-S_{n}+n+1$

(4) $S_{n+3}=2S_{n+2}-S_{n+1}+(n+1)+1$

Subtracting (3) from (4) yields:

(5) $S_{n+3}=3S_{n+2}-3S_{n+1}+S_{n}+1$

(6) $S_{n+4}=3S_{n+3}-3S_{n+2}+S_{n+1}+1$

Subtracting (5) from (6) yields:

$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:

$r^4-4r^3+6r^2-4r+1=0$

$(r-1)^4=0$

We have the root r = 1 of multiplcity 4, thus, the closed-form for $S_n$ will take the form:

$S_n=k_1+k_2n+k_3n^2+k_4n^3$

$S_0=0\:\therefore\:k_1=0$

Computing:

$S_1=1$

$S_2=3$

$S_3=7$

We now have the 3X3 system:

$k_2+k_3+k_4=1$

$2k_2+4k_3+8k_4=3$

$3k_2+9k_3+27k_4=7$

and we find:

$k_2=\frac{5}{6}$

$k_3=0$

$k_4=\frac{1}{6}$

Therefore, we have:

$S_n=\frac{5n}{6}+\frac{n^3}{6}=\frac{n\left(n^2+5 \right)}{6}$

Thus:

$n\left(n^2+5\right)=6S_n$

From (1), noting that the product of two consecutive integers is always even, we know $S_n$ is an integer.
• Dec 24th 2011, 02:30 PM
Deveno
Re: Induction - Divisibility
so far, i count 4 ways to skin this cat. outstanding!
• Dec 24th 2011, 04:53 PM
Wilmer
Re: Induction - Divisibility
https://oeis.org/

enter sequence# A004006
• Dec 24th 2011, 07:19 PM
MarkFL
Re: Induction - Divisibility
In a method very similar to that of Also sprach Zarathustra, we know:

$(n-1)n(n+1)$ is divisible by 6, and so must:

$(n-1)n(n+1)+6n$ be divisible by 6.

$(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 PM
Prove It
Re: Induction - Divisibility
Quote:

Originally Posted by MarkFL2
In a method very similar to that of Also sprach Zarathustra, we know:

$(n-1)n(n+1)$ is divisible by 6, and so must:

$(n-1)n(n+1)+6n$ be divisible by 6.

$(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)$

I like this one best, it's so clear and simple :)