Let $\alpha(k)$ be the number of ways to travel from city $A$ to city $B \neq A$ with $k$ buses. Let $\beta(k)$ be the number of ways to travel from city $A$ to city $A$ with $k$ buses. If we start in city $A$ and then take $k$ buses, this can be done in $(n-1)^{k}$ ways. In $\beta(k)$ of these cases, we end up in city $A$, and in $(n-1) \alpha(k)$ of these cases, we end up in a city other than $A$. Therefore,

$$(n-1) \alpha(k)+\beta(k)=(n-1)^{k} .$$

Now take $k \geq 2$. To travel from city $A$ to city $A$ with exactly $k$ buses, we take a bus from $A$ to any city (this can be done in $(n-1)$ ways); then we must travel from a city not equal to $A$ to city $A$ with $k-1$ buses, which can be done in $\alpha(k-1)$ ways. Thus,

$$\beta(k)=(n-1) \alpha(k-1) \quad \text { for } k \geq 2$$

We now substitute this expression for $\beta(k)$ into (1). This gives us for $k \geq 2$ that

$$(n-1) \alpha(k)+(n-1) \alpha(k-1)=(n-1)^{k}$$

and thus

$$\alpha(k)=(n-1)^{k-1}-\alpha(k-1) .$$

We will now prove by induction on $k$ that for $n \geq 2$ and $k \geq 1$,

$$\alpha(k)=\frac{(n-1)^{k}-(-1)^{k}}{n} .$$

For $k=1$, this gives $\alpha(1)=\frac{(n-1)+1}{n}=1$, which is correct, since there is exactly one way to travel from city $A$ to city $B \neq A$ with one bus. Now let $m \geq 1$ be an integer, and assume that we have proven the expression for $\alpha(k)$ for $k=m$. Then, using (3), for $k=m+1 \geq 2$ we have

$$\begin{aligned} & \alpha(m+1)=(n-1)^{m}-\alpha(m)=(n-1)^{m}-\frac{(n-1)^{m}-(-1)^{m}}{n} \\ & =\frac{n(n-1)^{m}-(n-1)^{m}+(-1)^{m}}{n}=\frac{(n-1)^{m+1}-(-1)^{m+1}}{n} \end{aligned}$$

which is exactly the expression we wanted to prove for $k=m+1$. This completes the induction.