## Problem 1

Let $a_{n}$ be the number written with $2^{n}$ nines. For example, $a_{0}=9, a_{1}=99, a_{2}=9999$. Let $b_{n}=\Pi_{0}{ }^{n} a_{i}$. Find the sum of the digits of $b_{n}$.


## Solution

Answer: $9 \cdot 2^{\text {n }}$.

Induction on $\mathrm{n}$. We have $\mathrm{b}_{0}=9$, digit sum 9 , and $\mathrm{b}_{1}=891$, digit sum 18 , so the result is true for $\mathrm{n}=0$ and 1 . Assume it is true for n-1. Obviously $\mathrm{a}_{\mathrm{n}}<10$ to the power of $2^{\mathrm{n}}$, so $\mathrm{b}_{\mathrm{n}-1}<10$ to the power of $\left(1+2+2^{2}+\ldots+\right.$ $\left.2^{n-1}\right)<10$ to the power of $2^{n}$. Now $b_{n}=b_{n-1} 10^{N}-b_{n-1}$, where $N=2^{n}$. But $b_{n-1}<10^{N}$, so $b_{n}=\left(b_{n-1}-1\right) 10^{N}+$ $\left(10^{N}-b_{n-1}\right)$ and the digit sum of $b_{n}$ is just the digit sum of $\left(b_{n-1}-1\right) 10^{N}$ plus the digit sum of $\left(10^{N}-b_{n-1}\right)$.

Now $b_{n-1}$ is odd and so its last digit is non-zero, so the digit sum of $b_{n-1}-1$ is one less than the digit sum of $b_{n-}$ 1, and hence is $9 \cdot 2^{n-1}-1$. Multiplying by $10^{N}$ does not change the digit sum. $\left(10^{N}-1\right)-b_{n-1}$ has $2^{n}$ digits, each 9 minus the corresponding digit of $b_{n-1}$, so its digit sum is $9 \cdot 2^{n}-9 \cdot 2^{n-1} \cdot b_{n-1}$ is odd, so its last digit is not 0 and hence the last digit of $\left(10^{N}-1\right)-b_{n-1}$ is not 9 . So the digit sum of $10^{N}-b_{n-1}$ is $9 \cdot 2^{n}-9 \cdot 2^{n-1}+1$. Hence $b_{n}$ has digit sum $\left(9 \cdot 2^{n-1}-1\right)+\left(9 \cdot 2^{n}-9 \cdot 2^{n-1}+1\right)=9 \cdot 2^{n}$.

