Proving something about the sequence of powers of 3 mod 10. Oh boy 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...
 A: 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$ :


*

*For $k=3$ this is true $3^{100}=1\mod 1000$

*Assume that $3^{10^{k-1}}=1\mod 10^k$ or equivalently :$3^{10^{k-1}}=1+q. 10^k$ now we have:
$$3^{10^{k}}= (3^{10^{k-1}})^{10}=(1+q10^k)^{10}=1+10 (q.10^k)+45 (q.10^k)^2+\cdots $$


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).
