I am trying to find a closed form for S(n), where $$ S(n) = \begin{cases} 1 & n = 0\\ (S(n-1))^2 + 2(n-1) & n>0 \end{cases} $$
How can I go about solving this with repeated substitution? When I try the substitution technique, I don’t see any obvious solution for the closed form. Help would be really appreciated.
Let $T(n) = S(n) + 1$
Then $T(n) = (S(n-1))^2 + 2S(n-1) + 1) = (S(n-1)+1)^2$
Using substitution you end up with $T(n) = (S(n-k)+1)^{2^{k}}$ as our assumption.
With $S(0) = 1, n - k = 0 \implies k = n$ then:
$T(n) = (S(n-n) + 1)^{2^{n}} = 2^{2^{n}}$
$T(n) = S(n) + 1 \implies S(n) = 2^{2^{n}} - 1$
A proof by induction follows easily.
I'm only a little cruel for answering our assignment question after it's due right?