13 - Induction

!Screenshot 2023-10-09 at 10.05.42 AM.png

In Class Practice

Given $n \in N$ , it happens that $2^{n} > n$ .

Scratch work:
Open sentence: $P (n) : 2^{n} > n$
Base case: P(1): $2^{1} > 1$
Inductive step: Show that $P (k) ⟹ P (k + 1)$
Let $k \in N$ . Assume $2^{k} > k$
We want to show that $2^{k + 1} > k + 1$ . We have that

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

(since $k \geq 1$ )

Formal Proof:
We work by induction on $n \in N$ .
Let $P (n) : 2^{n} > n$ .
Base Case. Fix $n = 1$ . We see that $2^{1} > 1$
Inductive step.
Let $k \in N$ . Assume $2^{k} > k .$
Then

\begin{aligned} 2^{k + 1} & = 2 (2^{k}) \\ > 2 k (since P(k) is true) \\ = (k - 1) + (k + 1) \\ \geq k + 1 (since k \geq 1) \end{aligned}

Thus $P (k + 1) : 2^{k + 1} > k + 1$ is true. By the principle of mathematical induction, $P (n) is true for all n \in N$ . $◻$

Proposition. Let $A$ be a finite nonempty set of real numbers. Then $A$ has a least element.

Idea of the proof:

If $| A | = 1$ , then $A$ clearly has a least element
If $| A | = 2$ , clearly true

Open sentence: $P (n) : If | A | = n, then A$ has a least element.

Let $K \in N$ .
Assume P(k) is true.
We want to show $P (k + 1)$ is true.
Let A have $k + 1$ elements. Let $x \in A$ . Let $B = A - {x}$ .
Then by assumption $B$ has a least element, call it $y$ . Then $min (x, y)$ is the least element of $A$ . $◻$

Pigeonhole principle:
Three pigeonholes, five pigeons. At least 1 pigeonhole has more than one pigeon in it.

HW 13

Ben Finch

E 13.1
Let $P (n)$ be the open sentence

\sum_{i = 1}^{n} (2 i - 1) = n^{2}

We work by induction to prove that $P (n)$ is true for each $n \in N$ .
Base Case: We have

\begin{aligned} P (1) = 2 (1) - 1 & = 1^{2} \\ 2 - 1 & = 1^{2} \\ 1 & = 1 \end{aligned}

is true.
Inductive step: Let $k \in N$ and assume that

P (k) : \sum_{i = 1}^{k} (2 i - 1) = k^{2}

is true. We want to show that:

P (k + 1) : \sum_{i = 1}^{k + 1} (2 i - 1) = (k + 1)^{2}

is true.

Then,

\begin{aligned} \sum_{i = 1}^{k + 1} (2 i - 1) & = \sum_{i = 1}^{k} (2 i - 1) + 2 (k + 1) - 1 \\ = k^{2} + 2 (k + 1) - 1 [by the inductive assumption] \\ = k^{2} + 2 k + 1 \\ = (k + 1)^{2} \end{aligned}

So, if $P (k)$ is true, then $P (k + 1)$ is also true.

Therefore, the statement $\sum_{i = 1}^{n} (2 i - 1) = n^{2}$ holds for all $n \in N$ . $◻$

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

\sum_{i = 1}^{n} \frac{1}{(2 i - 1) (2 i + 1)} = \frac{n}{2 n + 1}

We work by induction to prove that $P (n)$ is true for each $n \in N$ .

Base case: $P (1)$ is true since we have

\begin{aligned} P (1) = \frac{1}{(2 (1) - 1) (2 (1) + 1)} & = \frac{1}{2 (1) + 1} \\ \frac{1}{3} & = \frac{1}{3} \end{aligned}

Inductive step. Let $k \in N$ and assume that

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

is true. We want to show that:

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

We find:

\begin{aligned} \sum_{i = 1}^{k + 1} \frac{1}{(2 i - 1) (2 i + 1)} & = \sum_{i = 1}^{k} \frac{1}{(2 i - 1) (2 i + 1)} + \frac{1}{(2 (k + 1) - 1) (2 (k + 1) + 1)} \\ = \frac{k}{2 k + 1} + \frac{1}{(2 k + 1) (2 k + 3)} [by the inductive assumption] \\ = \frac{(2 k + 3) (k) + 1}{(2 k + 1) (2 k + 3)} \\ = \frac{2 k^{2} + 3 k + 1}{(2 k + 1) (2 k + 3)} \\ = \frac{(2 k + 1) (k + 1)}{(2 k + 1) (2 k + 3)} \\ = \frac{k + 1}{2 (k + 1) + 1} \end{aligned}

Therefore, $P (n)$ is true for all $n \in N$ . $◻$

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

\sum_{i = 1}^{n} i^{2} = \frac{n (n + 1) (2 n + 1)}{6}

We work by induction to prove that $P (n)$ is true for each $n \in N$ .
Base Case. $P (1)$ is true since we have

\begin{aligned} P (1) = 1^{2} & = \frac{1 (1 + 1) (2 (1) + 1)}{6} \\ 1 & = \frac{2 (3)}{6} \\ 1 & = 1 \end{aligned}

Inductive Step. Let $k \in N$ and assume.

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

We want to show that:

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

We have

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

Therefore $P (n)$ is true for all $n \in N$ . $◻$

