[snip]

With probability (k-1)/(k+1), the first passenger picks seat number s, where

. Then passengers 2, 3, ..., s-1 will all take their desired seats and passenger s will make a random choice from the remaining k-s+2 seats. This is just like the original problem, where passenge s now takes the place of passenger 1 and the plane contains k-s+2 seats. By the inductive hypothesis, the probability that the last passenger will get his desired seat is 1/2.

[Edit: No, this part isn't quite right-- let me work on it and get back to you later. It's too late at night to work on it now.]