## Problem of the Day #206: Climbing Stairs
*October 11, 2011*

*Posted by Billy in : potd , trackback*

Albert is climbing a staircase with $n$ stairs. He is currently at the bottom of the stairs. For any step, let $m$ be the number of steps above him until the top. Each turn, Albert has a $\frac{1}{2^k}$ chance of going up $k$ stairs and a $\frac{1}{2^m}$ chance of staying on the same step. What is the expected number of turns it will take Albert to reach the top of the stairs?

## Comments»

no comments yet - be the first?