# yet another Mathematical Induction question

Printable View

• Jun 20th 2007, 09:52 PM
delpin
yet another Mathematical Induction question
Prove by mathematical Induction
If two numbers are divisible by 3 then their sum is divisible by 6
Any help is appreciated
• Jun 20th 2007, 11:46 PM
CaptainBlack
Quote:

Originally Posted by delpin
Prove by mathematical Induction
If two numbers are divisible by 3 then their sum is divisible by 6
Any help is appreciated

First a base case:

If a and b are two numbers less than 1 both divisible by 3 then their sum
is divisible by 3, since they are both zero.

Now suppose that for some k>1 that for all pairs of integers

(a,b; 3|a, 3|b, a<=k, b<=k)

implies that 3|(a+b)

Now consider a pair of (u,v;3|u, 3|v, u<=k+1, v<=k+1),

then if u<=k and v<=k; 3|(u+v) by supposition.

If k<u<=k+1, v<=k, then u=u'+3, u'<k, and so 3|(u'+v) which implies 3|(u+v)

If u<=k, k<v<=k+1, then v=v'+3, v'<k, and so 3|(u+v') which implies 3|(u+v)

If k<u<=k+1, k<v<=k+1, then u=u'+3, u'<k, and v=v'+3, v'<k, and so 3|(u'+v') which implies 3|(u+v)

So if for some k>1 that for all pairs of integers (a,b; 3|a, 3|b, a<=k, b<=k) implies that 3|(a+b), then for all pairs of integers (a,b; 3|a, 3|b, a<=k+1, b<=k+1) implies that 3|(a+b). Which with the base case proves by induction
that:

If a and b are two numbers both divisible by 3 then their sum
is divisible by 3

This could probably be made neater by taking n=3 for the base case, and steping from
k to k+3 in the inductive step.

RonL
• Jun 21st 2007, 05:37 PM
Soroban
Hello, delpin!

Is there a typo?
. . The statement isn't true . . .

Quote:

Prove by mathematical induction:
. . If two numbers are divisible by 3, then their sum is divisible by 6.

Counter-example: .6 and 9 are divisible by 3,
. . but $6 + 9 \:=\:15$ is not divisible by 6.

• Jun 21st 2007, 08:15 PM
CaptainBlack
Quote:

Originally Posted by CaptainBlack
First a base case:

If a and b are two numbers less than 1 both divisible by 3 then their sum
is divisible by 3, since they are both zero.

Now suppose that for some k>1 that for all pairs of integers

(a,b; 3|a, 3|b, a<=k, b<=k)

implies that 3|(a+b)

Now consider a pair of (u,v;3|u, 3|v, u<=k+1, v<=k+1),

then if u<=k and v<=k; 3|(u+v) by supposition.

If k<u<=k+1, v<=k, then u=u'+3, u'<k, and so 3|(u'+v) which implies 3|(u+v)

If u<=k, k<v<=k+1, then v=v'+3, v'<k, and so 3|(u+v') which implies 3|(u+v)

If k<u<=k+1, k<v<=k+1, then u=u'+3, u'<k, and v=v'+3, v'<k, and so 3|(u'+v') which implies 3|(u+v)

So if for some k>1 that for all pairs of integers (a,b; 3|a, 3|b, a<=k, b<=k) implies that 3|(a+b), then for all pairs of integers (a,b; 3|a, 3|b, a<=k+1, b<=k+1) implies that 3|(a+b). Which with the base case proves by induction
that:

If a and b are two numbers both divisible by 3 then their sum
is divisible by 3

This could probably be made neater by taking n=3 for the base case, and steping from
k to k+3 in the inductive step.

RonL

Oppsss.. misread the problem, then went and proved something that was
true even though more easiy proven by other methods.

RonL