MathNet 2011 Question 100

Let $n\ge2$ and $k\ge1$ be integers. A country has $n$ cities, and a two-way bus connection joins every pair of cities. Let $A$ and $B$ be distinct cities. Prove that the number of ways to travel from $A$ to $B$ using exactly $k$ buses equals
$$\frac{(n-1)^k-(-1)^k}{n}.$$