There are infinitely many stations on a train route. Sup-
pose 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.
Examples of Hypothesis In the conditional, "If all four sides of a quadrilateral measure the same, then the quadrilateral is a square" the hypothesis is "all four sides of a quadrilateral measure the same".
Let p(k) be the hypothesis that the train stops at station k.
Base case: P(1) is true because we are told that the train stops at the first station.
Induction step: Assume that the train stops at station k - 1 that is P ( k - 1 ) , is true.
Now, we are told to assume that, if the train stops at a station, then it stops at the next station. Since we assumed that it stopped at station k - 1 (by induction hypothesis), it means that it will stop at station k. Thus P (K) , is true.
Then, by induction, P(k) is true for all k and, therefore, the train stops at all stations.
The well-ordering property can be used to show that there is a unique greatest common divisor of two positive integers. Let a and be positive integers, and let S be the set of positive integers of the form , where s and t are integers.
a) Show that s is nonempty.
b) Use the well-ordering property to show that s has a smallest element .
c) Show that if d is a common divisor of a and b, then d is a divisor of c.
d) Show that c I a and c I b. [Hint: First, assume that . Then , where . Show that , contradicting the choice of c.]
e) Conclude from (c) and (d) that the greatest common divisor of a and b exists. Finish the proof by showing that this greatest common divisor is unique.
94% of StudySmarter users get better grades.Sign up for free