MUN Computer Science 1002 - Lab 7

Induction and its variants




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

A student wants to run a game at a mixer which involves betting using tokens instead of money. However, right before the mixer she realizes that the only tokens she has are of values 6, 10 and 15. Prove that she can still run the game if she restricts the amount of the minimal bet.

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?

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).

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.