$a_1=1$, $a_{n+1} = 3 a_n^2$.
Prove for all positive integers, $a_n\leq{3^{2^n}}$ using induction.
My work so far:
Base case is true (1 < 9)
Induction Hypothesis: $a_k\leq{3^{2^k}}$
IS: prove that n = k+1 is true
I'm stuck because I just can't seem to prove the induction step. Any help is appreciated.
Best Answer
We need to show the stronger condition
$$a_n\leq{3^{2^n-1}}(\leq{3^{2^n}})$$
and therefore assuming as Induction Hypothesis $a_k\leq{3^{2^k-1}}$ we have
$$a_{k+1}=3a_k^2\stackrel{Ind. Hyp.}\leq 3\cdot (3^{2^{k}-1})^2={3^{2^{k+1}-1}}$$
Refer also to the related