MathDB

[(n - 1)^k - (-1)^k] /n is number of ways with k buses, between 2 cities

Source: Dutch IMO TST2 2011 p1

January 10, 2020

combinatorics

Problem Statement

Let

n \ge 2

and

k \ge1

be positive integers. In a country there are

n

cities and between each pair of cities there is a bus connection in both directions. Let

A

and

B

be two different cities. Prove that the number of ways in which you can travel from

A

B

by using exactly

k

buses is equal to

\frac{(n - 1)^k - (-1)^k}{n}