E 13.4
a)
Let $P (n)$ be the open statement $n < 3^{n}$ .
We work by induction to prove $P (n)$ for all $n \in N$ .
Base Case:
We see that $1 < 3^{1} = 3$ .
Inductive step:
Let $k \in N$ . Assume that $k < 3^{k}$ . We want to prove that $k + 1 < 3^{k + 1}$ . We find

\begin{aligned} k + 1 & < 3^{k} + 1 & (by the inductive assumption) \\ < 3^{k} + 3^{k} \\ = 2 \cdot 3^{k} \\ < 3 \cdot 3^{k} \\ = 3^{k + 1} . \end{aligned}

Thus $P (n)$ is true for all $n \in N$ . $◻$

b)
For $n \in Z$ , we have two cases: $n \leq 0$ and $n > 0$ .

For $n \leq 0$ , we have:

n \leq 0 < 3 n

For $n > 0$ , by the result of part (a), we know that $n < 3^{n}$ . Since $3^{n} \leq 3 n$ for $n > 0$ , we can conclude that:

n < 3^{n} \leq 3 n

Therefore, in both cases, we have $n < 3 n$ for all $n \in Z$ .

E 13.5
Let $x \in R - {1}$ . Let $P (n)$ be the open sentence:

\sum_{i = 1}^{n} x^{i} = \frac{1 - x^{n + 1}}{1 - x}

We aim to prove $P (n)$ for all $n \in N$ .

The proof will be done by induction.

Base case:
Substituting $n = 1$ into the equation, we get

\begin{aligned} x & = \frac{1 - x^{1 + 1}}{1 - x} \\ x & = \frac{1 - x^{2}}{1 - x} \\ x & = \frac{(1 - x) (1 + x)}{1 - x} \\ x & = x \end{aligned}

So, $P (1)$ is true.

Inductive step:

Let $k \in R$ . Assume $P (k)$ is true:

\sum_{i = 1}^{k} x^{i} = \frac{1 - x^{k + 1}}{1 - x}

We aim to show $P (k + 1)$ is true:

\sum_{i = 1}^{k + 1} x^{i} = \frac{1 - x^{k + 2}}{1 - x}

We find:

\begin{aligned} \sum_{i = 1}^{k + 1} x^{i} & = \sum_{i = 1}^{k} x^{i} + x^{k + 1} \\ = \frac{1 - x^{k + 1}}{1 - x} + x^{k + 1} & (by the inductive assumption) \\ = \frac{1 - x^{k + 1} + (1 - x) x^{k + 1}}{1 - x} \\ = \frac{1 - x^{k + 1} (1 - x)}{1 - x} \\ = \frac{1 - x^{k + 2}}{1 - x} \end{aligned}

Therefore, $P (k + 1)$ is true, assuming that $P (k)$ is true.

Thus $P (n)$ is true for all $n \in N$ . $◻$

E 13.6
Let $P (n)$ be the open statement $(1 + x)^{n} \geq 1 + n x$
Base Case:

\begin{aligned} (1 + x)^{1} & \geq 1 + 1 x \\ 1 + x & \geq 1 + x \end{aligned}

The base case holds true.

Inductive step:
Let $k \in N$ . Assume $(1 + x)^{k} \geq 1 + k x$ .
We aim to prove $(1 + x)^{k} + 1 \geq 1 + (k + 1) x$

\begin{aligned} (1 + x)^{k + 1} & = (1 + x)^{k} * (1 + x) \\ \geq (1 + k x) * (1 + x) (Using inductive assumption) \\ = 1 + k x + x + k x^{2} \\ = 1 + (k + 1) x + k x^{2} \\ \geq 1 + (k + 1) x (Since x^{2} \geq 0 as x \in R) \end{aligned}

Thus $P (n)$ is true for all $n \in N$ .

E 13.7
Let $S$ be some nonempty set of natural numbers.

Consider the set $A = {k \in N : k \leq n$ for some $n \in S}$ . $A$ is a nonempty subset of natural numbers because $S$ is nonempty.

According to Proposition 13.11, since $A$ is a finite nonempty set of real numbers, it has a least element, call it $m$ .

Assume by way of contradiction that $m$ is not the least element of $S$ . Then, there exists an element $p \in S$ such that $p < m$ .

Since $p$ is in $S$ , it implies that $p$ is also in $A$ because $A$ contains all natural numbers less than or equal to some element in $S$ . However, this contradicts the fact that $m$ is the least element of $A$ .

Therefore, our assumption is false, and m must be the least element of $S$ .

Hence, any nonempty set of natural numbers, $S$ , has a least element. $◻$

E 13.8
Proof:
Let $m \in N \cup 0$ , let $n \in N$ , and assume $m < n$ . We aim to prove that the open sentence:

If m objects are placed in n bins, some bin does not contain any object.

We work by way of induction.

Base Case: For $n = 1$ , the statement holds trivially because we assume $m < n$ and so if $m = 0$ and $n = 1$ , we have 1 bin which is empty.

Inductive Step:
Assume the statement holds for some $n = k$ .

We need to show that the statement holds for $n = k + 1$ .

Consider $m$ objects in $k + 1$ bins. Since $m < k + 1$ , we have two cases:

If $m < k$ , by inductive assumption, at least one bin remains empty when $m$ objects are placed in $k$ bins. Adding another bin to make it $k + 1$ bins, we will have more than one bin that is empty.
If $m = k$ , every bin among the $k$ bins gets one object. Adding one additional bin to make it $k + 1$ bins will leave that additional bin empty.

Therefore the statement holds for all $n$ . $◻$