Induction

Exercise 3

Exercise

Prove the Generalized De Morgan's Laws, that is, $\forall n \in \mathbb{N}$,

$$\neg \left(\bigwedge\limits_{i=1}^n p_i\right) \equiv \bigvee\limits_{i=1}^n \neg p_i$$

and

$$\neg \left(\bigvee\limits_{i=1}^n p_i\right) \equiv \bigwedge\limits_{i=1}^n \neg p_i$$

Proof

Note that the cases $n=0$ and $n=1$ are straightforward. The case $n=2$ we know it as (normal) De Morgan's Laws. Let's assume the propositions are ${\color{green}\textbf{true}​}$ for $k\ge 2$, and we need to prove them for $k+1$

$$\begin{align*} \neg \left(\bigwedge\limits_{i=1}^{k+1} p_i\right) &\equiv \neg \left(\left(\bigwedge\limits_{i=1}^{k} p_i\right) \land p_{k+1}\right) & \\ & \equiv \left(\neg \left(\bigwedge\limits_{i=1}^{k} p_i\right) \lor \neg p_{k+1}\right) & \text{(De Morgan's Law)} \\ & \equiv \left(\left(\bigvee\limits_{i=1}^{k} \neg p_i\right) \lor \neg p_{k+1}\right) & \text{(Inductive Hypothesis)} \\ & \equiv \left(\bigvee\limits_{i=1}^{k+1} \neg p_i\right) \end{align*}$$

And analogously,

$$\begin{align*} \neg \left(\bigvee\limits_{i=1}^{k+1} p_i\right) &\equiv \neg \left(\left(\bigvee\limits_{i=1}^{k} p_i\right) \lor p_{k+1}\right) & \\ & \equiv \left(\neg \left(\bigvee\limits_{i=1}^{k} p_i\right) \land \neg p_{k+1}\right) & \text{(De Morgan's Law)} \\ & \equiv \left(\left(\bigwedge\limits_{i=1}^{k} \neg p_i\right) \land \neg p_{k+1}\right) & \text{(Inductive Hypothesis)} \\ & \equiv \left(\bigwedge\limits_{i=1}^{k+1} \neg p_i\right) \end{align*}$$

Exercise 4.b

Exercise

Let $P(n)$ be the statement that $n! < n^n$. This is a guided exercise to prove $\forall n \in \mathbb{N}_2$

1. What is $P(2)$?
2. Prove $P(2)$
3. What is the inductive hypothesis?
4. What do you need to prove in the inductive step?
5. Complete the inductive step
6. Explain why these steps show that this inequality is ${\color{green}\textbf{true}​}, \forall n \in \mathbb{N}_2$

Answer

1. $P(2)$ is the proposition $2! < 2^2$, it corresponds to the basis step
2. $P(2)$ is ${\color{green}\textbf{true}​}$ since $2! = 1\cdot 2 < 2 \cdot 2 = 2^2$
3. The inductive hypothesis is $P(k) \equiv k! < k^k$
4. In the inductive step one needs to prove that $\forall k \in \mathbb{N}_2, k! < k^k \Rightarrow (k+1)! < (k+1)^{k+1}$
5. Let $k \in \mathbb{N}_2$ and assume $k! < k^k$, then we compute

$$\begin{align*} (k+1)! &= k! \cdot (k+1) & \\ & < k^k \cdot (k+1) & \text{(Inductive Hypothesis)} \\ & < (k+1)^k \cdot (k+1) & \\ & = (k+1)^{k+1} \end{align*}$$

6. Because we have proven the basis step and inductive step of a proof by induction 😊

Exercise 5.a

Exercise

Consider the following proposition: $\forall n \in \mathbb{N}, 5n = 0$

What is wrong with this “proof” by strong induction?

• Basis Step: $5 \cdot 0 = 0$
• Inductive Step: Assume $5i = 0, \forall i \in \mathbb{N}, i \le k$. Write $k +1= i' +i''$, where $i'$ and $i''$ are natural numbers less than $k+1$. By the inductive hypothesis, $5(k +1)= 5(i' +i'')= 5i' +5i''= 0 +0= 0$

Answer

The basis step is valid. However, the inductive step only works when $k+1$ can be written as $i'+i''$ where both $i'$ and $i''$ are natural numbers less than $k+1$. This is not possible when $k=0$ (i.e., it is not possible to write $1$ as the sum of two natural numbers less than $1$)

Exercise 3.a

Exercise

Let $a_1, a_2, \ldots, a_n$ be positive real numbers. The arithmetic mean of these numbers is

$$A = \frac{\sum_{i=1}^{n}a_i}{n}$$

and the geometric mean of these numbers is

$$G= \left(\prod_{i=1}^n a_i\right)^{1/n}$$

Prove that $A \ge G, \forall n \in \mathbb{N}_2$

Proof

We prove this by Cauchy Induction, that is,

1. Prove $P(2)$: Suppose, for the sake of contradiction that $\frac{a_1+a_2}{2} < \sqrt{a_1a_2}$. Squaring, multiplying by $4$ and subtracting by $4a_1a_2$, we obtain $(a_1+a_2)^2 - 4a_1a_2 < 0$. Expanding the square we obtain $a_1^2 - 2a_1a_2 + a_2^2 < 0$. Finally, factoring the square we get $(a_1-a_2)^2 < 0$. This is a contradiction since the square of any real number (in this case $a_1 - a_2$) is non-negative
2. Prove $\forall k \in \mathbb{N}_2, P(k) \Rightarrow P(2k)$: Let $k \in \mathbb{N}_2$, then we need to prove that

$$\frac{\sum_{i=1}^{2k}a_i}{2k} \ge \left(\prod_{i=1}^{2k} a_i\right)^{1/(2k)}$$

We start by separating the sum

$$\begin{align*} \frac{\sum_{i=1}^{2k}a_i}{2k} &= \frac{\frac{\sum_{i=1}^{k}a_i}{k} + \frac{\sum_{i=k+1}^{2k}a_i}{k}​}{2} & \\ \\ & \ge \frac{\left(\prod_{i=1}^{k} a_i\right)^{1/k} + \left(\prod_{i=k+1}^{2k} a_i\right)^{1/k}​}{2} & \text{(ind. hyp. x2)} \\ \\ &\ge \sqrt{\left(\prod_{i=1}^{k} a_i\right)^{1/k}\left(\prod_{i=k+1}^{2k} a_i\right)^{1/k}​} & \text{($P(2)$)}\\ \\ & = \left(\prod_{i=1}^{2k} a_i\right)^{1/(2k)} \end{align*}$$

3. Prove $\forall k \in \mathbb{N}_2, P(k+1) \Rightarrow P(k)$: Let $k \in \mathbb{N}_2$. Then,

$$\begin{align*} \frac{\sum_{i=1}^{k}a_i}{k} &= \frac{k+1}{k+1}\cdot\frac{\sum_{i=1}^{k}a_i}{k}\\ \\ &= \frac{\frac{k \sum_{i=1}^{k}a_i + \sum_{i=1}^{k}a_i}{k}​}{k+1}\\ \\ &= \frac{\sum_{i=1}^{k}a_i + \frac{\sum_{i=1}^{k}a_i}{k} }{k+1}\\ \\ &= \frac{\sum_{i=1}^{k+1}a_i}{k+1} & \text{(with $a_{k+1}= \frac{\sum_{i=1}^{k}a_i}{k}$)}\\ \\ & \ge \left(\prod_{i=1}^{k+1} a_i\right)^{1/(k+1)} & \text{(ind. hyp.)} \end{align*}$$

Rewriting the inequality we obtain

$$a_{k+1} \ge \left(a_{k+1}\cdot\prod_{i=1}^{k} a_i\right)^{1/(k+1)}$$

Taking the power of $k+1$ and dividing by $a_{k+1}$ we obtain

$$(a_{k+1})^k \ge \left(\prod_{i=1}^{k} a_i\right)$$

Finally, taking the power of $1/k$ and rewriting $a_{k+1}$ we get

$$\frac{\sum_{i=1}^{k}a_i}{k} \ge \left(\prod_{i=1}^{k} a_i\right)^{1/k}$$

Exercise 4.a

Exercise

Prove that every positive integer can be written as a sum of distinct powers of two

Proof

By (strong) induction

• Basis step: $1$ can be written as $2^0$
• Inductive step:
  • Case 1: $k+1$ is even, then $(k+1)/2$ is a positive integer and by inductive hypothesis $(k+1)/2$ can be written as a sum of distinct powers of two, that is,

  $$(k+1)/2 = 2^{a_1} + \ldots + 2^{a_\ell}$$

  where $0 \le a_1 < \ldots < a_\ell$, and therefore

  $$k+1 = 2^{a_1+1} + \ldots + 2^{a_\ell+1}$$

  with $0 \le a_1+1 < \ldots < a_\ell+1$
  • Case 2: $k+1$ is odd, thus $k$ is even and by inductive hypothesis

  $$k = 2^{b_1} + \ldots + 2^{b_m}$$

  where $0 \le b_1 < \ldots < b_m$. Moreover, $b_1 > 0$, since otherwise $k$ would be odd (do you see why? 😃), and thus

  $$k +1 = 2^{0} + 2^{b_1} + \ldots + 2^{b_m}$$