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.
Since is an integer, we have that , as desired.
Thus, holds for all by induction.