Passenger seating - One puzzle a day - Puzzle Buddies

Puzzle:A line of 100 airline passengers is waiting to board the plain. They each hold a ticket to one of the 100 seats on that flight. (For convenience, let's say that the Nth passenger in line has a ticket for the seat number N.)
Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. All the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?
Note: Don't forget to visit us again. Answer to the puzzle will be posted tomorrow with winner's name. You can provide your answer in comments.
Solution:The solution to this one is pretty mathimatically involved.

The crazy passenger that boards first has an equal chance of getting on any of the 100 seats. Therefore, the probability of this person sitting in a particular seat k is 1/100.

Now for any value of k, all the passengers up to k will board and take their seats as normal. Then the k-th passenger will find themselves out of a seat, and pick a random seat, in effect, becoming the crazy passenger for a problem with 101 - kpassengers.

(For example if the crazy person takes the tenth seat, passengers 2 through 9 will be seated normally, and when passenger 10's turn comes, they can be considered the crazy passenger first in line of 91 people boarding a plane with 91 seats.)

Let us define P(n) as the probability that the last of n passengers boards their proper place under the conditions of the problem. So for solution, we are looking to find the value of P(100).

In a situation with n passengers, the first, "crazy", passenger can take any of the seats 1 .. n with the probability of 1/n. Also, given some seat number k that the crazy passenger may occupy, the problem will become that of 1+n-k passengers. Therefore, we can say that

P(n) = 1/n * (1 + P(n-1) + P(n-2) + ... + P(2))

(This problem does not make sense with less than 2 passengers. Also, it is easy to see that P(2) is 1/2)

What we would like to do is see what the value of P(n) is in terms of P(n-1).

P(n-1) = 1/(n-1) * (1 + P(n-2) + P(n-3) + ... + P(2) P(n-1) * (n-1) = (1 + P(n-2) + P(n-3) + ... + P(2) P(n) = 1/n * (1 + P(n-1) + P(n-2) + ... + P(2)) (P(n) * n) - P(n-1) = (1 + P(n-2) + ... + P(2))

So,

(P(n) * n) - P(n-1) = P(n-1) * (n-1) (P(n) * n) - P(n-1) = (P(n-1) * n) - P(n-1) (P(n) * n) = (P(n-1) * n) P(n) = P(n-1)

This shows us that the problem's answer does not change if we add one more passenger. Starting at 2 passengers with the anser of 1/2, we can add passengers indefinitely, and still arrive at the same answer. Thus for the instance with 100 passengers, the probability of the last one getting to their proper seat is also 1/2, or 50%.
Winner: