the limit when n goes to infinity in recurrence relation

Question

in this equation I don't know how to calculate the limit of $nP(n)$

$$P(n)=P(n-1)\bigg(1-\bigg(\dfrac{1}{2}\bigg)P(n-1)\bigg)$$ $$P(0)=1$$

I thought of just expand until I catch some co-relation but I failed.

Answer 1

I claim that $\lim_{n\to\infty} nP(n) = 2$.

Define $R(n)=1/P(n)$, so that $R(0)=1$ and the recursive relation can be written (after some rearrangement) in the form $$ R(n)=R(n-1) + \frac12 + \frac1{4R(n-1)-2}. $$ From this one can easily show that $R(n)\ge R(n-1) + \frac12$ and hence $R(n) \ge 1+\frac n2$ for all $n$, and then that $$ R(n) \le R(n-1) + \frac12 + \frac1{2n+2}, $$ for all $n$, which implies that $$ R(n) \le 1 + \frac n2 + \sum_{k=1}^n \frac1{2k+2} = \frac n2+O(\log n). $$ Together these inequalities show that $\lim_{n\to\infty} R(n)/n = \frac12$, and so $\lim_{n\to\infty} nP(n) = \lim_{n\to\infty} n/R(n) = 2$.