Tutorial: More Induction

2025-05-21

1 Prime Factorization

For any number $n \in \mathbb{N}$ with $n \geq 2$. $n$ can be written as the product of one or more prime numbers.

Prove it using (complete induction).
Prove it using the Well Ordering Principle.

Solution

By complete induction

Base case. $2$ is prime so the base case holds.

Inductive step. Let $k \in \mathbb{N}$ be any number with $k \geq 2$, and assume that any number between 2 and $k$ can be written as the product of prime numbers. Consider $k+1$. If $k+1$ is prime, then we are done. Otherwise, $k+1 = a\cdot b$ for some numbers $a , b$ with $2 \leq a, b < k+1$. Thus, the inductive hypothesis applies to $a$ and $b$, so $a = a_1a_2...a_i$ and $b = b_1b_2...b_j$, where each of the $a_i$s and $b_i$s are prime. Therefore $k+1 = a_1a_1...a_ib_1b_2...b_j$ and is also the product of primes. This completes the induction.

By the WOP

By contradiction, assume the claim is false, let $S = \{n \in \mathbb{N}: n \geq 2, \text{$n$ is not the product of primes}\}$.

Since $S$ is non-empty, there is some minimal element $m$.

Since $m$ can not be written as the product of primes, it must not be prime itself. Thus $m = ab$ for some $2 \leq a, b < m$. Since $m$ can not be written as the product of primes, at least one of $a$ or $b$ can not be written as the product of primes. But this contradicts the minimality of $m$ in $S$!

2 … generates

2.1

Let $\mathrm{Palindrome} = \{w: w \text{ is a palindrome }\}$. Note a palindrome is any string that is the same when read backwards. The empty string, which we’ll denote as $\epsilon$, counts as a palindrome.

Generate $\mathrm{Palindrome}$.

Solution

$B = \{\epsilon, a,b,...,z\}$. For each character $\alpha$, define $f_\alpha$ to be the function that maps $x \mapsto \alpha x \alpha$. Set $F = \{f_\alpha: \alpha \in \{a,...,z\} \}$

2.2

Write a construction sequence for ‘tacocat’.

Solution

We have \[ \text{tacocat} = f_t(f_a(f_c(o))). \]

So a valid construction sequence for ‘tacocat’ is [o,coc,acoca,tacocat]. Note that each element of the sequence is either in $B$ or $f_\alpha(x)$ where $x$ is some earlier element in the sequence.

2.3

Let $\mathrm{Even} = \{w: w \text{ is a bitstring with an even number of 1s }\}$. A bit string is a sequence of $0$s and $1s$. Does $B = \{\epsilon\}$, $F=\{x\mapsto x0, x\mapsto x11\}$ work? If not, explain why and come up with a fix.

Generate $\mathrm{Even}$

Solution

The proposal doesn’t work b/c can’t generate 100001 for example - 1s are always next to each other! Here is one fix.

$B = \{\epsilon\}$. $F=\{x\mapsto x0, x\mapsto 1x1, x\mapsto 0x\}$

3 Pairs

Let $B = \{(0,0)\}$, and $f_1, f_2, f_3$ be the functions defined as follows

$f_1(a, b) = (a, b+1)$
$f_2(a, b) = (a+1, b+1)$
$f_3(a, b) = (a+2, b+1)$

3.1

Let $X$ be the set generated from $B$ by $\{f_1,f_2,f_3\}$. Show that for all $(a, b) \in X$, $a \leq 2b$.

Solution

By structural induction. Let $P(a, b)$ be the predicate that $a \leq 2b$.

Base case. $0 \leq 2\cdot 0$, so the base case holds.

Inductive Step.

$f_1$. Suppose $a \leq 2b$, then $a \leq 2b + 2 = 2(b+1)$, so $P(f_1(a, b)) = P(a, b+1)$ holds.
$f_2$. Suppose $a \leq 2b$. then $a + 1 \leq 2b + 2$, so $P(f_2(a, b))$ holds.
$f_3$. Suppose $a \leq 2b$. then $a + 2 \leq 2b + 2$, so $P(f_3(a, b))$ holds.

This completes the induction.

4 Nim

Nim is a two player game that works as follows.

There are two piles of stones. Each pile has the $n$ stones for some $n \in \mathbb{N}$.
The players alternate taking some (non-zero) number of stones from one pile.
If at the start of a player’s turn, all piles are empty, then that player loses.

Play this game with someone with $n = 15$!

4.1

Prove that for all $n \in \mathbb{N}$, there is a winning strategy for the second player.

Solution

The winning strategy for player 2 do whatever player 1 did in the previous turn but to the other pile! We’ll show this strategy works for all $n$ by induction.

Base case. For $n = 0$, it is player 1’s turn and there are no more stones left in either pile, thus player 1 loses.

Inductive step. Let $k \in \mathbb{N}$ be some natural number. Assume the strategy works for every $i \in \mathbb{N}$ with $i \leq k$. Consider the game with $k+1$ stones in each pile. Player 1 takes $x$ stones from one pile for some $1 \leq x \leq k+1$. Applying the strategy, player 2 takes $x$ stones from the other pile. Thus, both piles have $k+1 - x$ stones. Since $x \geq 1$, $k+1-x \leq k$, thus, the inductive hypothesis applies and player 2 wins using this strategy.