MUN Computer Science 1002 - Lab 7, question 4

Fill-in-the-blanks proof

In this question you need to insert the missing pieces of the proof in the blanks. The annotation stating the rationale for each step are highlighted.

Proof text Hint

Theorem: for any $n \in \mathbb{N}$ , $n^3 -n$ is divisible by 3.

Using definition of divisibility , that can be restated as _______________________ Here you put $\forall n \in \mathbb{N} \ \exists m\in\mathbb{N} \ n^3-n=3m$

Thus, with this definition, the predicate $P(n)$ is: _______________________ Write what $P(n)$ stands for

Base case: for $n=$ ___, $P($ ___ $)$ : _______________________. Insert the respective value of $n$ and write out $P(n)$ for that value.

It holds with______ as the witness for the existential quantifier the value of $m$ for this specific $n$

Induction hypothesis: assume $P(k):$ _______________________ what $P(k)$ stands for

That is, __________ = ________ for some _______. Existential instantiation for the statement in $P(k)$ .

Induction step: We will show that $P(k+1):$ ____________________________________ holds assuming the induction hypothesis. Use a different name for the variable under the existential quantifier (you will need to refer to it later).

_______________________ = Write out the left side of the expression in $P(k+1)$

= ________________________________________ = Multiply out brackets to get a sum of terms

= ________________________________________ = Rearrange terms to get your expressing to start with the left side of the equality in the induction hypothesis.

By induction hypothesis: = _________________________________ = Substitute the expression on left side in $P(k)$ in the formula on the previous line with the expression on the right side in $P(k)$ .

= ______________________________________________________ = now do some more algebra to get your resulting expression into the form 3*something

Thus, _______________________ = 3 * (_______________________ ), Now say what your existentially quantified variable for $P(k+1)$ is as a function of that variable in $P(k)$

So by definition of divisibility with ______ = _______________________ and existential generalization, _______________________ is divisible by 3. Use the existentially quantified variable's name from $P(k+1)$ at the beginning of the induction step.

Therefore, by induction _______________________ holds. the theorem statement

Proof text	Hint
Theorem: for any $n \in \mathbb{N}$ , $n^3 -n$ is divisible by 3.
Using definition of divisibility , that can be restated as _______________________	Here you put $\forall n \in \mathbb{N} \ \exists m\in\mathbb{N} \ n^3-n=3m$
Thus, with this definition, the predicate $P(n)$ is: _______________________	Write what $P(n)$ stands for
Base case: for $n=$ ___, $P($ ___ $)$ : _______________________.	Insert the respective value of $n$ and write out $P(n)$ for that value.
It holds with______ as the witness for the existential quantifier	the value of $m$ for this specific $n$
Induction hypothesis: assume $P(k):$ _______________________	what $P(k)$ stands for
That is, __________ = ________ for some _______.	Existential instantiation for the statement in $P(k)$ .
Induction step: We will show that $P(k+1):$ ____________________________________ holds assuming the induction hypothesis.	Use a different name for the variable under the existential quantifier (you will need to refer to it later).
_______________________ =	Write out the left side of the expression in $P(k+1)$
= ________________________________________ =	Multiply out brackets to get a sum of terms
= ________________________________________ =	Rearrange terms to get your expressing to start with the left side of the equality in the induction hypothesis.
By induction hypothesis: = _________________________________ =	Substitute the expression on left side in $P(k)$ in the formula on the previous line with the expression on the right side in $P(k)$ .
= ______________________________________________________ =	now do some more algebra to get your resulting expression into the form 3*something
Thus, _______________________ = 3 * (_______________________ ),	Now say what your existentially quantified variable for $P(k+1)$ is as a function of that variable in $P(k)$
So by definition of divisibility with ______ = _______________________ and existential generalization, _______________________ is divisible by 3.	Use the existentially quantified variable's name from $P(k+1)$ at the beginning of the induction step.
Therefore, by induction _______________________ holds.	the theorem statement

MUN Computer Science 1002 - Lab 7, question 4 Fill-in-the-blanks proof

MUN Computer Science 1002 - Lab 7, question 4

Fill-in-the-blanks proof