A student proved the following statement using mathematical induction: \"The pop
ID: 3872571 • 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 analysis is as follows:
The claim is for every n, S is any set of n cities in USA then all the cities have same population.
The base induction step is Ok.
It is assumed true for m cities and has been proven for m+1.
The issue here is if we consider a set of m cities then pupulation of those cities are same, but what about two collections. It is not clear if two different collections of m cities will have same population as compared to each other.Even if we look at the base case i.e n = 1, we haven;t addressed the issue of comparison between two sets consisting of two different countries.Thee same feature is from within the set and not outside the set.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.