Problem: Define a function $f \colon \NN \to \NN$ by $f(1) = 1$,
$f(n+1) = f(n) + 2^{f(n)}$ for every positive integer $n$.
Prove that $f(1)$, $f(2)$, \dots, $f(3^{2013})$
leave distinct remainders when divided by $3^{2013}$.

Solution: I'll prove by induction on $k \ge 1$ that any $3^k$
consecutive values of $f$ produce distinct residues modulo $3^k$.
The base case $k=1$ is easily checked
($f$ is always odd, hence $f$ cycles $1$, $0$, $2$ mod $3$).

For the inductive step, assume it's true for $k$.
Note that $2^\bullet \pmod{3^{k+1}}$ cycles every $2 \cdot 3^k$
so we look at the outputs of $f$ modulo $2 \cdot 3^k$.
\begin{claim*}
  We have
  \[ \{ f(n), f(n+1), \dots, f(n+3^k-1) \} \pmod{2 \cdot 3^k} \]
  is a permutation
  \[ \{ 1, 3, \dots, 2 \cdot 3^k-1 \} \pmod{2 \cdot 3^k}. \]
\end{claim*}
\begin{proof}
  The $f$-values were given to be distinct modulo $3^k$, and $f$ is always odd.
\end{proof}
Thus, we conclude that
\[ \{ 2^{f(n)}, 2^{f(n+1)}, \dots, 2^{f(n+3^k-1)}\} \pmod{3^{k+1}} \]
is a permutation of
\[ \{ 2^{1}, 2^{3}, \dots, 2^{2 \cdot 3^k - 1}\} \pmod{3^{k+1}} \]
and so
\begin{align*}
  f(n+3^k) - f(n)
  &= 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)} \pmod{3^{k+1}} \\
  &\equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} \pmod{3^{k+1}} \\
  &= 2 \cdot \frac{4^{3^k}-1}{4-1}.
\end{align*}
Hence
\[
  f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}}
  \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1}
\]
noting that $C$ does not depend on $n$. Exponent lifting gives $\nu_3(C) = k$
hence $f(n)$, $f(n+3^k)$, $f(n+2\cdot3^k)$ differ mod $3^{k+1}$ for all $n$,
and the inductive hypothesis now solves the problem.