How does the author find $M_n(p)$ in the Toilet Paper Problem In this paper, The Toilet Paper Problem, by D. Knuth, in the first page the author states that

Let us assume that people enter the toilet stalls independently at
  random, with probability $p$ that they are big-choosers and
  probability $q = 1 - p$ that they are little-choosers. If the janitor
  supplies a particular stall with two fresh rolls of toilet paper, both
  of length $n$, let $M_n (p)$ be the average number of portions left on
  one roll when the other roll first empties. (We assume that everyone
  uses the same amount of paper, and that the lengths are expressed in
  terms of this unit.) For example, it is easy to establish that
$$M_1(p) = 1, \quad M_2(p) = 2-p, ...$$

, but how does he find $M_n(p)$ ? 
I mean, if $n = 1$, people choose one of the stalls at random and since both stalls have 1 unit of paper, the other will be left with 1 unit of paper, hence $M_1(p) = 1$, but for other cases, I couldn't derive the relations clearly.  
 A: Let's compute $M_2(p)$. We want the 'average' or 'expected' number of sheets left on one of the rolls when the other one is empty. 
Starting both rolls with 2 sheets, label this $[2,2]$. The first person goes into the stall and uses one sheet. Regardless of who it is, big or small chooser, they take from second roll . So now we have $[2,1]$. The second user comes in. With probability $q=1-p$ they are small user so we end up with $[2,0]$. With probability $p$ they are big chooser so we end up with $[1,1]$. In that first scenario we terminate so with probability $q$ we are left with 2 sheets. In the second scenario it doesn't matter who comes in, by the end of the step we end up with $[1,0]$. Thus with probability $q$ we end with $[2,0]$ and with probability $p$ we end with $[1,0]$. And so on average we have $2q+p=2-2p+p=2-p$. 
Try doing out $M_3(p)$. I recommend doing this with a tree diagram. Branching with the probabilities of big or small chooser and terminating a branch when a roll runs out. 
For $M_n(0)$ this means we always have small choosers, so we get $[n,n]\rightarrow [n,n-1]\rightarrow [n,n-2]\rightarrow \cdots \rightarrow [n,0].$ And so $M_n(0)=n$. For $M_n(1)$, we always have big choosers so we have $[n,n]\rightarrow [n,n-1]\rightarrow [n-1,n-1]\rightarrow \cdots \rightarrow [1,1]\rightarrow [0,1].$ 
A: Keeping track rather of both roll states as $M(a,b)$ with $0\le a\le b$, we find
$$M(a,b)=\begin{cases}(1-p)M(a-1,b)+pM(a,b-1)&0<a<b\\
M(a-1,a)&0<a=b\\
b&0=a(<b)\end{cases} $$
This is good enough to compute $M_n(p)=M(n,n)$ for small $n$, e.g., one quickly obtains
$$ M_{10}(p)=-1430p^{17} + 11440p^{16} - 39182p^{15} + 74074p^{14} - 82478p^{13} + 52426p^{12} - 15782p^{11} + 502p^{10} + 246p^9 + 118p^8 + 54p^7 + 22p^6 + 6p^5 - 2p^4 - 6p^3 - 8p^2 - 9p + 10$$
