Showing that only $(n+1)^{n-1}$ of all the possible $n^n$ choices assure a full car park 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?
 A: This solution is paraphrased from http://www-math.mit.edu/~rstan/transparencies/parking.pdf.

Imagine that the parking spaces are instead arranged in a circle, and an $(n+1)^{st}$ spot is added. Each of the $n$ cars chooses a favorite space between $1$ and $n+1$. Each car tries to park in their preferred space, but if they find it occupied, they inspect adjacent spaces in increasing order until they find an empty space. Now, every car will be able to find a spot with certainty. Furthermore, the sequence $(a_1,a_2,\dots,a_n)$ is valid in the original problem if and only if the unused space is $n+1$ in the modified problem.
There are $(n+1)^n$ choices for the sequence of space preferences. Furthermore, if the unused spot for $(a_1,\dots,a_n)$ is $k$, then the unused spot for $(a_1+1,\dots,a_n+1)$ is $k+1$, where all addition is modulo $n+1$. Therefore, these $(n+1)^{n}$ sequences are partitioned into sets of size $n+1$ where there is exactly one valid sequence for the original problem, so the number of valid sequences is $$\frac{(n+1)^n}{n+1}=(n+1)^{n-1}.$$

