Monday, 19 August 2013

Solving a recurrence for a probability?

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