I've been working on some recursive sequences for my Discrete class. I've understood most of them, but I've come to a new question which I'm confused about.
A sequence $C_{0}$, $C_{1}$, $C_{2}$ is defined by letting $C_{0}=3$ and $C_{k}=(C_{k-1})^{2}$ $\forall$ $\mathbb{Z}$ $k\geqslant 1$. Show that $C_{n}=3^{2^{n}}$ $\forall$ $\mathbb{Z}$ $n\geqslant 0$.
I am not completely sure where to start on this. Do we solve for $P(n)$ using the k equation?
$i.e.$ $C_{n}=(C_{n-1})^{2} \overset{\underset{\mathrm{def}}{?}}{=} C_{n}=3^{2^{n}}$
I am not completely sure how to start the problem, but I think it should be relatively simple once I have some direction on what exactly I need to be doing.
You've got the right idea. Here's what it might look like with a few more words included for readability.
Base case: For $n = 0$, $$ C_0 = 3^{2^0} = 3^1 = 3. $$ So, the formula holds in this case.
Induction step: Suppose that formula holds for $n = k - 1$ (where $k \ge 1$): $$ C_{k - 1} = 3^{2^{k - 1}} $$ Now, use the recursive formula to establish the formula $n = k$: $$ \begin{align} C_k &= \left( C_{k-1} \right)^2 \\ &= \left( 3^{2^{k - 1}} \right)^2 \\ &= 3^{2^{k - 1} \cdot 2} \\ &= 3^{2^k}. \end{align} $$ Bam. You have shown that $C_n = 3^{2^n}$ for all $n \ge 0$.