N Bottles of Beer

Let’s solve a more general version of the problem. Suppose there are $n$ bottles of beer, and there is a probability $p$ of forgetting at every verse. Define $E_k$ to be the expected number of additional verses we will sing assuming we are currently singing verse $k$. Our task is to solve for $E_1$. Since at each verse, we have a probability $p$ of returning to verse $1$, and a probability $1-p$ of moving to the next verse, we can write:

\begin{align}
E_1 &= 1 + p E_1 + (1-p) E_2 \\
E_2 &= 1 + p E_1 + (1-p) E_3 \\
&\;\vdots \\
E_{n-2} &= 1 + p E_1 + (1-p) E_{n-1} \\
E_{n-1} &= 1 + p E_1 + (1-p)
\end{align}In the last equation, we substituted $E_n=1$, since if we start on the last verse, we will sing that verse and the song will end. We have a system of $n-1$ equations in the unknowns $E_1,E_2,\dots,E_{n-1}$ and our task is to solve for $E_1$.

The obvious approach is to use back-substitution: solve for $E_{n-1}$ in the last equation, substitute into the previous equation to solve for $E_{n-2}$, and continue in this fashion until we reach the first equation. However this leads to a complicated formula. A more efficient approach is to multiply the $k^\text{th}$ equation by $(1-p)^{k-1}$, and obtain:

\begin{align}
E_1 &= 1 + p E_1 + (1-p) E_2 \\
(1-p)E_2 &= (1-p)(1 + p E_1) + (1-p)^2 E_3 \\
(1-p)^2E_3 &= (1-p)^2(1 + p E_1) + (1-p)^3 E_4 \\
&\;\vdots \\
(1-p)^{n-3}E_{n-2} &= (1-p)^{n-3}(1 + p E_1) + (1-p)^{n-2} E_{n-1} \\
(1-p)^{n-2}E_{n-1} &= (1-p)^{n-2}(1 + p E_1) + (1-p)^{n-1} E_n
\end{align}We can get all the terms involving $E_2,\dots,E_{n-1}$ to cancel if we add all these equations together. This yields:

\begin{align}
E_1 &= (1 + p E_1)\sum_{k=0}^{n-2} (1-p)^{k} + (1-p)^{n-1} \\
&= (1+ p E_1) \frac{1-(1-p)^{n-1}}{p} + (1-p)^{n-1} \\
&= \frac{1-(1-p)^{n-1}+p(1-p)^{n-1}}{p} + \bigl(1-(1-p)^{n-1}\bigr)E_1 \\
&= \frac{1-(1-p)^{n}}{p} + \bigl(1-(1-p)^{n-1}\bigr)E_1
\end{align}Now solve for $E_1$ and obtain

$\displaystyle
E_1 = \frac{1-(1-p)^{n}}{p(1-p)^{n-1}}
$

As a simple sanity check, if $n=1$, we obtain $E_1=1$ as we should. It’s also possible to check that if $p\to 0$, we get $E_1\to n$. The problem asks what happens to the ratio $E_1/n$ if we set $p=1/n$ and $n$ is very large. We can write this as

\begin{align}
\lim_{n\to\infty}\left.\frac{E_1}{n}\right|_{p=\frac{1}{n}} &= \lim_{n\to\infty} \frac{1}{n}\frac{1-\left(1-\tfrac{1}{n}\right)^{n}}{\tfrac{1}{n}\left(1-\tfrac{1}{n}\right)^{n-1}} \\
&= \lim_{n\to\infty} \frac{1-\left(1-\tfrac{1}{n}\right)^{n}}{\left(1-\tfrac{1}{n}\right)^{n-1}} \\
&= \frac{1-e^{-1}}{e^{-1}} \\
&= e-1 \\
&\approx 1.71828
\end{align}In the second-last step, we used the well-known fact that $\lim_{n\to\infty} \left(1+\frac{x}{n}\right)^{n} = e^x$, which implies that $\lim_{n\to\infty} \left(1-\frac{1}{n}\right)^{n} = e^{-1}$.

We can verify this limit by plotting $\frac{1}{n}E_1$ with $p=\frac{1}{n}$, which yields