The following question was asked in an theoretical computer science entrance exam in India:
A spider is at the bottom of a cliff, and is n inches from the top. Every step it takes brings it one inch closer to the top with probability $1/3$, and one inch away from the top with probability $2/3$, unless it is at the bottom in which case, it always gets one inch closer. What is the expected number of steps for the spider to reach the top as a function of $n$?
How do we solve this problem? The recurrence for the expectation seems tricky because of the boundary conditions :(