I am studying stochastic processes using An Introduction to Stochastic Modeling by Pinsky and Karlin. I stuck on this question 3.4.18 in Chapter 3. I would really appreciate if someone could help me with it! Here is the question:
A well-disciplined man, who smokes exactly one half of a cigar each day, buys a box containing $N$ cigars. He cuts a cigar in half, smokes half, and returns the other half to the box. In general, on a day in which his cigar box contains $w$ whole cigars and $h$ half cigars, he will pick one of the $w + h$ smokes at random, each whole and half cigar being equally likely, and if it is a half cigar, he smokes it. If it is a whole cigar, he cuts it in half, smokes one piece, and returns the other to the box. What is the expected value of $T$, the day on which the last whole cigar is selected from the box?
The textbook provides a hint:
Let $X_n$ be the number of whole cigars in the box after the $n$th smoke. Then $X_n$ is a Markov chain whose transition probabilities vary with $n$. Define $v_n(w) = E[T | X_n = w]$. Use a first-step analysis to develop a recursion for $v_n(w)$ and show that the solution is \begin{equation} v_n(w) = \frac{2Nw + n + 2w}{w + 1} - \sum_{k = 1}^w \frac{1}{k}, \end{equation} whence \begin{equation} E[T] = v_0(N) = 2N - \sum_{k = 1}^N \frac{1}{k}. \end{equation}
So far, what I have done is the following:
According to the hint, $X_n$ is the number of whole cigars in the box after $n$th smoke.
If $X_n = w$, then $X_{n + 1} = w$ or $w - 1$, and \begin{equation} Pr\{X_{n + 1} = w | X_n = w\} = \frac{h}{w + h}, \end{equation} \begin{equation} Pr\{X_{n + 1} = w - 1 | X_n = w\} = \frac{w}{w + h}. \end{equation} Moreover, \begin{equation} v_n(w) = E[T | X_n = w] = E[T | X_{n - 1} = w] \cdot Pr\{X_{n - 1} = w | X_n = w\} + E[T | X_{n + 1} = w - 1] \cdot Pr\{X_{n + 1} = w - 1 | X_n = w\} = \frac{h}{w + h} v_{n + 1}(w) + \frac{w}{w + h} v_{n + 1}(w - 1). \end{equation}
I am not 100% sure whether my steps so far are correct, though I feel they should alright. But I don't know how to proceed next and how to derive the answer. Thanks a lot in advance!