Is it true that for infinitely many values of $n$, the sum of digits of $2^n$ is greater than for $2^{n+1}$? Let $S(n)$ denote the digit sum of the integer $n$, using base $10$.
How to prove that there exist infinitely natural numbers such that $S(2^n)>S(2^{n+1})$? 

Remarks (by Deven Ware): 


*

*This is not true in base $2$, because then the sum of digits is always $1$.

*$S(2^n)$ is never equal to $S(2^{n+1})$ because the powers differ $\bmod 3$.
 A: Expanding on Deven Ware's observation: assuming $S(2^n)$ is eventually nondecreasing, not only would it strictly increase, but we can give a non-trivial lower bound on its rate of growth.
Working mod $3$, for instance, note that if for some $m$, $S(2^m) \equiv 2 \pmod 3$, then $S(2^{m+1}) \equiv 1 \pmod 3$, so if $S(2^{m+1}) > S(2^m)$ then in fact $S(2^{m+1}) \ge S(2^m)+2$.  We can easily see this leads a lower bound of $$S(2^n) \ge \tfrac32 n + O(1),$$ which is stronger than the $n+O(1)$ lower bound one gets from just being strictly increasing.
On the other hand, since $2^n$ has $\frac{\log 2}{\log 10}n + O(1)$ digits, we have an upper bound of $$S(2^n) \le 9\frac{\log 2}{\log 10}n + O(1) < 2.71n + O(1).$$  This doesn't contradict our lower bound of $S(2^n) \ge \tfrac32 n + O(1)$, but look at what happens when we work modulo $9$ instead:
The sequence $\{2^n\}$ cycles modulo $9$ as $1,2,4,8,7,5,1,\ldots$, and $\{S(2^n)\}$ follows exactly the same cycle.  However, if we assume $S(2^n)$ is (eventually) nondecreasing, then starting from any sufficiently large $m$ such that $S(2^m) = 9k+1$, we have the chain of inequalities:
\begin{align}
S(2^{m+1}) &\ge 9k+2, \\
S(2^{m+2}) &\ge 9k+4, \\
S(2^{m+3}) &\ge 9k+8, \\
S(2^{m+4}) &\ge 9k+16, \\
S(S^{m+5}) &\ge 9k+23, \\
S(S^{m+6}) &\ge 9k+28,
\end{align}
which yields a lower bound of $S(2^n) \ge \frac{27}{6} n + O(1) = 4.5n + O(1)$.  This does contradict the upper bound from the number of digits, so indeed $S(2^n)$ must decrease infinitely often.
What homework is this from?  This is actually quite a pretty question, and I'm both pleased and impressed that it can be answered by such elementary methods.
