Induction

Math wiz Prudence Juris wins the Fields Medal by proving the following theorem:

Theorem 1 All students in CS 212 will get the same grade.
Proof: We prove the theorem by induction.
Base case: Consider a set of 1 CS 212 student. Certainly the student gets the same grade as herself.
Induction hypothesis: Let n 1. Suppose that for any set A of n CS 212 students, all students in set A will receive the same grade.
Induction Step: Suppose the induction hypothesis hold for some n 1. We need only show that for any set B on n + 1 CS 212 students, that all students in set B will receive the same grade.

(Part 1) Take the set B. It has n + 1 students. Take one, say s, out, to obtain a set A = B - {s}. Now, set A contains n students so by the induction hypothesis, all students in A will receive the same grade. Call this grade g_s. Now, put s back in to obtain B again.

(Part 2) Pick another student t of B, different from s. Remove t from B to obtain another set C. Now, C has n elements, so that all students in C will receive the same grade, by the induction hypothesis. Call this grade g_t.

We can show that g_s = g_t. Pick any student r in B different from s and t. Then, r will receive grade g_s in part 1 and grade g_t in part 2. Since r receives identically on grade, g_s = g_t. Hence students t, s and r all receive the same grade. Since the choices of students were arbitrary, we conclude that all students in CS 212 will receive the same grade.

Prudence is very proud of her result, and hopes to get an A+ in CS 212. But she is dismayed when her classmate , lazy, slothful Nick Nurd proves the following lemma

Lemma 1 I (Nick) will flunk CS 212.
Proof: By construction. I won't study, I'll get roaring drunk before the test, dress worse than the CS 212 staff, ride my motorcycle into the test halfway through, and enrage the TAs by mixing up their name on purpose.

This results in the following unfortunate

Corrollary 1 All students will fail CS 212.
Proof: By Nick's Lemma 1, one student (Nick) will get and F. Hence, by the theorem 1 of Juris (above), all students will get an F.

Prudence is enraged and saddened. All that work down the drain because of one shiftless, no-account bum! She goes to consult her favorite logic professor, Letcher S. Hazbin. Hazbin consoles her: "Well, you could try to find a flaw in Nick's lemma... But that would involve reforming him so that he'll pass. An odious task! If I were you, I'd look for a bug in your argument. If you find one, then he can flunk, and you can still get an A!"

1. Is there a flaw in her proof? Explain briefly in good English. If there is a flaw, identify it an explain. You may assume that Nick's lemma is true.
   
   
   
   
   
2. Assume Nick's lemma is true. Will all students fail CS 212? Explain.
   
   
   
   

Solution

Return to CS 212 Prelim 2 - Spring 1997