0

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.

Seals
  • 1

1 Answers1

0

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?

MQStacked
  • 1