## Green Induction Recursive Proof that carry less than 2 in addition of two numbers

We consider the addition of two numbers using place value in a tens unit system.

The ones place is 10^0 so we call it the zero exponent place.

If the carry out of a place is less than 2, we call the place green.

Lemma:  The ones place is green.

Proof

Let a, b be the two digits.

a <= 9

b <= 9

a+b <= 18

So the carry out is 0 or 1, which is less than 2.  So the ones place is green.

Lemma If a place is green, the next next place is green.

Proof

If a place is green, the carry out is at most 1.  Call the carry c.

Let a, b be the two digits in the next place.  We add a,b, and c.

a <= 9

b <= 9

a+b <= 18

c <= 1

a+b + c < 19

Thus the carry out of the next place is 0 or 1.  So it is less than 2.  Thus the next place is green.

Lemma:  All places are green.

Proof.

We have shown the first place is green. We have shown if a place is green, the next place is green.   By green induction, all places are green.