All Tails (Solution)

As a function of $n$, the average number of steps is

$$\frac{n^2+n}{4}$$

Or put another way, if $T_n$ in the $n$th triangular number (1,3,6,10,15,…), then the average number of steps is

$$\frac{T_n}{2}$$