# SS - Lecture 0 exercises

## Exercise 6*
Assume, for the sake of contradiction that if $m + n \geq 19$ then $m \geq 10$ or $n \geq 10$.

$m+n \geq 19 \wedge \neg (m \geq 10 \vee n\geq 10)$
$m+n \geq 19 \wedge m \lt 10 \wedge n\lt 10$

$m + n \geq 19 \wedge m + n < 20 = false$

## Exercise 8*

$P(n) = 4^n+14\mod 6 = 0$

### Base Case
Case n = 1
$4^1 + 14 \mod 6 = 0$
$4 + 14 \mod 6 = 0$
$18 \mod 6 = 0\ \checkmark$

### Induction
Assume $P(n)$ is true for all $n \leq i$.

Now we prove that $P(i+1)$ holds:

$$
\begin{align}
P(i+1) &= 4^{i+1} + 14 \mod 6 = 0\\
&= 4^{i}\cdot 4 + 14 \mod 6 = 0
\end{align}
$$

Solution of Exercise 8
Let P(n) be the property “there exists integer m such that 4
n + 14 = 6m” (this is the definition
for a number to be divisible by 6).
Base Case: We prove P(1). This follows because 4
1 + 14 = 6 · 3.
Inductive Step: For i ≥ 1 assume P(i) is true. Then, as 4
i + 14 = 6m, by a simple rearrangement we have that 4
i = 6m − 14. Next we show that P(i + 1) also follows.
4
i+1 + 14 = 4(4i
) + 14
= 4(6m − 14) + 14 (inductive hp.)
= 24m − 42
= 6(4m − 7).
Indeed, from the above, m0 = 4m − 7 is the integer showing that P(i +