Problem 3 (20 points) Your friend tries to convince you of the following obviously erroneous theorem, and

gives the following proof by induction.

Theorem 1. In every set of 1 students, all students have the same favorite song.

Proof. Let () be the statement In every set of 1 students, all students have the same

favorite song. We will prove that () is true for every . For the base case (1) is true since

any single student has the same favorite song as itself. For the inductive step, we will prove that

( 1) = () for every 2. Consider any set of students. By the inductive hypothesis

( 1), the first 1 students have the same favorite song.

1 2 3 . . . 1

| {z }

same favorite song

Also, by the inductive hypothesis, the last 1 students have the same favorite song.

1 2 3 . . . 1

| {z }

same favorite song

By transitivity, all of the students must have the same favorite song. The proof of the theorem

now follows by induction.

Since the statement is obviously false, the proof must have a specific flaw. What is it?

23 (20 points) Your friend tries to convince you of the following obviously erroneous theorem, and gives the following proof by induction. Theorem 1. In every set of n1 students, all students have the same favorite song. Proof. Let H(k) be the statement "In every set of 1nk students, all students have the same favorite song." We will prove that H(n) is true for every n. For the base case H(1) is true since any single student has the same favorite song as itself. For the inductive step, we will prove that H(k1)H(k) for every k2. Consider any set of k students. By the inductive hypothesis H(k1), the first k1 students have the same favorite song. Also, by the inductive hypothesis, the last k1 students have the same favorite song. s1samefavoritesongs2s3sk1sk By transitivity, all k of the students must have the same favorite song. The proof of the theorem now follows by induction. Since the statement is obviously false, the proof must have a specific flaw. What is it