This exercise is taken from the site of Queen Mary University of London:
A car park has $n$ spaces, numbered from $1$ to $n$, arranged in a row. $n$ drivers each independently choose a favourite parking space in the park. As each driver enters the park, he drives to his favourite space. If it is empty, he parks there. Otherwise, he continues along the line and parks in the first free space. If all spaces between his favourite and $n$ are taken, he leaves in disgust.
Show that, out of the $n^n$ choices of favourite spaces that the drivers can make, just $(n+1)^{n-1}$ lead to all drivers parking successfully.
Now, my question is whether my (attempt of ) solution is wrong and what a different approach could be. Here's my idea: proving the claim by (a kind of) induction. It is easy to verify truthfulness for $n=1$ and $n=2$, so having this base case, we shall prove that if the claim holds for all $1\le n\le k$, then it does also for $n=k+1$.
Let us assume WLOG there is an already established order of appearance of the drivers, since a different order yields the same number of successful choices: it just suffices to swap the drivers. Let us call $d_m$ the space chosen by the $m$-th driver.
Now, consider the cases in which $d_1=1$. By inductive hypothesis, the other drivers have $n^{n-2}$ successful choices. In fact, the same goes for all the other $n-1$ choices of the first driver, so that in total, as a "first outcome", we have $\color\red{n^{n-1}}$ successful choices. We somewhat can do the same reasoning with the second driver, but we must keep in mind that for each of his choices, we have already counted those in which the first driver occupies the other spaces. For example, we need to subtract the successful cases in which at the same time $d_2=1$ and $d_1=2$: that is $(n-1)^{n-2}$. This happens for all the spaces not chosen by the second driver, and so we actually need to subtract $(n-1)^{n-1}$. Finally, letting vary $d_2$ yields the "second outcome" $\color\red{n^{n-1}-n(n-1)^{n-1}}$. And so on, and so on. The final outcome would be the sum of all the red expressions. However I'm afraid no nice power would be a result of this. Is there a mistake in my reasoning?