Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2018-01-31 19:29:27

Monox D. I-Fly
Member
From: Indonesia
Registered: 2015-12-02
Posts: 1,268

[ASK] Prove Using Induction

Prove that n(n + 1)(n + 2) is divisible by 6 for any integer n

What I have done so far:

For n = 1
1(1 + 1)(1 + 2) = 1(2)(3) = 6(1) = 6
6 is divisible by 6 (TRUE)

For n = k
k(k + 1)(k + 2) is divisible 6 (ASSUMED AS TRUE)

For n = k + 1
(k + 1)(k + 2)(k + 3) = k(k + 1)(k + 2) + 3(k + 1)(k + 2)

What am I supposed to do from here onward?

Yes, I know that:
k(k + 1)(k + 2) is divisible by 6
(k + 1) and (k + 2) are subsequent numbers so that its product is even or divisible by 2. Because (k + 1)(k + 2) is divisible by 2 then 3(k + 1)(k + 2) is divisible by 6.
Because k(k + 1)(k + 2) is divisible by 6 and 3(k + 1)(k + 2) is divisible by 6 then k(k + 1)(k + 2) + 3(k + 1)(k + 2) is divisible by 6 (PROVEN TRUE)

However, I am not sure if that follows the standard procedure of mathematical induction. Can someone please show me the "proper" "formal" way using mathematical induction continued from the bolded part?

Last edited by Monox D. I-Fly (2018-01-31 19:30:42)


Actually I never watch Star Wars and not interested in it anyway, but I choose a Yoda card as my avatar in honor of our great friend bobbym who has passed away. May his adventurous soul rest in peace at heaven.

Offline

#2 2018-01-31 21:55:11

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,398

Re: [ASK] Prove Using Induction

hi Monox D. I-Fly

That looks good to me.  You've done the two stages: (1) showed it works for a starting value; (2) showed that true for k leads to true for k+1.   There will always be a bit of algebra at (2) and what you have done is correct and does prove stage (2).

As an alternative, you could start by saying let's consider the expression  k(k+1)(k+2) + 3(k+1)(k+2).  Show this is divisible exactly as you have done, and hence complete the stage (2) step.  Essentially it's the same proof but backwards.  I'm sure either way round is acceptable.  Well done!

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#3 2018-02-01 01:10:56

Alg Num Theory
Member
Registered: 2017-11-24
Posts: 338
Website

Re: [ASK] Prove Using Induction

I don’t think induction is the way to go about proving this. Better to argue directly as follows.

The product is clearly divisible by 2, since at least one of n, n+1, n+2 is even (you can’t have three consecutive odd integers).

Also, any three consecutive integers must contain a multiple of 3. One way to prove this is to reduce mod 3:

  • If n ≡ 0 (mod 3) then n is divisible by 3.

    If n ≡ 1 (mod 3) then n+2 is divisible by 3.

    If n ≡ 2 (mod 3) then n+1 is divisible by 3.

Since n , n+1, n+2 contain a multiple of 2 and 3, and gcd(2,3) = 1, their product is divisible by 2×3 = 6.

Offline

#4 2018-02-01 04:10:50

Monox D. I-Fly
Member
From: Indonesia
Registered: 2015-12-02
Posts: 1,268

Re: [ASK] Prove Using Induction

bob bundy wrote:

As an alternative, you could start by saying let's consider the expression  k(k+1)(k+2) + 3(k+1)(k+2).  Show this is divisible exactly as you have done, and hence complete the stage (2) step.  Essentially it's the same proof but backwards.  I'm sure either way round is acceptable.  Well done!

Errr... Can you elaborate more about it? It's a bit incomprehendsible for me, adding some lines wouldn't hurt.


Actually I never watch Star Wars and not interested in it anyway, but I choose a Yoda card as my avatar in honor of our great friend bobbym who has passed away. May his adventurous soul rest in peace at heaven.

Offline

#5 2018-02-01 07:00:47

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,398

Re: [ASK] Prove Using Induction

Nothing hard.  I must have explained it badly.

step (2): consider the expression k(k+1)(k+2) + 3(k+1)(k+2) = term 1 + term 2

The first term is divisible by 6 by (inductive) assumption.

The second term has 3 as a factor and 2 also as either k+1 or k+2 must be even.

So it also is divisible by 6.

Adding term 1 to term 2 must therefore be divisible by 6.

But the expression simplifies to (k+1)(k+2)(k+3) completing the induction step.

As you can see there is nothing original in this; it is just your proof written backwards.

Alg Num Theory: Hi.  I agree but the title of the post seems to require a proof by induction.  Perhaps it's in that chapter as an exercise in induction.

I once did some A level marking and one question told candidates to use a certain method.  The chief examiner ordered us to give no marks if any other method was used!!!

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#6 2018-02-01 12:50:46

Monox D. I-Fly
Member
From: Indonesia
Registered: 2015-12-02
Posts: 1,268

Re: [ASK] Prove Using Induction

bob bundy wrote:

Nothing hard.  I must have explained it badly.

step (2): consider the expression k(k+1)(k+2) + 3(k+1)(k+2) = term 1 + term 2

The first term is divisible by 6 by (inductive) assumption.

The second term has 3 as a factor and 2 also as either k+1 or k+2 must be even.

So it also is divisible by 6.

Adding term 1 to term 2 must therefore be divisible by 6.

But the expression simplifies to (k+1)(k+2)(k+3) completing the induction step.

As you can see there is nothing original in this; it is just your proof written backwards.

I mean, I have used that method in the first post, but I don't know whether it is valid or not if the instruction specifically asked me to use induction.


Actually I never watch Star Wars and not interested in it anyway, but I choose a Yoda card as my avatar in honor of our great friend bobbym who has passed away. May his adventurous soul rest in peace at heaven.

Offline

#7 2018-02-01 22:22:19

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,398

Re: [ASK] Prove Using Induction

I think it is valid.  Compare with a standard induction proof for the sum of n integers.

I think the formula is sum= n(n+1)/2

step 1:  when n = 1 , sum = 1x2/2 = 1

So the formula works for n = 1

step 2: assume it is correct for n = k

sum of k integers = k(k+1)/2

The next integer is k+1.

So the sum of k+1 integers is sum of k integers + k+1 = k(k+1)/2 + k+1 = (k+1)(k/2 + 1) = (k+1)(k+2)/2

This is the same formula with k replaced by k+1, so if the formula works for n=k then it works for n = k+1

The bit in bold characters is just algebra.  So it is normal to include some algebraic steps in the proof.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

Board footer

Powered by FluxBB