Solving a recurrence for a probability?
I came across the following recurrence relation when exploring properties
of a certain type of randomized perfect binary tree:
$$ T(0) = \frac{1}{2} $$ $$ T(k + 1) = 1 - T(k)^2 $$
I have never encountered a recurrence like this one before (most
recurrences I know of come from the analysis of recursive algorithms or
data structures, which rarely have squared terms arise). Is there a
standard technique for solving recurrences of this sort? If so, how can I
use them to solve this recurrence?
Thanks!
No comments:
Post a Comment