Description

Discrete Mathematics TAs
1 Induction
The Induction Principle: let P(n) be a statement which involves a natural number n, i.e., n = 1,2,3…, then
P(n) is true for all n if
1. P(1) is true , and
2. P(k) →− P(k + 1) for all natural numbers k
2 Questions
1. 10 points Prove that the sum of adding the first n natural numbers is given by
2. What is wrong with the following proof:
In the following proof we show that all horses are of the same color.
Base Case: The case with just one horse is trivial. If there is only one horse in the ”group”, then clearly all horses in that group have the same color.
Inductive step: Assume that n horses always are the same color. Consider a group consisting of n+1 horses. First, exclude one horse and look only at the other n horses; all these are the same color since n horses always are the same color. Likewise, exclude some other horse (not identical to the one first removed) and look only at the other n horses. By the same reasoning, these too, must also be of the same color. Therefore, the first horse that was excluded is of the same color as the non-excluded horses, who in turn are of the same color as the other excluded horse. Hence the first horse excluded, the non-excluded horses, and last horse excluded are all of the same color, and we have proven that: If n horses have the same color, then n + 1 horses will also have the same color. And as we have already sown that the base case is true, therefore all horses are of the same color.
QED
3. 10 points Prove by induction the sum of adding the first n odd numbers is given by
4. Show that n! < nn ∀n ∈ N {1}
5. Given a finite set A, show that |P(A)| = 2|A|
6. Prove that 2 divides n2 + n whenever n is a positive integer.
7. Given a set of natural numbers from 1 to n, it possible to arrange the numbers in an order where the average of 2 numbers doesn’t lie between them.
1
CS 113 Spring 201 Recitation: Induction Discrete Mathematics TAs

8. There is a midnight party in the jungle and you are out to track the elusive unicorn. Because all the guests are in costume, it is difficult to spot the unicorn visually. Instead you are relying on the fact that the unicorn smells like a rainbow. Your own sense of smell is overpowered by all the scents from the guests, the jungle, and the smoke from the party machine. So you are going to question the animals at the party who possess a keener sense of smell. Animals do not lie.
Your Animalese is weak–the only question you can ask a guest is whether another guest smells like the rainbow to them.
Use mathematical induction to show that if there are n animals at the party, then you can find the unicorn, if it is attending, with a total of at most 3(n − 1) questions.
9. Given a 2n ×2n board where ∀n ∈ Z,n ≥ 0, if we remove a single square from the board, the remaining board can be tiled entirely by L-shaped trominoes shown in Figure 1. Prove this using induction.

(a) T1 (b) T2 (c) T3 (d) T4
Figure 1: All Possible Trominoes

Page 2 of 2