# Recurrence relation lab modelling

This is the first question here I'm struggling with. I dont know how to start and I'm kind of lost in this question.

Suppose that you will have lab exam in a particular lab where computers are called "inek", and everybody has a particular place (think of the seating plan we prepare for you). But unfortunately one of your friends, let it be $G$, who is first to arrive forgot his assigned inek computer, and chooses an inek machine randomly. After, successively arriving students will sit their assigned inek if it is not occupied, if occupied he/she has to choose randomly too. Assume you are last to arrive and $n$ students are participating for the class, then generate a recurrence relation for the probability that you will take the lab exam in your originally assigned inek.

• Hint. What is the probability if there are just two students in the class? If you know the answer for $n$ students how would you use it to find the answer for $n+1$? Jan 1, 2017 at 16:30
• It is 1/2 if there are two students, right? Why are we trying to find n+1? It is enough to find for n students. Jan 1, 2017 at 17:35
• Right for $n=2$. Then "recurrence" means "express the answer for $n+1$ in terms of the answer for $n$." If you'd rather, then it's "express the answer for $n$ in terms of the answer for $n-1$." Jan 1, 2017 at 19:42
• @Ethan: Not quite: it need not be a first-order recurrence. If $p_n$ is the answer for $n$, it means ‘express $p_{n+1}$ in terms of the values $p_k$ for $2\le k\le n$’. Jan 2, 2017 at 1:54

Let $p_n$ be the probability that you take your assigned seat if you are the last of $n$ students; clearly $p_2=\frac12$. Now suppose that you’re the last of $n+1$ students. If the first student takes that student’s assigned seat, each of the remaining $n$ students, including you, will take his or her assigned seat; this occurs with probability $\frac1{n+1}$.

Now suppose that the first student takes an incorrect seat. If that seat is your assigned seat, you definitely will not get your assigned seat, so we can limit ourselves to the case in which the first student takes an incorrect seat that is not yours. Suppose that the first student takes seat $k$, where $1<k<n+1$. Then students $2,3,\ldots,k-1$ will take their assigned seats, and seats $1$ and $k+1,\ldots,n+1$ will be available for student $k$.

Claim: The probability that you will get your assigned seat is $p_{n-k+2}$.

To see why this is so, note that the first $k-1$ students have taken seats, so you are the last of the $(n+1)-(k-1)=n-k+2$ students who have not yet taken a seat. Student $k$ is the first of this remaining group of $n-k+2$ students. Temporarily relabel seat $1$ as seat $k$. Then we have a group of $n-k+2$ students, each of whom has a correct seat, the first student in the group (i.e., student $k$) must choose one at random, and you are the last student in the group. By definition $p_{n-k+2}$ is the probability that in this situation you will get your assigned seat.

The probability that the first student takes seat $k$ is $\frac1{n+1}$, so

\begin{align*} p_{n+1}&=\frac1{n+1}+\sum_{k=2}^n\frac{p_{n-k+2}}{n+1}\\ &=\frac1{n+1}\left(1+\sum_{k=2}^np_{n-k+2}\right)\\ &=\frac1{n+1}\left(1+\sum_{k=2}^np_k\right)\;, \end{align*}

where in the last step I’ve substituted $k$ for $n+2-k$: as $k$ runs from $2$ through $n$, $n+2-k$ runs from $n$ down through $2$.

This is your recurrence: it expresses $p_{n+1}$ in terms of the values $p_k$ for $2\le k\le n$. If you recursively calculate $p_n$ for a few small values of $n\ge 2$, you should easily be able to conjecture a closed form for for $p_n$ and prove it by induction. This question and its answers will let you confirm that your closed form is correct and show some other ways to arrive at it.