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

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

Hello, delpin!

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

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 is not divisible by 6.

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