Hey everyone. I have a proof by induction problem that I\'m trying to understand
ID: 3536333 • Letter: H
Question
Hey everyone.
I have a proof by induction problem that I'm trying to understand and solve.
Here is the text from the assignment verbatim.
Consider the following theorem and proof. Explain what%u2019s wrong with the proof.
Theorem: Everyone taking this class is the same age.
Proof: By induction.
Base Case: Assume the class has size 1. Obviously, this person has exactly one age.
The problem is that I haven't done proofs like this in a long time, so to me, everything looks correct.
What am I missing here?
Explanation / Answer
Consider the following theorem and proof. Explain what%u2019s wrong with the proof.
Theorem: Everyone taking this class is the same age.
Proof: By induction.
Base Case: Assume the class has size 1. Obviously, this person has exactly one age.
Inductive step: Assume that in a class of n people, everyone has the same age.
We show that this implies that the same is true for a class of n+1 people.
Assume P, Q, and R are members of the class of n+1 people.
Consider the class of n people containing everybody except Q.
INDUCTION1: Since this is a class of n people, all of them have the same age (by the inductive hypothesis).
Now consider the class of n people containing everybody except P.
INDUCTION2: Since this is also a class of n people, all of them have the same age (same reasoning).
Since R is in both classes of size n, P=R and Q=R. Thus P=Q=R, and the class of n+1 people all have the same age.
The error is in the last sentence. The two statements INDUCTION1 and INDUCTION2 statements of our choice.
imply that INDUCTION = INDUCTION1 U INDUCTION 2 are of same age if and only if INDUCTION1 and INDUCTION2 doesnt have any
common student. but in INDUCTION1 we have p P and R
in INDUCTION2 we have Q and R means R is common between them.
but this is not true when we have only 2 students.
when there are 2 students i.e P and Q. if we remove Q. then P will have same age.
but if we remove P. then we left with Q means Q may or may not have same age.
this iives us no means to conclude that they both have the same age.