If induction is the only tool you have then it’s ok. What you really want is modular arithmetic. If you don’t have modular arithmetic then pricing it directly i

If induction is the only tool you have then it’s ok. What you really want is modular arithmetic. If you don’t have modular arithmetic then pricing it directly is hard: n = Sum(d_k 10^k) Let S = sum of digits = Sum(d_k) n - S = Sum(d_k (10^k - 1)) But (10^k - 1) = ((9 + 1)^k - 1) = ((1 + k*9 + (2 choose k)*9^2 + ... + 9^k) - 1) by binomial expansion so is divisible by 9. Therefore n - S is divisible by 9, so n is divisible by 9 iff S is. The same is true when you replace divisibility by 9 with divisibility by 3. I remember being asked this in an interview for a place at university and I solved it by induction (which was all I had) and was then shown this direct proof.