How prove that for a given integer $k$ there exist infinitely many $n$ such that $S(2^n+n)+k<S(2^n)$?

Let $S(n)$ be the sum of digits of $n$. How prove that for a given integer $k$ there exist infinitely many $n$ such that $S(2^n+n)+k<S(2^n)$?

I have modified this problem: Denote by $S(a)$ the sum of the digits in the decimal representation of $a$. Prove that there are infinitely many $n\in \mathbb{Z_{+}}$ such that: ${S(2^{n}+n})<S(2^{n})$.

This problem is also true that for every integer $k$ there exist infinitely many $n$ satisfying $S(2^n+n)+k<S(2^n)$.

• $2^{4k}$ ends in a $6$, so I expect $S(2^{100\dots004}+100\dots004)<S(2^{100\dots004})$. – Gerry Myerson Jul 20 '15 at 7:17
• @GerryMyerson This idea works for any base (instead 2) that is is not divisible by 10. – grizzly Jul 20 '15 at 8:59
• Deleting my earlier comment. The idea was to make the remainder of $2^n$ modulo a power of ten as large as possible so that $2^n$ and $2^n+n$ would straddle a multiple of $10^k$. Basically a lot of 9s near the end of $2^n$ and a lot of zeros in $2^n+n$. We can reach the remainder $10^k-2^k$ when $n=2\cdot 5^{k-1}+k$, but that $n$ is too large in comparison to $10^k$ for the trivial estimates for $S(2^n), S(2^n+n)$ to give what is needed (the number of 0s in the bigger number is not high enough. Gerry's idea is more promising. – Jyrki Lahtonen Jul 20 '15 at 11:22