I'm stuck on trying to prove this Recursion Relation through mathematical induction:
We were given:
$cS(n−1)^2$
and was asked to find out the closed-form equation via the expand, guess, and verify method. Through that, I was able to get:
$S(n) = c^{2^{k}-1} \cdot S(n-k) \cdot 2^{k}$
and by substituting $k= n-1$, I got:
$S(n) = c^{2^{n-1}-1} \cdot S(n-(n-1)) \cdot 2^{n-1}$
Which is just:
$S(n) = c^{2^{n-1}-1} \cdot S(1) \cdot 2^{n-1}$
The base case is true
Induction Step:
$S(n+1) = c^{2^n-1} \cdot S(1) \cdot 2^n$ => What I have to prove
$S(n+1) = cS(n)^2 = c[c^{2^{n-1}-1} S(1) 2^{n-1}]^2$
I'm not quite sure how I would begin to square the above equation; I feel as though it's really simple and I'm going to keep trying to work out it as I post this, but any hints to get started would definitely be appreciated.
Hint (using $S_n$ for $S(n)$): write out the first few consecutive terms, then telescope all the way down to $S_1$ once the pattern emerges.
$$ \begin{align} S_n & = c \cdot S_{n-1}^2 = c^{2-1} \cdot S_{n-1}^{2^1}\\ & = c \cdot \big(c \cdot S_{n-2}^2\big)^2 = c^{2^2-1} \cdot S_{n-2}^{2^2} = \\ & = c^{2^2-1} \cdot \big(c \cdot S_{n-3}^2\big)^{2^2} = c^{2^3-1} \cdot S_{n-3}^{2^3} = \\ & \cdots \\ & = c^{2^{n-1}-1} \cdot S_{1}^{2^{n-1}} \end{align} $$
To formally justify the "telescoping", prove by induction that:
$$ \begin{align} S_{n+1} = c^{2^{n}-1} \cdot S_{1}^{2^{n}} \end{align} $$