Discrete Math Use induction to prove The city of Inductiona

Discrete Math -

Use induction to prove.

The city of Inductionapolis has multiple police districts. Any two districts are connected by a one-way street. Show that there is a route that passes through every district of the city.

Solution

Base case: 2 districts

Since there are one-way streets between any two districts. So there is a route passing through the two districts

Hence base case is true

Inductive hypothesis: Assume it is true for some n number of districts, n>=2

Inductive step: We show it is true for n+1

COnsider any arbitrary district , say, D

Remaining n district have a route,R, passing through them because of inductive hypothesis

So, the C be a district which is the end point . Since there is a one way street from C to D call it , S

So the route, R+S is the route passing through all n+1 districst

Hence true for n+1

And hence for all n>=2