HMMT 2011 U11

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?