okie dokie, let's see where we get with this. i suppose you know the method of induction, so i won't explain it. let's just jump in

Let : " for all "

Clearly is true, since

So assume holds for some . That is, we can write for some . We show

Now is . We must show that this is divisible by 9, provided is.

Note that:

Since is an integer, we have that , as desired.

Thus, holds for all by induction.

QED