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