Solution 4.9.7.1.
To get the idea, consider what happens with only 2 people, then only 3. Generalize.
The answer is 1/2. To obtain this, you can define recursively the probability that the kth person sits in their own set as f(k). Consider the first traveler’s and your seats. Then you get the following cases:
P(first guy sits in his own seat and you sit in yours) = \(\frac{1}{k} \cdot 1\)
P(first guy sits in your seat and you do not sit in yours) = \(\frac{1}{k} \cdot 0\)
P(other k-2 travelers make their choices) = \(\frac{k-2}{k} f(k-1)\)
\begin{equation*}
f(k) = 1/k + 0 + \frac{k-2}{k} f(k-1)
\end{equation*}
with f(2) = 1/2.
For example,
f(3) = 1/3 + f(2)/3 = 1/3 + 1/6 = 1/2.
f(4) = 1/4 + 2/4 f(3) = 1/4 + 1/2 1/2 = 1/2.
f(5) = 1/5 + 3/5 1/2 = 1/2.
f(6) = 1/6 + 4/6 1/2 = 1/2.
Etc.