3. calculate the sum of the digits of the number

$$
9 \times 99 \times 9999 \times \cdots \times \underbrace{99 \ldots 99}_{2^{n}}
$$

where the number of nines doubles in each factor.

## 1st solution
We prove the following in general

Lemma 1 Let a be a number with at most m decimal places, so that the last digit of a is not 0. Then the sum of the digits of $\underbrace{99 \ldots 99}_{m} \times$ a is equal to $9 m$.

Proof. Let $a_{m-1} \ldots a_{1} a_{0}$ the decimal representation of $a$ with $a_{0} \neq 0$. The following applies $99 \ldots 99 \times$ $a=10^{m} \cdot a-a$. In the subtraction

![](https://cdn.mathpix.com/cropped/2024_04_28_5c9583348f9286d58572g-03.jpg?height=175&width=1080&top_left_y=235&top_left_x=568)

there is now a carry of 1 at the $m$ last digits. Since this carry is always equal to 1, and since $a_{0}$ does not disappear according to the prerequisite, there are no further carries at the $m+1$-th and thus all subsequent digits. So $b_{0}+a_{0}=$ 10, for $1 \leq k \leq m-1$ $b_{k}+a_{k}=9$, furthermore $b_{m}+1=a_{0}$ and $b_{k}=a_{k-m}$ for $k \geq m+1$. So in total

$$
\sum_{k=0}^{2 m-1} b_{k}=\left(10-a_{0}\right)+\sum_{k=1}^{m-1}\left(9-a_{k}\right)+\left(a_{0}-1\right)+\sum_{k=1}^{m-1} a_{k}=9 m
$$

The number $a=9 \times 99 \times 9999 \times \cdots \times \underbrace{99 \ldots 99}_{2^{n-1}}$ does not end with a zero and is also smaller than $10 \cdot 10^{2} \cdot 10^{4} \cdots 10^{2^{n-1}}=10^{2^{n}-1}$, so it has at most $2^{n}-1$ digits. From the lemma it now follows with $m=2^{n}$ that the sum of digits is equal to $9 \cdot 2^{n}$.