There are infinitely many stations on a train route. Suppose that the train stops at the first station and suppose that if the train stops at a station, then it stops at the next station. Show that the train stops at all stations

Let’s revisit the principle of mathematical induction.

PRINCIPLE OF MATHEMATICAL INDUCTION: “To prove that P(n) is true for all positive integers n, where P (n) is a propositional function, we complete two steps:

BASIS STEP: We verify that P (1) is true.

INDUCTIVE STEP: We show that the conditional statement P (k) → P (k + 1) is true for

all positive integers k.” Source: Discrete Mathematics and its Applications by Rosen.

Now we can solve the exercise by applying the principle of mathematical induction.

Let P(n) be the statement that the train stops at station n.

Now, we need to complete the basis step by verifying that P(1) is true.

Basis step: P(1) is true because the exercise states that the train stops at the first station (read again the exercise).

Inductive step: By the problem description, if the train stops at a station, then it stops at the next station. We can write this by stating that P(n) implies P(n+1) for n≥1.

Therefore, P(n) is true for all positive integers by mathematical induction.

⧠

Related exercises:

• a) Find a formula for 1/2 + 1/4 + 1/8 + … + 1/2^n by examining the values of this expression for small values of n. b) Prove the formula you conjectured in part (a).
• Prove that 3+3 · 5+3 · 52+···+3 · 5^n=3(5^(n+1)−1)/4 whenever n is a nonnegative integer
• Let P(n) be the statement that 1^2 +2^2 +···+n^2 = n(n + 1)(2n + 1)/6 for the positive integer n.