We have to prove that is divisible by 6. How do we go about it?

Printable View

- December 24th 2011, 09:22 AMcosmonavtInduction - Divisibility
We have to prove that is divisible by 6. How do we go about it?

- December 24th 2011, 09:49 AMPlatoRe: Induction - Divisibility
- December 24th 2011, 10:13 AMWilmerRe: Induction - Divisibility
- December 24th 2011, 11:32 AMMarkFLRe: Induction - Divisibility
To use induction, as mentioned, we first check the base case :

true. So we state our induction hypothesis :

where

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

- December 24th 2011, 11:46 AMQuackyRe: Induction - Divisibility
- December 24th 2011, 01: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). - December 24th 2011, 01: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. - December 24th 2011, 02:54 PMMarkFLRe: Induction - Divisibility
Just for fun, we could begin with the non-homogeneous recurrence:

(1) where

(2)

Subtracting (1) from (2) yields:

(3)

(4)

Subtracting (3) from (4) yields:

(5)

(6)

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:

Computing:

We now have the 3X3 system:

and we find:

Therefore, we have:

Thus:

From (1), noting that the product of two consecutive integers is always even, we know is an integer. - December 24th 2011, 03:30 PMDevenoRe: Induction - Divisibility
so far, i count 4 ways to skin this cat. outstanding!

- December 24th 2011, 05:53 PMWilmerRe: Induction - Divisibility
https://oeis.org/

enter sequence# A004006 - December 24th 2011, 08:19 PMMarkFLRe: Induction - Divisibility
In a method very similar to that of

**Also sprach Zarathustra**, we know:

is divisible by 6, and so must:

be divisible by 6.

- December 24th 2011, 09:04 PMProve ItRe: Induction - Divisibility