1

I have the recursive function

$R(0) = 2$

$R(n) = \left(R(n-1)\right)^{2}$

And I found the non-recursive version of it

$P(n) = 2^{2^{n}}$

How do I prove they are the same through induction? I tried making $n = k + 1$ but got stuck on the R function

Edit: Changed the 3s to 2s

Carlos Melo
  • 13

1 Answers1

0

For the base case, $$R(0) = 2 = 2^1 = 2^{2^0} = P(0).$$ For the inductive case, assume that $R(n)=2^{2^n}$. We just need to prove that $R(n+1)=P(n+1)$. \begin{align*} R(n+1) &= (R(n+1-1))^2 \\ &= (R(n))^2 \\ &= (2^{2^n})^2\quad(\text{by the induction hypothesis}) \\ &= 2^{2^n\cdot2} \\ &= 2^{2^{n+1}} \\ &= P(n+1). \end{align*}

Kainoa B
  • 171