MUN Computer Science 1002 - Lab 7

Induction and its variants

Review:

• Lectures 21-23.

Vocabulary

• Sum, product, factorial notation
• Mathematical induction, strong induction, well-ordering principle.
• Sequences. Arithmetic and geometric progressions.

Individual work

Solve each of the following exercises.

1. Compute the following (you can use a calculator).
   1. $\Sigma_{i=2}^5 i^2$,
   2. $ \Pi_{i=0}^3 (i+2)$
   3. $(10-6)!$
2. List the first five elements in the following sequences.
   1. Arithmetic sequence with c=10 and d = 4.
   2. $(n!)/2^n$ for $n \in \mathbb{N}$. (Hint: define $0!=1$).
3. Read the following proofs, and annotate them stating how each step came from the previous. In particular, indicate the statements of the theorem being proven, the predicate, the base case, the induction hypothesis and the induction step, and where the induction hypothesis and/or the base case are applied (and where it is just calculations). State whether a proof is by strong induction or the "normal" induction.

   a) Let us show that for every natural number $n$, $\Sigma_{i=0}^n 2^i = 2^{n+1} -1$. For $n=0$, $\Sigma_{i=0}^0 2^i = 2^0 = 1 = 2^1-1$. Now suppose that $\Sigma_{i=0}^k 2^i = 2^{k+1} -1$. Then $\Sigma_{i=0}^{k+1} 2^i = (\Sigma_{i=0}^k 2^i) + 2^{k+1} = (2^{k+1} -1) + 2^{k+1} = 2^{k+2}-1$. Therefore, $\forall n \in \mathbb{N}$ $\Sigma_{i=0}^n 2^i = 2^{n+1} -1$.

   b) DeMorgan's law can be generalized to a union (similarly, intersection) of any $n$ sets from some common universe: $\overline{A_1 \cup \dots \cup A_n} = \overline{A_1} \cap \dots \cap \overline{A_n}.$

   Indeed, the cases of $n=0$ and $n=1$ are trivial, and for $n=2$ it is our standard DeMorgan's law, $\overline{A_1 \cup A_2} = \overline{A_1} \cap \overline{A_2}$.

   Let $\overline{A_1 \cup \dots \cup A_i} = \overline{A_1} \cap \dots \cap \overline{A_i}$ for every $i$ such that $2 \leq i < k$, and any sets $A_1, \dots, A_i$.

   As $k>2$, for some $j$ such that $1 \leq j < k$, $\overline{A_1 \cup \dots \cup A_k} = \overline{A_1 \cup \dots \cup A_j \cup A_{j+1} \cup \dots \cup A_k}.$

   Then $$\overline{A_1 \cup \dots \cup A_k}= \overline{A_1 \cup \dots \cup A_j \cup A_{j+1} \cup \dots \cup A_k} = $$ $$= \overline{(A_1 \cup \dots \cup A_j) \cup (A_{j+1} \cup \dots \cup A_k)} = $$ $$= \overline{(A_1 \cup \dots \cup A_j)} \cap \overline{(A_{j+1} \cup \dots \cup A_k)} =$$ $$= (\overline{A_1} \cap \dots \cap \overline{A_j}) \cap (\overline{A_{j+1}} \cap \dots \cap \overline{A_k})=$$ $$ =\overline{A_1} \cap \dots \cap \overline{A_j} \cap \overline{A_{j+1}} \cap \dots \cap \overline{A_k} =$$ $$= \overline{A_1} \cap \dots \cap \overline{A_k}.$$ Thus generalized DeMorgan's law holds for any $n$ and any sets $A_1, \dots, A_n$.

4. In this question you need to complete an induction proof of the theorem that for any integer $n$, $n^3-n$ is divisible by 3 by filling in missing pieces. For that, open this proof template and fill in the blanks .

Group exercises

For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

Topic 1: Betting with tokens

• Try making various amounts between 20 and 35 out of 6, 10 and 15. Which of them you can make and which you cannot? Make a guess at what is the largest number $a$ that you cannot make out of these three kinds of tokens
• Now, prove that indeed you can make any amount larger than the $a$ you just found by using tokens of values 6, 10 and 15. Try three different kinds of proof: by well-ordering principle, by induction, and by strong induction
• Let's generalize. Suppose you have $m$ tokens of values $t_1, \dots, t_m$. How can you determine if any amount larger than something can be paid with these tokens, or whether there are always amounts that cannot be paid? Hint: what if the only tokens were of values 10 and 15, without 6? What would go wrong in you proof?

Topic 2: Sharing chocolate

Imagine that you have a bar of chocolate which is a $n \times m$ grid of pieces ("squares"). To share it with your friends, you would like to break it up into individual squares, without ever breaking an individual square. How many steps would it take for you to do so, if at any step you can break a piece of chocolate in half horizontally or vertically? Does it depend on the order in which you break it, and if so, what is the best order?

• Try it out by cutting a 4 x 4 grid into individual squares. Then try a 10 x 1 grid and a 6 x 3 grid. Use these expriments to figure out what might be the fastest way to do it and how many steps you need.
• Prove your answer in two different ways: by induction and by strong induction. Hint: your might need to use different predicates for induction vs. strong induction proof.

Topic 3: Pie fights

Imagine $n$ people standing in a field, each holding a pie. At a signal, everybody throws a pie into their nearest neighbour (assume that distances between each pair of people are all different, so in particular everybody has one nearest neighbour).

• Draw examples of such arrangments with 5, 6 and 7 people, and determine who throws pie into whom in each example.
• Prove using well-ordering principle that there are at least two people who throw pies at each other. Hint: recall that the well-ordering principle applies to any countable set (and its countable or finite subsets).
• Suppose $n$ is odd. Prove by induction that there is always at least one person who does not get hit by a pie.
• Prove that if the number of people is even then for every $n$ there is a way to arrange people on the field so that everybody gets hit by a pie. Hint: assume that the field size is unlimited.

Review after the group activity

1. Say how to make number 37 out of tokens of values 6, 10, 15. Now say how to do it only with tokens of values 4 and 7. Can you do it with tokens 6 and 15?
2. How many breaks do you need to break a 10 x 2 chocolate bar into individual squares? And how many for a 6 x 5 bar?
3. If 3 people in a pie fight stand on the corners of a right triangle with sides 3,4,5, who will throw pie into whom? Who will survive? Now, put a 4th person at the side of length 5 a distance 1 from the corner of 5-side and 4-side. Who throws the pie where now? Does anyone survive? And how would it change if the 4th person were to stand on the 3-side 1 away from the right corner?
4. In all induction and strong induction proofs (for questions 3 and 4, as well as the group exercises), identify the statement $P(n)$ being proven, base case(s), induction hypothesis, induction step, and where that induction hypothesis is used in the induction step. Make sure you know the difference between strong induction and normal induction.