14 - More examples of induction

In class practice

Proposition. For all integers $n \geq 10$ we have $2^{n} > n^{3}$ .

Scratch work:
Assume $2^{k} > k^{3}$ for some $k \in Z$ , $k \geq 10$ .
Want to show $2^{k + 1} > (k + 1)^{3}$

\begin{aligned} 2^{k + 1} & = 2 (2^{k}) \\ > 2 (k^{3}) \\ = k^{3} + k^{3} \end{aligned}

Also:

\begin{aligned} (k + 1)^{3} & = k^{3} + 3 k^{2} + 3 k + 1 \end{aligned}

HW 14

![[induction 1.pdf]]

Ben Finch

E 14.4
Proof.
Let $P (n)$ be the open statement:
For any $n \in N$ with $n \geq 2$ , if $P_{1}, . . ., P_{n}$ are statements, then $$¬(P_1 ∧···∧P_n)≡(¬P_1)∨···∨(¬P_n)$$
Base Case: (n=2) ¬(P1 ∧ P2) is equivalent to (¬P1 ∨ ¬P2) based on DeMorgan's law.

Inductive step:
Assume that the statement is true for $n = k$ .

We aim to prove the statement is true for $n = k + 1$ .

Consider $\neg (P_{1} \land P_{2} \land . . . \land P_{k} \land P_{k + 1})$ .

We can rewrite this as $\neg (P_{1} \land P_{2} \land . . . \land P_{k}) \land P_{k + 1}$ .

Applying DeMorgan's law to the rewritten expression gives us $\neg (P_{1} \land P_{2} \land . . . \land P_{k}) \lor \neg P_{k + 1}$ .

By the induction hypothesis, we know that ¬(P_1 ∧ P_2 ∧...∧ P_k) is equivalent to $\neg P_{1} \lor \neg P_{2} \lor . . . \lor \neg P_{k}$ .

Substituting this into the expression gives us $\neg P_{1} \lor \neg P_{2} \lor . . . \lor \neg P_{k} \lor \neg P_{k + 1}$ .

Thus for any $n \in N$ with $n \geq 2$ , if $P_{1}, . . ., P_{n}$ are statements, then $\neg (P_{1} \land \cdot \cdot \cdot \land P_{n}) \equiv (\neg P_{1}) \lor \cdot \cdot \cdot \lor (\neg P_{n})$ . $◻$

E 14.5

Proof.

Base case: let $n = 1$ . For any $x_{1} \in R$ ,

| \sum_{i = 1}^{1} x_{i} | = | x_{1} | = \sum_{i = 1}^{1} | x_{i} |

So the proposition holds for $n = 1$ .

Inductive step.
We assume that the proposition holds for some $n = k$ :

| \sum_{i = 1}^{k} x_{i} | \leq \sum_{i = 1}^{k} | x_{i} |

We need to prove that the proposition holds for $n = k + 1$ :

| \sum_{i = 1}^{k + 1} x_{i} | = | \sum_{i = 1}^{k} x_{i} + x_{k + 1} |

According to the triangle inequality, we know that:

| \sum_{i = 1}^{k} x_{i} + x_{k + 1} | \leq | \sum_{i = 1}^{k} x_{i} | + | x_{k + 1} |

By the induction hypothesis, we can replace $| \sum_{i = 1}^{k} x_{i} |$ with $\sum_{i = 1}^{k} | x_{i} |$ :

| \sum_{i = 1}^{k} x_{i} | + | x_{k + 1} | \leq \sum_{i = 1}^{k} | x_{i} | + | x_{k + 1} | = \sum_{i = 1}^{k + 1} | x_{i} |

Therefore, by the principle of mathematical induction, the proposition holds for all $n \in N$ . $◻$

E 14.6
a) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
b) Proof.
Base Case:
Begin with the base case where $n = 1$ . For this case, the formula becomes $$\sum_{i=1}^{1} F_{i}= F_{1+2}-1$$Using the definitions of $F_{1}$ and $F_{3}$ , we get $F_{1} = F_{3} - 1$ , which simplifies to $1 = 2 - 1 = 1$ . Thus, the formula holds for the base case.

Inductive Step:
Assume the formula $\sum_{i = 1}^{k} F_{i} = F_{k + 2} - 1$ to be true for some positive integer $k$ .

We aim to prove $\sum_{i = 1}^{k + 1} F_{i} = F_{(k + 1) + 2} - 1$ .

We start by expanding the left hand side:

