The average time for a spider to reach the top of a cliff 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 :(
 A: The recurrence for the expectation $a_n$ is
$$
a_k=1+\frac13a_{k-1}+\frac23a_{k+1}\;,
$$
with solution $a_k=c_1+c_22^{-k}-3k$. The boundary conditions are $a_0=0$ and $a_n=1+a_{n-1}$, yielding $c_1+c_2=0$ and $c_22^{-n}-3n=1+c_22^{-(n-1)}-3(n-1)$. Solving the second equation for $c_2$ yields $c_2=-4\cdot2^n$, so $a_k=4\cdot2^n\left(1-2^{-k}\right)-3k$ and $a_n=4\cdot\left(2^n-1\right)-3n$.
A: The recurrence relation can be thought as,
Tn = (1/3)(Tn-1 + 1) + (2/3)(Tn-1 + 1 + Tn - Tn-2)
On further simplification
Tn = 3* Tn-1 - 2*Tn-2 + 3
The intuition is: To find expected number of steps to reach nth inch we first need to reach (n-1)th inch now after reaching (n-1)th inch we need 1 more step with probability 1/3 to complete nth inch this "move forward" step incurred additional cost of 1 otherwise with probability 2/3 we have to move 1 inch behind from (n-1)th inch so this "move back" step incurred additional cost 1 so we are now at (n-2)th inch, expected number of steps to complete n inches is Tn and expected number of steps to complete n-2 inches is Tn-2 so after reaching (n-2)th inch we require Tn-Tn-2 additional cost to complete n inches.
Hope this helps
