Let an be the number written with 2n nines. For example, a0 = 9, a1 = 99, a2 = 9999. Let bn = P0n ai. Find the sum of the digits of bn.
Solution
Answer: 9·2n.
Induction on n. We have b0 = 9, digit sum 9, and b1 = 891, digit sum 18, so the result is true for n = 0 and 1. Assume it is true for n-1. Obviously an < 10 to the power of 2n, so bn-1 < 10 to the power of (1 + 2 + 22 + ... + 2n-1) < 10 to the power of 2n. Now bn = bn-110N - bn-1, where N = 2n. But bn-1 < 10N, so bn = (bn-1 - 1)10N + (10N - bn-1) and the digit sum of bn is just the digit sum of (bn-1 - 1)10N plus the digit sum of (10N - bn-1).
Now bn-1 is odd and so its last digit is non-zero, so the digit sum of bn-1 - 1 is one less than the digit sum of bn-1, and hence is 9·2n-1 - 1. Multiplying by 10N does not change the digit sum. (10N - 1) - bn-1 has 2n digits, each 9 minus the corresponding digit of bn-1, so its digit sum is 9·2n - 9·2n-1. bn-1 is odd, so its last digit is not 0 and hence the last digit of (10N - 1) - bn-1 is not 9. So the digit sum of 10N - bn-1 is 9·2n - 9·2n-1 + 1. Hence bn has digit sum (9·2n-1 - 1) + (9·2n - 9·2n-1 + 1) = 9·2n.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002