# Prove sequence using induction

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

• square and multiply by 3 on both sides:$$a_{k+1}=3a_k^2\leq 3^{2^{k+1}+1}$$ – user645636 Oct 2 '19 at 19:55
• @RoddyMacPhee but the induction step is prove $a_{k+1}\leq3^{2^{k+1}}$ – Harold Smith Oct 2 '19 at 20:00

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

• Because $2^{k+1} >2^k+1$ for $k>0$ – Mason Oct 2 '19 at 19:56
• @Mason Yes of course, that's why in short. – user Oct 2 '19 at 19:57
• I don't understand how you got $3(a_k)^2\leq3\cdot{3^{2^k}}$ using the IH. What happened to the squared on $3(a_k)^2$? – Harold Smith Oct 2 '19 at 20:19
• @HarrySmith Ops sorry, you ar eright, I fox that. – user Oct 2 '19 at 20:22

Induction proves $$a_n=3^{2^n-1}$$, which implies the inequality.