[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Let [math]b_k[/math] denote the expected number of steps to reach [math]n[/math] from [math]n-k[/math], in the process described in Exercise.

• Define [math]b_0 = 0[/math]. Show that for [math]k \gt 0[/math], we have
  [[math]] b_k = 1 + \frac 1k \bigl(b_{k-1} + b_{k-2} + \cdots + b_0\bigr)\ . [[/math]]
• Let
  [[math]] f(x) = b_0 + b_1 x + b_2 x^2 + \cdots\ . [[/math]]
  Using the recursion in part (a), show that [math]f(x)[/math] satisfies the differential equation
  [[math]] (1-x)^2 y' - (1-x) y - 1 = 0\ . [[/math]]
• Show that the general solution of the differential equation in part (b) is
  [[math]] y = \frac{-\log(1-x)}{1-x} + \frac c{1-x}\ , [[/math]]
  where [math]c[/math] is a constant.
• Use part (c) to show that
  [[math]] b_k = 1 + \frac 12 + \frac 13 + \cdots + \frac 1k\ . [[/math]]