1
$\begingroup$

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

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

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

$\endgroup$
4
  • 1
    $\begingroup$ Because $2^{k+1} >2^k+1$ for $k>0$ $\endgroup$ – Mason Oct 2 '19 at 19:56
  • $\begingroup$ @Mason Yes of course, that's why in short. $\endgroup$ – user Oct 2 '19 at 19:57
  • $\begingroup$ 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$? $\endgroup$ – Harold Smith Oct 2 '19 at 20:19
  • $\begingroup$ @HarrySmith Ops sorry, you ar eright, I fox that. $\endgroup$ – user Oct 2 '19 at 20:22
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.