Rosencrantz and Guildenstern play a game in which they repeatedly flip a fair coin. Let $a_{1}=4$, $a_{2}=3$, and $a_{n}=a_{n-1}+a_{n-2}$ for all $n \geq 3$. On the $n$th flip, if the coin is heads, Rosencrantz pays Guildenstern $a_{n}$ dollars, and, if the coin is tails, Guildenstern pays Rosencrantz $a_{n}$ dollars. If play continues for 2010 turns, what is the probability that Rosencrantz ends up with more money than he started with?
Since Rosencrantz and Guildenstern have an equal chance of winning each toss, both have the same probability of ending up with a positive amount of money. Let $x$ denote the probability that they both end up with zero dollars. We wish to find $\frac{1-x}{2}$. We have $x$ is equal to the probability that \[ s_{2010}:=i_{1} a_{1}+i_{2} a_{2}+\cdots i_{2010} a_{2010}=0 \] where $i_{n}$ has an equal probability of being either 1 or -1 . We claim that $s_{2010}=0$ if and only if $i_{3 n}=-i_{3 n-1}=-i_{3 n-2}$ for all $n \leq 670$. We start with the following lemma. Lemma. We have $a_{n}>\sum_{k=1}^{n-3} a_{k}$ for all $n \geq 4$. Proof: For the case $n=4, a_{4}=a_{3}+a_{2}=2 a_{2}+a_{1}>a_{1}$. In case $n>4$, we have \[ a_{n}=a_{n-2}+a_{n-1}>a_{n-2}+\sum_{k=1}^{n-4} a_{k}=a_{n-4}+\sum_{k=1}^{n-3} a_{k}>\sum_{k=1}^{n-3} a_{k} \] It suffices to show that $s_{3 n}=0$ only if $i_{3 k}=-i_{3 k-1}=-i_{3 k-2}$ for all $k \leq n$. The triangle inequality implies the following: \[ \begin{aligned} & 0 \leq|| i_{3 n-2} a_{3 n-2}+s_{3 n-3}|-| i_{3 n-1} a_{3 n-1}+i_{3 n} a_{3 n}|| \leq\left|s_{3 n}\right|=0 \\ & 0 \leq|| i_{3 n-1} a_{3 n-1}+s_{3 n-3}|-| i_{3 n-2} a_{3 n-2}+i_{3 n} a_{3 n}|| \leq\left|s_{3 n}\right|=0 \end{aligned} \] By the lemma, we have \[ \begin{array}{rll} a_{3 n-2}+\sum_{k=1}^{3 n-3} a_{k}<a_{3 n-2}+a_{3 n} & < & a_{3 n-1}+a_{3 n} \\ a_{3 n-1}+\sum_{k=1}^{3 n-3} a_{k}<a_{3 n-1}+a_{3 n-3}+a_{3 n-4}+a_{3 n-2} & = & a_{3 n-2}+a_{3 n} \end{array} \] $i_{3 n}=i_{3 n-1}$ implies $\left|a_{3 n-2}+\sum_{k=1}^{3 n-3} a_{k}\right|<\left|i_{3 n-1} a_{3 n-1}+i_{3 n} a_{3 n}\right|$ and $i_{3 n}=i_{3 n-2}$ implies $\mid a_{3 n-1}+$ $\sum_{k=1}^{3 n-3} a_{k}|<| i_{3 n-2} a_{3 n-2}+i_{3 n} a_{3 n} \mid$, which are both contradictions; therefore, we must have $i_{3 n}=-i_{3 n-1}$ and $i_{3 n}=-i_{3 n-2}$. The probability that $i_{3 n}=-i_{3 n-1}=-i_{3 n-2}$ is $\frac{1}{4}$, so $x=\left(\frac{1}{4}\right)^{670}=\frac{1}{2^{1340}}$, and $\frac{1-x}{2}=\frac{1}{2}-\frac{1}{2^{1341}}$. $\fbox{\frac{1}{2}-\frac{1}{2^{1341}}}$.