3
$\begingroup$

Possible Duplicate:
Solving the recurrence $t(n)=(t(n-1))^2 + 1$

Show that the number of binary trees of height less than or equal to $n$ is given by the recurrence

\begin{align*} T(1) & = 1, \\ T(n) & = T(n- 1)^2 + 1. \end{align*}

Show that $T(n) = k^{2^n}$ for some constant $k$. What is the value of $k$?

I'm really lost, how can start to solve it?

  • 2
    You might want to merge this question with [the other one](http://math.stackexchange.com/q/171731).2012-07-17

0 Answers 0