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