\begin{aligned} \sum_{i = 1}^{k + 1} F_{i} & = F_{k + 1} + \sum_{i = 1}^{k} F_{i} \end{aligned}

Next, we apply the induction assumption:

\begin{aligned} = F_{k + 1} + (F_{k + 2} - 1) \end{aligned}

Simplify the equation:

\begin{aligned} = F_{k + 2} + F_{k + 1} - 1 \end{aligned}

By the definition, we know that $F_{k + 3} = F_{k + 2} + F_{k + 1}$ , so we replace these terms:

\begin{aligned} = F_{k + 3} - 1 \end{aligned}

Therefore, by mathematical induction, the formula is true. $◻$

c) Proof.

Let $P (n)$ be the open statement that for each $n \in N$ ,

\sum_{i = 1}^{n} F_{i}^{2} = F_{n} F_{n + 1}

Base Case (n = 1): We see that P(1) is true:

\begin{aligned} \sum_{i = 1}^{1} F_{1}^{2} & = F_{1} (F_{2}) \\ 1 & = 1 * 1 \\ 1 & = 1 \end{aligned}

Inductive step
Assume that for some $n = k$ ,

\sum_{i = 1}^{k} F_{i}^{2} = F_{k} F_{k + 1}

We aim to prove that the property holds for $n = k + 1$ :

\sum_{i = 1}^{k + 1} F_{i}^{2} = F_{k + 1} F_{k + 2}

We can write the left-hand side as

\begin{aligned} \sum_{i = 1}^{k + 1} F_{i}^{2} & = \sum_{i = 1}^{k} F_{i}^{2} + F_{k + 1}^{2} \end{aligned}

By the induction hypothesis, we can replace $\sum_{i = 1}^{k} F_{i}^{2}$ with $F_{k} F_{k + 1}$ , which gives us

\sum_{i = 1}^{k + 1} F_{i}^{2} = F_{k} F_{k + 1} + F_{k + 1}^{2}

This expression can be rewritten as

\sum_{i = 1}^{k + 1} F_{i}^{2} = F_{k + 1} (F_{k} + F_{k + 1})

But we know from the Fibonacci sequence property $F_{k + 2} = F_{k} + F_{k + 1}$ , so we can replace $(F_{k} + F_{k + 1})$ with $F_{k + 2}$ .

This gives us

\sum_{i = 1}^{k + 1} F_{i}^{2} = F_{k + 1} F_{k + 2}

Hence, the property holds for $n = k + 1$ if it holds for $n = k$ . Thus for each $n \in N$ $$\sum_{i=1}^{n}F_i^{2}= F_nF_{n+1}$$
$◻$

E 14.7

Let the open sentence $P (n)$ be:

$F_{n} > n^{2}$ and $F_{n - 1} > (n - 1)^{2}$ .

We want to prove P(n) is true for all $n \geq 14$ . This would imply that $F_{n} > n^{2}$ for all $n \geq 13$ .

Base Case:

Let $n = 14$ . Thus $F_{14} = 377 > 14^{2} = 196$ and $F_{13} = 233 > 13^{2} = 169$ . Thus, P(14) is true.

Inductive Step:

Assume that P(k) is true for some $k \geq 14$ , $k \in N$ . This means that $F_{k} > k^{2}$ and $F_{k - 1} > (k - 1)^{2}$ .

We aim to prove that $P (k + 1)$ is true, that is, $F_{k + 1} > (k + 1)^{2}$ and $F_{k} > k^{2}$ .

From the definition of Fibonacci numbers, we know that:

F_{k + 1} = F_{k} + F_{k - 1}

By the inductive hypothesis, we know $F_{k} > k^{2}$ and $F_{k - 1} > (k - 1)^{2}$ . Adding these inequalities we get:

F_{k + 1} = F_{k} + F_{k - 1} > k^{2} + (k - 1)^{2}

This simplifies to:

F_{k + 1} > 2 k^{2} - 2 k + 1 = (k - 1)^{2} + (k + 1)^{2}

Since for $k \geq 14$ , $(k - 1)^{2} + (k + 1)^{2} > (k + 1)^{2}$ , it follows that:

F_{k + 1} > (k + 1)^{2}

This is what we needed to prove. Therefore, the proposition P(k + 1) is true, and the inductive step is complete.

Hence, by mathematical induction, the proposition P(n) is true for all $n \geq 14$ . As a result, $F_{n} > n^{2}$ for all $n \geq 13$ .