HMMT-Nov 2018 thm, Problem 5

Lil Wayne, the rain god, determines the weather. If Lil Wayne makes it rain on any given day, the probability that he makes it rain the next day is $75 \%$. If Lil Wayne doesn't make it rain on one day, the probability that he makes it rain the next day is $25 \%$. He decides not to make it rain today. Find the smallest positive integer $n$ such that the probability that Lil Wayne makes it rain $n$ days from today is greater than $49.9 \%$.

Solution: Let $p_{n}$ denote the probability that Lil Wayne makes it rain $n$ days from today. We have $p_{0}=0$ and \[ p_{n+1}=\frac{3}{4} p_{n}+\frac{1}{4}\left(1-p_{n}\right)=\frac{1}{4}+\frac{1}{2} p_{n} \] This can be written as \[ p_{n+1}-\frac{1}{2}=\frac{1}{2}\left(p_{n}-\frac{1}{2}\right) \] and we can check that the solution of this recurrence is \[ p_{n}=\frac{1}{2}-\frac{1}{2^{n+1}} \] We want $\frac{1}{2^{n+1}}<\frac{1}{1000}$, which first occurs when $n=9$. $\fbox{9}$.

Answer: 9