A student proved the following statement using mathematical induction: \"The pop
ID: 3887335 • Letter: A
Question
A student proved the following statement using mathematical induction: "The population of every city in US is the same." The students proof proceeds as follows. The above statement is equivalent to: "For every n, if S is any set of n cities in US, then the population of all cities from S is the same". Base Case. Size of S is 1. There is only one city in S. Thus population of every city in S is the same. Inductive Hypothesis. Let S be a set of m cities and assume that population of every city in S is the same. Induction Step. We will prove that if S is a set of m + 1 cities, then the population of every city in S is the same. Let S = {c_1, c_2, . . . , c_m, c_m + 1}. Consider the following two subsets of S: S_1 = {c_1, . . . , c_m}, S_2 = {c_2, . . . , c_m + 1} Note that both S_1 and S_2 are of size m. Thus by induction hypothesis: population(c_1) = population(c_2) = . . . = population(c_m), population(c_2) = population(c_2) = . . . = population(c_m + 1). Since c_2 appears in both sets, we have population(c_1) = population(c_2) = . . . = population(c_m) = population(c_m + 1). Thus for every set of m + 1 cities, their population is the same. By induction principle, every city in US has the same population. Of course, the above statement is wrong. Identify the problem in the above proof. To receive credit, you must explain why the above proof is correct-identify the exact place where the proof fails.Explanation / Answer
The proof fails only when S=1. In that case it fails because the sets S1={c1} and S2 = {c2} no longer overlap: there is no city in both sets. Thus, while it’s true that all of the cities in S1 are the same population and that all of the cities in S2 are the same population; we can no longer infer that those two population must be the same. But if we could somehow show that in every set of two cities, both cities were the same population, the induction argument as given would work just fine: we’d always be considering some n2, so the sets S1 and S2 would overlap.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.