An interesting problem. Is this from the course or from somewhere else?
Basically, as I see it, at any one time there is at most one passenger whose seat is already taken. The question is whether or not that passenger solves the problem by:
- Being the next to board the plane
- Happening to choose the seat of someone who is already on the plane
If we don't have both of these things happening then we return to where we started, i.e. with one passenger still to board whose seat is already taken. We can view the process as having two end-stages, i.e. the first and last passengers to board, and several intermediate stages, where the next passenger to board could solve the problem and allow the remaining passengers to board in their correct seats. We want the probability that none of the intermediate stages succeeds.
We can get this by examining an individual intermediate stage, assuming that there is still a passenger whose seat is already taken and that \(r\) passengers have already boarded and there are \(n-r\) still to board. The probability of the passenger whose seat is already taken being the next to board the plane is \(\frac{1}{n-r}\) and, given that this passenger boards, the probability that he solves the problem by randomly choosing the seat of someone who is already on the plane is \(\frac{1}{n-r}\), since there is only one such seat out of the \(n-r\) remaining. So the probability of the problem being solved at this stage is \(\frac{1}{(n-r)^2}\) and the probability of it not being solved is \[1-\frac{1}{(n-r)^2}=\frac{(n-r+1)(n-r-1)}{(n-r)^2}\].
Now we want the probability that the problem is not solved at any of the \(n-2\) intermediate stages:
\[\prod_{r=1}^{n-2}\frac{(n-r+1)(n-r-1)}{(n-r)^2}=\frac{n}{2(n-1)}\]
This gives the probability that the last passenger finds his seat already taken. So the probability that the last passenger finds his seat free is:
\[1-\frac{n}{2(n-1)}=\frac{n-2}{2(n-1)}\]
I've a hunch that this conclusion could have been arrived at rather more simply and I'd be interested to hear from anyone who can demonstrate how.
