This question may smell like my older question http://math.stackexchange.com/questions/1778/a-probability-game, but this time my intentions are different.
The above problem came from my friend. Or so I thought, it really came from me incorrectly remembering his problem. The problem he actually gave me was:
Suppose you start with 1 dollar and flip a weighted coin. With probability 3/4 (call this heads) you win a dollar and with probability 1/4 (call this tails) you lose a dollar. What is the probability you eventually run out of money? (Suppose the house has as many dollar bills as needed).
I know how to solve this problem in the following way: First observe the number of tails must equal the number of heads plus one. If a string of Hs and Ts satisfy this property, call it Good. Now we want to count the number of Good strings that don't have Good proper prefixes. For a string of length 2n-1 this is just the nth Catalan number. Now we just take the appropriate summation and we arrive at the probability we eventually run out of money which turns out to be 1/3.
Now when my friend told me this problem, he said he was able to apply a clever trick and solve it almost instantly. The thing is, he doesn't remember how he did it. He says he vaguely remembers using a recurrence relation and then telescoping a sum. (Which sounds very plausible)
So can you come up with a short and sweet solution?
On a side note, I am aware my title is poor at best. If you can think of a better one, please let me know.