Given the sequence $t_0=3, t_1=3^3,...$ so that $t_{n+1}=3^{t_n}$, prove
$t_{k+1} \equiv t_k \mod 10^n$ for all integers $n \leq k$
My work so far: I thought it was a pretty obvious case for induction. First though notice that if we prove the statement for $n=k$, it's good for all numbers less, because if $x \equiv y \mod 10^n$, then $x \equiv y \mod 10^{n-1}$ (found by converting it to equation form). Sooo
Given
$t_k \equiv t_{k-1} \mod 10^{k-1}$ for some $k$, then prove
$t_{k+1} \equiv t_k \mod 10^k$
Since the only formula that comes to mind when thinking of powers and mods is Euler's I tried to apply it:
By Euler's,
$t_k = 3^{t_{k-1}}\equiv 3^{t_{k-1} \mod \phi (10^{k})} \mod 10^k$
Oh godddd. If you are wondering about that exponent, just pick the smallest positive value in that mod is what I mean.
I think the trouble with this because of two things: the fact that it's a sequence of powers (and the only formula I know is Euler's and well, yeah that), and because of the difference in mods from the inductive hypothesis to what we want...
So because you started induction, we can assume that $t_k=t_{k-1} \mod 10^{k-1}$ and write $ t_k=t_{k-1}+q.10^{k-1}$ :it suffices to prove that: $$3^{10^{k-1}}=1 \mod 10^k\ \ \ \ (*) $$ (because if we have this : $t_{k+1}=3^{t_k}=3^{t_{k-1}}(3^{10^{k-1}})^q=t_k \mod 10^k$)
The identity $(*)$ is true only for $k\geq 3$ :
And here we just used the expansion of $(1+x)^{10}$ we observe that the rest of terms are higher powers of $10^k$ so they are all divisible by $10^{k+1}$ and we deduce that $$3^{10^{k}}=1 \mod 10^{k+1} $$ Here the proof terminates because we proved the result for $k+1$.
Now we can prove your inequality, we can verify easily it's true up to $k=3$ and then we use induction and $(*)$.
I answered another related question in which I explained why Euler's theorem is weak to prove this sort of statements ( because it depends on a particular number here $3$ and Euler's theorem is more general).