Recursive Definitions & Structural Induction

Textbook

Rosen 8e, Section 5.3

Study day

Friday, Nov 6

Homework

Written HW 6: 1, 3, 7, 9–11, 13, 22–27, 31, 33–46, 50–57

Progress

Notes not read 0 / 38 problems graded

Work each problem on paper before opening its solution, then mark it Got it or Review. Do the Core problems first if you're short on time.

5.3 #1 Core Computing values

Find $f (1), f (2), f (3)$ , and $f (4)$ if $f (n)$ is defined recursively by $f (0) = 1$ and for $n = 0, 1, 2, \dots$

a) $f (n + 1) = f (n) + 2$
b) $f (n + 1) = 3 f (n)$
c) $f (n + 1) = 2^{f (n)}$
d) $f (n + 1) = f (n)^{2} + f (n) + 1$

Show solution

Answer

a) 3, 5, 7, 9 b) 3, 9, 27, 81 c) 2, 4, 16, 65536 d) 3, 13, 183, 33673

Fill in the table one value at a time, starting from $f (0) = 1$ .

a) $f (1) = 1 + 2 = 3$ , $f (2) = 5$ , $f (3) = 7$ , $f (4) = 9$ .

b) $f (1) = 3$ , $f (2) = 9$ , $f (3) = 27$ , $f (4) = 81$ .

c) $f (1) = 2^{1} = 2$ , $f (2) = 2^{2} = 4$ , $f (3) = 2^{4} = 16$ , $f (4) = 2^{16} = 65, 536$ .

d) $f (1) = 1 + 1 + 1 = 3$ , $f (2) = 9 + 3 + 1 = 13$ , $f (3) = 169 + 13 + 1 = 183$ , $f (4) = 18 3^{2} + 183 + 1 = 33, 489 + 184 = 33, 673$ .

5.3 #3 Core Computing values

Find $f (2), f (3), f (4)$ , and $f (5)$ if $f$ is defined recursively by $f (0) = - 1$ , $f (1) = 2$ , and for $n = 1, 2, \dots$

a) $f (n + 1) = f (n) + 3 f (n - 1)$
b) $f (n + 1) = f (n)^{2} f (n - 1)$
c) $f (n + 1) = 3 f (n)^{2} - 4 f (n - 1)^{2}$
d) $f (n + 1) = f (n - 1) / f (n)$

Show solution

Answer

a) −1, 5, 2, 17 b) −4, 32, −4096, 536870912 c) 8, 176, 92672, 25764174848 d) −1/2, −4, 1/8, −32

Two starting values are given, and each new value uses the two previous ones.

$f (2) = f (1) + 3 f (0) = 2 - 3 = - 1$
$f (3) = f (2) + 3 f (1) = - 1 + 6 = 5$
$f (4) = 5 + 3 (- 1) = 2$
$f (5) = 2 + 3 (5) = 17$

$f (2) = f (1)^{2} f (0) = 4 (- 1) = - 4$
$f (3) = (- 4)^{2} \cdot 2 = 32$
$f (4) = 3 2^{2} \cdot (- 4) = 1024 \cdot (- 4) = - 4096$
$f (5) = (- 4096)^{2} \cdot 32 = 536, 870, 912$

$f (2) = 3 (2)^{2} - 4 (- 1)^{2} = 12 - 4 = 8$
$f (3) = 3 (64) - 4 (4) = 176$
$f (4) = 3 (17 6^{2}) - 4 (8^{2}) = 92, 928 - 256 = 92, 672$
$f (5) = 3 (9267 2^{2}) - 4 (17 6^{2}) = 25, 764, 174, 848$

$f (2) = f (0) / f (1) = - 1/2$
$f (3) = f (1) / f (2) = 2/ (- 1/2) = - 4$
$f (4) = f (2) / f (3) = (- 1/2) / (- 4) = 1/8$
$f (5) = f (3) / f (4) = - 4/ (1/8) = - 32$

5.3 #7 Core Explicit → recursive

Give a recursive definition of the sequence ${a_{n}}$ , $n = 1, 2, 3, \dots$ if

a) $a_{n} = 6 n$ b) $a_{n} = 2 n + 1$ c) $a_{n} = 1 0^{n}$ d) $a_{n} = 5$

Show solution

Answer

a) $a_{1} = 6$ , $a_{n + 1} = a_{n} + 6$ b) $a_{1} = 3$ , $a_{n + 1} = a_{n} + 2$ c) $a_{1} = 10$ , $a_{n + 1} = 10 a_{n}$ d) $a_{1} = 5$ , $a_{n + 1} = a_{n}$

The sequence starts at $n = 1$ , so the basis is $a_{1}$ . For the recursive step, compute $a_{n + 1}$ and rewrite it in terms of $a_{n}$ .

a) $a_{n + 1} = 6 (n + 1) = 6 n + 6 = a_{n} + 6$ . So $a_{1} = 6$ , $a_{n + 1} = a_{n} + 6$ for $n \geq 1$ .

b) $a_{n + 1} = 2 (n + 1) + 1 = (2 n + 1) + 2 = a_{n} + 2$ . So $a_{1} = 3$ , $a_{n + 1} = a_{n} + 2$ .

c) $a_{n + 1} = 1 0^{n + 1} = 10 \cdot 1 0^{n} = 10 a_{n}$ . So $a_{1} = 10$ , $a_{n + 1} = 10 a_{n}$ .

d) Constant: $a_{1} = 5$ , $a_{n + 1} = a_{n}$ .

5.3 #9 Core Explicit → recursive

Let $F$ be the function such that $F (n)$ is the sum of the first $n$ positive integers. Give a recursive definition of $F (n)$ .

Show solution

Answer

$F (0) = 0$ ; $F (n) = F (n - 1) + n$ for $n \geq 1$ .

The sum of the first $n$ positive integers is the sum of the first $n - 1$ plus the next one, $n$ .

Basis: $F (0) = 0$ (empty sum). Equivalently $F (1) = 1$ .
Recursive step: $F (n) = F (n - 1) + n$ for $n \geq 1$ .

Check: $F (1) = 1$ , $F (2) = 3$ , $F (3) = 6$ , $F (4) = 10$ . ✓

5.3 #10 Core Explicit → recursive

Give a recursive definition of $S_{m} (n)$ , the sum of the integer $m$ and the nonnegative integer $n$ .

Show solution

Answer

$S_{m} (0) = m$ ; $S_{m} (n + 1) = S_{m} (n) + 1$ .

Recurse on $n$ (the nonnegative one), building addition out of "add 1."

Basis: $S_{m} (0) = m + 0 = m$ .
Recursive step: $S_{m} (n + 1) = m + (n + 1) = (m + n) + 1 = S_{m} (n) + 1$ .

5.3 #11 Core Explicit → recursive

Give a recursive definition of $P_{m} (n)$ , the product of the integer $m$ and the nonnegative integer $n$ .

Show solution

Answer

$P_{m} (0) = 0$ ; $P_{m} (n + 1) = P_{m} (n) + m$ .

This one was done in class (Problem 11). Recurse on $n$ , building multiplication out of repeated addition.

Basis: $P_{m} (0) = m \cdot 0 = 0$ .
Recursive step: $P_{m} (n + 1) = m (n + 1) = mn + m = P_{m} (n) + m$ .

5.3 #13 Core Fibonacci induction

Prove that $f_{1} + f_{3} + \dots + f_{2 n - 1} = f_{2 n}$ when $n$ is a positive integer. ( $f_{n}$ is the $n$ th Fibonacci number.)

Show solution

Let $P (n)$ : $f_{1} + f_{3} + \dots + f_{2 n - 1} = f_{2 n}$ . Use ordinary induction on $n \geq 1$ .

Basis ( $n = 1$ ): LHS $= f_{1} = 1$ , RHS $= f_{2} = 1$ . ✓

Inductive step. Assume $P (k)$ : $f_{1} + f_{3} + \dots + f_{2 k - 1} = f_{2 k}$ . Then
$f_{1} + f_{3} + \dots + f_{2 k - 1} + f_{2 k + 1} = f_{2 k} + f_{2 k + 1} = f_{2 k + 2} = f_{2 (k + 1)} . (IH) (Fibonacci recurrence)$
So $P (k + 1)$ holds. By induction, $P (n)$ is true for all $n \geq 1$ . ∎

Pattern

In Fibonacci proofs, the step almost always ends with $f_{j} + f_{j + 1} = f_{j + 2}$ . Aim for that.

5.3 #22 Core Set equality

Show that the set $S$ defined by $1 \in S$ and $s + t \in S$ whenever $s \in S$ and $t \in S$ is the set of positive integers.

Show solution

Show both inclusions.

$Z^{+} \subseteq S$ (induction on $n$ ). Let $P (n)$ : $n \in S$ .

Basis: $1 \in S$ by the basis step.
Step: if $k \in S$ , then since $1 \in S$ , the recursive step gives $k + 1 \in S$ .

So every positive integer is in $S$ .

$S \subseteq Z^{+}$ (structural induction).

Basis: $1 \in Z^{+}$ .
Step: if $s, t \in S$ are positive integers (IH), then $s + t$ is a positive integer.

So every element of $S$ is a positive integer. Therefore $S = Z^{+}$ . ∎

5.3 #23 Core Recursive sets

Give a recursive definition of the set of positive integers that are multiples of 5.

Show solution

Answer

Basis: $5 \in S$ . Recursive: if $x \in S$ then $x + 5 \in S$ . (Also fine: if $x, y \in S$ then $x + y \in S$ .)

Basis step: $5 \in S$ .
Recursive step: if $x \in S$ , then $x + 5 \in S$ .

This generates $5, 10, 15, \dots$ , exactly the positive multiples of 5. An equally correct alternative (the class example): if $x \in S$ and $y \in S$ , then $x + y \in S$ .

5.3 #24 Core Recursive sets

Give a recursive definition of

a) the set of odd positive integers.
b) the set of positive integer powers of 3.
c) the set of polynomials with integer coefficients.

Show solution

a) Basis: $1 \in S$ . Recursive: if $x \in S$ then $x + 2 \in S$ . (Generates $1, 3, 5, \dots$ )

b) Basis: $3 \in S$ . Recursive: if $x \in S$ then $3 x \in S$ . (Generates $3, 9, 27, \dots$ ) If you count $3^{0} = 1$ , use basis $1 \in S$ instead.

c) Let $P$ be the set of polynomials in $x$ with integer coefficients.

Basis: every integer $a$ (a constant polynomial) is in $P$ .
Recursive step: if $p (x) \in P$ and $a \in Z$ , then $x \cdot p (x) + a \in P$ .

This builds any $a_{n} x^{n} + \dots + a_{1} x + a_{0}$ in "Horner form" $(\dots ((a_{n}) x + a_{n - 1}) x + \dots) x + a_{0}$ . Another valid answer: Basis: $x \in P$ and every integer is in $P$ . Recursive: if $p, q \in P$ then $p + q \in P$ and $p \cdot q \in P$ .

5.3 #25 Core Recursive sets

Give a recursive definition of

a) the set of even integers.
b) the set of positive integers congruent to 2 modulo 3.
c) the set of positive integers not divisible by 5.

Show solution

a) Includes negatives, so you must go both ways. Basis: $0 \in S$ . Recursive: if $x \in S$ then $x + 2 \in S$ and $x - 2 \in S$ .

b) The set is $2, 5, 8, 11, \dots$ Basis: $2 \in S$ . Recursive: if $x \in S$ then $x + 3 \in S$ .

c) The set is $1, 2, 3, 4, 6, 7, 8, 9, 11, \dots$ (period 5). Basis: $1, 2, 3, 4 \in S$ . Recursive: if $x \in S$ then $x + 5 \in S$ .

(Compare the class example: positive integers not divisible by 7 had basis $1, \dots, 6$ and rule $x \mapsto x + 7$ .)

5.3 #26 Core Structural induction

Let $S$ be the set of positive integers defined by

Basis step: $1 \in S$ .
Recursive step: if $n \in S$ , then $3 n + 2 \in S$ and $n^{2} \in S$ .

a) Show that if $n \in S$ , then $n \equiv 1 (mod 4)$ .
b) Show that there exists an integer $m \equiv 1 (mod 4)$ that does not belong to $S$ .

Show solution

a) Structural induction.

Basis: $1 \equiv 1 (mod 4)$ . ✓
Recursive step: Assume $n \in S$ with $n \equiv 1 (mod 4)$ (IH). Two rules, two cases:
- $3 n + 2 \equiv 3 (1) + 2 = 5 \equiv 1 (mod 4)$ . ✓
- $n^{2} \equiv 1^{2} = 1 (mod 4)$ . ✓

So every element of $S$ is $\equiv 1 (mod 4)$ . ∎

b) Take $m = 9$ . Then $9 \equiv 1 (mod 4)$ . Suppose $9 \in S$ . It's not the basis element, so it came from a recursive rule:

$9 = 3 n + 2$ gives $n = 7/3$ , not an integer. ✗
$9 = n^{2}$ gives $n = 3$ . But $3 \neq \equiv 1 (mod 4)$ , so $3 \in / S$ by part (a). ✗

So $9 \in / S$ . (Elements of $S$ are $1, 5, 17, 25, 53, \dots$ ; 9 and 13 never appear.)

5.3 #27 Core Structural induction

Let $S$ be the set of positive integers defined by

Basis step: $5 \in S$ .
Recursive step: if $n \in S$ , then $3 n \in S$ and $n^{2} \in S$ .

a) Show that if $n \in S$ , then $n \equiv 5 (mod 10)$ .
b) Show that there exists an integer $m \equiv 5 (mod 10)$ that does not belong to $S$ .

Show solution

a) Structural induction.

Basis: $5 \equiv 5 (mod 10)$ . ✓
Recursive step: Assume $n \equiv 5 (mod 10)$ . Then $3 n \equiv 15 \equiv 5 (mod 10)$ and $n^{2} \equiv 25 \equiv 5 (mod 10)$ . ✓

b) $m = 35$ : $35 \equiv 5 (mod 10)$ , but $35 \neq = 5$ , $35 = 3 n$ has no integer solution, and $35$ is not a perfect square. So no rule produces 35, and $35 \in / S$ . (Elements of $S$ : $5, 15, 25, 45, 75, \dots$ )

5.3 #31 Extra Recursive sets of pairs

Give a recursive definition of each of these sets of ordered pairs of positive integers. Use structural induction to prove that the recursive definition you found is correct. (Hint: plot the points and look for patterns.)

a) $S = {(a, b) ∣ a, b \in Z^{+}, a + b is even}$
b) $S = {(a, b) ∣ a, b \in Z^{+}, a or b is odd}$
c) $S = {(a, b) ∣ a, b \in Z^{+}, a + b is odd and 3 ∣ b}$

Show solution

Each proof has two halves: (1) structural induction shows everything generated is in the set; (2) induction on $a + b$ shows everything in the set gets generated.

a) Basis: $(1, 1) \in S$ . Recursive: if $(a, b) \in S$ then $(a + 2, b)$ , $(a, b + 2)$ , $(a + 1, b + 1) \in S$ .

$(1, 1)$ has even sum, and each rule adds 2 to the sum, so parity is preserved.
Conversely, let $a + b$ be even. If $a + b = 2$ , then $(a, b) = (1, 1)$ . Otherwise $a + b \geq 4$ : if $a \geq 3$ use $(a - 2, b)$ ; if $b \geq 3$ use $(a, b - 2)$ ; otherwise $a = b = 2$ , use $(1, 1)$ . The smaller pair is in $S$ by the inductive hypothesis, and one rule produces $(a, b)$ .

b) Basis: $(1, 1), (1, 2), (2, 1) \in S$ . Recursive: if $(a, b) \in S$ then $(a + 2, b) \in S$ and $(a, b + 2) \in S$ .

The basis pairs each have an odd coordinate, and adding 2 doesn't change parity.
Conversely, if $(a, b)$ has an odd coordinate and isn't a basis pair, then $a \geq 3$ or $b \geq 3$ . Subtract 2 from that coordinate. The result still has an odd coordinate and positive entries, so it's in $S$ by induction on $a + b$ .

c) Basis: $(1, 6), (2, 3) \in S$ . Recursive: if $(a, b) \in S$ then $(a + 2, b) \in S$ and $(a, b + 6) \in S$ .

The basis pairs satisfy "odd sum, $3 ∣ b$ ." Adding 2 to $a$ keeps the sum's parity. Adding 6 to $b$ keeps both the parity and divisibility by 3.
Conversely, suppose $(a, b)$ qualifies. Since $3 ∣ b$ and $a + b$ is odd: if $a \geq 3$ , then $(a - 2, b)$ qualifies. If $a \in {1, 2}$ and $b \geq 9$ , then $(a, b - 6)$ qualifies. The remaining cases are exactly $(1, 6)$ and $(2, 3)$ . Induct on $a + b$ .

5.3 #33 Extra Well-formed formulae

Define well-formed formulae of sets, variables representing sets, and operators from ${, \cup, \cap, -}$ .

Show solution

Basis step: if $X$ is a set or a variable representing a set, then $X$ is a well-formed formula.
Recursive step: if $X$ and $Y$ are well-formed formulae, then so are $X$ , $(X \cup Y)$ , $(X \cap Y)$ , and $(X - Y)$ .

5.3 #34 Core Strings + structural induction

a) Give a recursive definition of the function $ones (s)$ , which counts the number of ones in a bit string $s$ .
b) Use structural induction to prove that $ones (s t) = ones (s) + ones (t)$ .

Show solution

a) (Same as $g$ from class, Problem 6.)

Basis: $ones (λ) = 0$ .
Recursive: for $w$ a bit string and $b \in {0, 1}$ , $ones (w b) = ones (w) + b$ .

b) Fix $s$ ; use structural induction on $t$ . Let $P (t)$ : $ones (s t) = ones (s) + ones (t)$ .

Basis ( $t = λ$ ): $ones (s λ) = ones (s) = ones (s) + 0 = ones (s) + ones (λ)$ . ✓

Recursive step. Assume $P (t)$ . For $b \in {0, 1}$ :
$ones (s (t b)) = ones ((s t) b) = ones (s t) + b = ones (s) + ones (t) + b = ones (s) + ones (t b) definition IH definition .$
So $P (t b)$ holds. ∎

5.3 #35 Extra Strings + structural induction

a) Give a recursive definition of the function $m (s)$ , which equals the smallest digit in a nonempty string of decimal digits.
b) Use structural induction to prove that $m (s t) = min (m (s), m (t))$ .

Show solution

Let $D = {0, 1, \dots, 9}$ .

a) The string must be nonempty, so the basis is a single digit.

Basis: if $x \in D$ , then $m (x) = x$ .
Recursive: if $t$ is a nonempty string of digits and $x \in D$ , then $m (t x) = min (m (t), x)$ .

b) Fix nonempty $s$ ; induct on nonempty $t$ .

Basis ( $t = x$ , a single digit): $m (s x) = min (m (s), x) = min (m (s), m (x))$ . ✓

Recursive step: assume $m (s w) = min (m (s), m (w))$ for a nonempty $w$ , and let $t = w x$ . Then
$m (s t) = m ((s w) x) = min (m (s w), x) = min (min (m (s), m (w)), x) = min (m (s), min (m (w), x)) = min (m (s), m (w x)) = min (m (s), m (t)) .$ ∎

5.3 #36 Core Strings

Find the reversal of the following bit strings.

a) 0101 b) 1 1011 c) 1000 1001 0111

Show solution

Answer

a) 1010 b) 1 1011 (a palindrome) c) 1110 1001 0001

Write the characters in reverse order (ignore the spaces; they're just grouping).

a) $0101 \to 1010$

b) $11011 \to 11011$ . It's a palindrome.

c) $100010010111 \to 111010010001$ , i.e. 1110 1001 0001.

5.3 #37 Core Strings

Give a recursive definition of the reversal of a string. (Hint: first define the reversal of the empty string. Then write a string $w$ of length $n + 1$ as $x y$ , where $x$ has length $n$ , and express the reversal of $w$ in terms of $x^{R}$ and $y$ .)

Show solution

Answer

$λ^{R} = λ$ ; $(x y)^{R} = y x^{R}$ for $x \in Σ^{*}$ , $y \in Σ$ .

Basis: $λ^{R} = λ$ .
Recursive step: if $x \in Σ^{*}$ and $y \in Σ$ (one symbol), then $(x y)^{R} = y x^{R}$ .

The last symbol moves to the front, followed by the reversal of the rest. Check: $(01 \cdot 1)^{R} = 1 \cdot (01)^{R} = 1 \cdot 1 \cdot (0)^{R} = 110$ . ✓

5.3 #38 Challenge Strings + structural induction

Use structural induction to prove that $(w_{1} w_{2})^{R} = w_{2}^{R} w_{1}^{R}$ .

Show solution

Fix $w_{1}$ and use structural induction on $w_{2}$ . Let $P (w_{2})$ : $(w_{1} w_{2})^{R} = w_{2}^{R} w_{1}^{R}$ .

Basis ( $w_{2} = λ$ ): $(w_{1} λ)^{R} = w_{1}^{R} = λ w_{1}^{R} = λ^{R} w_{1}^{R}$ . ✓

Recursive step. Assume $P (w_{2})$ and let $x \in Σ$ . Using the definition $(ux)^{R} = x u^{R}$ :
$(w_{1} (w_{2} x))^{R} = ((w_{1} w_{2}) x)^{R} = x (w_{1} w_{2})^{R} = x (w_{2}^{R} w_{1}^{R}) = (x w_{2}^{R}) w_{1}^{R} = (w_{2} x)^{R} w_{1}^{R} associativity definition of reversal IH associativity definition of reversal .$
So $P (w_{2} x)$ holds. ∎

5.3 #39 Core Strings

Give a recursive definition of $w^{i}$ , where $w$ is a string and $i$ is a nonnegative integer. (Here $w^{i}$ represents the concatenation of $i$ copies of $w$ .)

Show solution

Answer

$w^{0} = λ$ ; $w^{i + 1} = w w^{i}$ .

Basis: $w^{0} = λ$ (zero copies is the empty string).
Recursive step: $w^{i + 1} = w w^{i}$ for $i \geq 0$ .

Example: $(01)^{3} = 01 \cdot (01)^{2} = 01 \cdot 01 \cdot 01 \cdot λ = 010101$ .

5.3 #40 Challenge Strings

Give a recursive definition of the set of bit strings that are palindromes.

Show solution

Basis: $λ \in P$ , $0 \in P$ , $1 \in P$ .
Recursive step: if $w \in P$ , then $0 w 0 \in P$ and $1 w 1 \in P$ .

Why it's right: everything generated reads the same backward (wrapping a palindrome in matching ends keeps it a palindrome). Conversely, a palindrome of length $\geq 2$ has equal first and last symbols and a palindrome in the middle. Peel off the ends until you reach length 0 or 1, i.e. $λ$ , $0$ , or $1$ . You need both even- and odd-length bases.

5.3 #41 Core Strings

When does a string belong to the set $A$ of bit strings defined recursively by $λ \in A$ , and $0 x 1 \in A$ if $x \in A$ ?

Show solution

Answer

Exactly when it is $0^{n} 1^{n}$ ( $n$ zeros followed by $n$ ones) for some $n \geq 0$ .

Generate: $λ$ , then $01$ , then $0011$ , then $000111$ , … Each step wraps one more 0 on the left and one more 1 on the right. So $A = {0^{n} 1^{n} ∣ n \geq 0}$ : some number of 0s followed by the same number of 1s.

5.3 #42 Challenge Strings

Recursively define the set of bit strings that have more zeros than ones.

Show solution

Let $S$ be the set of bit strings with more 0s than 1s. One correct definition:

Basis: $0 \in S$ .
Recursive step: if $x, y \in S$ , then $x y \in S$ , and every string formed by inserting a single $1$ anywhere into $x y$ (front, back, or between any two symbols) is in $S$ .

Everything generated is in $S$ : if $x$ and $y$ each have at least one more 0 than 1s, then $x y$ has at least two more, and inserting one 1 leaves at least one more.

Everything in $S$ is generated (strong induction on length): all-zero strings come from concatenating 0s. If $w \in S$ has a 1, delete one 1 to get $u$ with $(#0 - #1) \geq 2$ . Scan $u$ left to right, tracking $#0 - #1$ . It starts at 0, ends $\geq 2$ , and moves by $\pm 1$ , so it hits exactly 1 at some point. Split $u = x y$ there: $x$ has difference 1 and $y$ has difference $\geq 1$ . Both are shorter strings in $S$ , so $w$ = $x y$ with a 1 inserted.

5.3 #43 Core Induction on strings

Use Exercise 39 ( $w^{0} = λ$ , $w^{i + 1} = w w^{i}$ ) and mathematical induction to show that $l (w^{i}) = i \cdot l (w)$ , where $w$ is a string and $i$ is a nonnegative integer.

Show solution

Let $P (i)$ : $l (w^{i}) = i \cdot l (w)$ .

Basis ( $i = 0$ ): $l (w^{0}) = l (λ) = 0 = 0 \cdot l (w)$ . ✓

Inductive step. Assume $l (w^{i}) = i \cdot l (w)$ . Then
$l (w^{i + 1}) = l (w w^{i}) = l (w) + l (w^{i}) = l (w) + i \cdot l (w) = (i + 1) l (w),$
using $l (x y) = l (x) + l (y)$ (textbook Example 12) and the IH. ∎

5.3 #44 Challenge Induction on strings

Show that $(w^{R})^{i} = (w^{i})^{R}$ whenever $w$ is a string and $i$ is a nonnegative integer.

Show solution

Induction on $i$ .

Basis ( $i = 0$ ): $(w^{R})^{0} = λ = λ^{R} = (w^{0})^{R}$ . ✓

Inductive step. Assume $(w^{R})^{i} = (w^{i})^{R}$ . Then
$(w^{R})^{i + 1} = w^{R} (w^{R})^{i} = w^{R} (w^{i})^{R} = (w^{i} w)^{R} = (w^{i + 1})^{R} definition of powers IH Exercise 38: (uv)^{R} = v^{R} u^{R} w^{i} w = w w^{i} = w^{i + 1} (both are i + 1 copies of w) .$ ∎

5.3 #45 Core Full binary trees

Use structural induction to show that $n (T) \geq 2 h (T) + 1$ , where $T$ is a full binary tree, $n (T)$ equals the number of vertices of $T$ , and $h (T)$ is the height of $T$ .

Show solution

Recall: single root has $n = 1$ , $h = 0$ ; and for $T = T_{1} \cdot T_{2}$ , $n (T) = 1 + n (T_{1}) + n (T_{2})$ and $h (T) = 1 + max (h (T_{1}), h (T_{2}))$ .

Basis (single vertex): $n (T) = 1 \geq 2 (0) + 1 = 1$ . ✓

Recursive step. Assume $n (T_{1}) \geq 2 h (T_{1}) + 1$ and $n (T_{2}) \geq 2 h (T_{2}) + 1$ (IH). For $T = T_{1} \cdot T_{2}$ :
$n (T) = 1 + n (T_{1}) + n (T_{2}) \geq 1 + (2 h (T_{1}) + 1) + (2 h (T_{2}) + 1) \geq 1 + 2 max (h (T_{1}), h (T_{2})) + 2 = 1 + 2 (1 + max (h (T_{1}), h (T_{2}))) = 2 h (T) + 1. IH since h (T_{1}) + h (T_{2}) \geq max (h (T_{1}), h (T_{2}))$ ∎

5.3 #46 Core Full binary trees

Use structural induction to show that $l (T)$ , the number of leaves of a full binary tree $T$ , is 1 more than $i (T)$ , the number of internal vertices of $T$ .

Show solution

Definitions: for a single root, $l (T) = 1$ and $i (T) = 0$ . For $T = T_{1} \cdot T_{2}$ : the leaves of $T$ are the leaves of $T_{1}$ and $T_{2}$ , so $l (T) = l (T_{1}) + l (T_{2})$ . The internal vertices are the new root plus those of $T_{1}$ and $T_{2}$ , so $i (T) = 1 + i (T_{1}) + i (T_{2})$ .

Basis: $l (T) = 1 = 0 + 1 = i (T) + 1$ . ✓

Recursive step. Assume $l (T_{1}) = i (T_{1}) + 1$ and $l (T_{2}) = i (T_{2}) + 1$ . Then
$l (T) = l (T_{1}) + l (T_{2}) = (i (T_{1}) + 1) + (i (T_{2}) + 1) = (1 + i (T_{1}) + i (T_{2})) + 1 = i (T) + 1.$ ∎

5.3 #50 Core Ackermann

Find these values of Ackermann's function: a) $A (1, 0)$ b) $A (0, 1)$ c) $A (1, 1)$ d) $A (2, 2)$

A (m, n) = ⎩ ⎨ ⎧ 2 n 02 A (m - 1, A (m, n - 1)) m = 0 m \geq 1, n = 0 m \geq 1, n = 1 m \geq 1, n \geq 2

Show solution

Answer

a) 0 b) 2 c) 2 d) 4

a) $m = 1 \geq 1$ , $n = 0$ : $A (1, 0) = 0$ .

b) $m = 0$ : $A (0, 1) = 2 \cdot 1 = 2$ .

c) $m \geq 1$ , $n = 1$ : $A (1, 1) = 2$ .

d) $A (2, 2) = A (1, A (2, 1)) = A (1, 2) = A (0, A (1, 1)) = A (0, 2) = 4$ .

5.3 #51 Core Ackermann

Show that $A (m, 2) = 4$ whenever $m \geq 1$ .

Show solution

Induction on $m$ . Let $P (m)$ : $A (m, 2) = 4$ .

Basis ( $m = 1$ ): $A (1, 2) = A (0, A (1, 1)) = A (0, 2) = 4$ . ✓

Inductive step. Assume $A (m, 2) = 4$ for some $m \geq 1$ . Then
$A (m + 1, 2) = A (m, A (m + 1, 1)) = A (m, 2) = 4,$
using $A (m + 1, 1) = 2$ (since $m + 1 \geq 1$ ) and then the IH. ∎

5.3 #52 Core Ackermann

Show that $A (1, n) = 2^{n}$ whenever $n \geq 1$ .

Show solution

Induction on $n$ .

Basis ( $n = 1$ ): $A (1, 1) = 2 = 2^{1}$ . ✓

Inductive step. Assume $A (1, n) = 2^{n}$ for some $n \geq 1$ . Since $n + 1 \geq 2$ ,
$A (1, n + 1) = A (0, A (1, n)) = 2 \cdot A (1, n) = 2 \cdot 2^{n} = 2^{n + 1} .$ ∎

5.3 #53 Core Ackermann

Find these values of Ackermann's function: a) $A (2, 3)$ b) $A (3, 3)$

Show solution

Answer

a) 16 b) 65,536

Use $A (1, n) = 2^{n}$ (#52) and $A (m, 2) = 4$ (#51).

a) $A (2, 3) = A (1, A (2, 2)) = A (1, 4) = 2^{4} = 16$ .

b) $A (3, 3) = A (2, A (3, 2)) = A (2, 4)$ , since $A (3, 2) = 4$ . Then
$A (2, 4) = A (1, A (2, 3)) = A (1, 16) = 2^{16} = 65, 536.$

5.3 #54 Challenge Ackermann

Find $A (3, 4)$ .

Show solution

Answer

$A (2, 65536)$ , a tower of 65,536 twos: $2^{2^{\cdot^{\cdot^{2}}}}$ .

$A (3, 4) = A (2, A (3, 3)) = A (2, 65536)$ by #53.

Now for $n \geq 2$ : $A (2, n) = A (1, A (2, n - 1)) = 2^{A (2, n - 1)}$ , with $A (2, 1) = 2$ . So $A (2, n)$ is a tower of $n$ twos ( $A (2, 2) = 2^{2}$ , $A (2, 3) = 2^{2^{2}}$ , …).

Therefore $A (3, 4)$ is a tower of exponents made of 65,536 twos, far too large to write out.

5.3 #55 Challenge Ackermann

Prove that $A (m, n + 1) > A (m, n)$ whenever $m$ and $n$ are nonnegative integers.

Show solution

Induction on $m$ , with an inner induction on $n$ .

Basis ( $m = 0$ ): $A (0, n + 1) = 2 n + 2 > 2 n = A (0, n)$ . ✓

Inductive step. Assume $A (m, \cdot)$ is strictly increasing: $A (m, x + 1) > A (m, x)$ for all $x \geq 0$ . Show the same for $A (m + 1, \cdot)$ , by induction on $n$ :

$n = 0$ : $A (m + 1, 1) = 2 > 0 = A (m + 1, 0)$ .
$n = 1$ : $A (m + 1, 2) = 4 > 2 = A (m + 1, 1)$ , using #51.
$n \geq 2$ : assume $A (m + 1, n) > A (m + 1, n - 1)$ . Then since $A (m, \cdot)$ is increasing,
$A (m + 1, n + 1) = A (m, A (m + 1, n)) > A (m, A (m + 1, n - 1)) = A (m + 1, n) .$

So $A (m + 1, \cdot)$ is strictly increasing, completing the induction. ∎

5.3 #56 Challenge Ackermann

Prove that $A (m + 1, n) \geq A (m, n)$ whenever $m$ and $n$ are nonnegative integers.

Show solution

We use #55 ( $A (m, \cdot)$ is increasing) and the lemma proved in #57: $A (i, j) \geq j + 1$ whenever $j \geq 1$ .

$n = 0$ : $A (m + 1, 0) = 0$ , and $A (m, 0) = 0$ (both when $m = 0$ and $m \geq 1$ ). Equal. ✓
$n = 1$ : $A (m + 1, 1) = 2$ , and $A (m, 1) = 2$ (whether $m = 0$ or $m \geq 1$ ). Equal. ✓
$n \geq 2$ : $A (m + 1, n) = A (m, A (m + 1, n - 1))$ . By the lemma, $A (m + 1, n - 1) \geq (n - 1) + 1 = n$ . Since $A (m, \cdot)$ is increasing,
$A (m + 1, n) = A (m, A (m + 1, n - 1)) \geq A (m, n) .$ ∎

5.3 #57 Extra Ackermann

Prove that $A (i, j) \geq j$ whenever $i$ and $j$ are nonnegative integers.

Show solution

Prove the stronger lemma: $A (i, j) \geq j + 1$ for all $i \geq 0$ , $j \geq 1$ . (Combined with $A (i, 0) = 0 \geq 0$ , this gives $A (i, j) \geq j$ for all $j$ .)

Induction on $i$ .

Basis ( $i = 0$ ): $A (0, j) = 2 j \geq j + 1$ for $j \geq 1$ . ✓

Inductive step. Assume $A (i, x) \geq x + 1$ for all $x \geq 1$ . Show $A (i + 1, j) \geq j + 1$ for $j \geq 1$ by induction on $j$ :

$j = 1$ : $A (i + 1, 1) = 2 \geq 2$ . ✓
$j \geq 2$ : assume $A (i + 1, j - 1) \geq j$ . Then $A (i + 1, j - 1) \geq 1$ , so the outer IH applies to it:
$A (i + 1, j) = A (i, A (i + 1, j - 1)) \geq A (i + 1, j - 1) + 1 \geq j + 1.$

Hence $A (i, j) \geq j$ always. ∎ (The book gets this from #56 as $A (i, j) \geq A (i - 1, j) \geq \dots \geq A (0, j) = 2 j \geq j$ .)

Custom (from lecture) Core Strings Not from HW

Define $h : {0, 1}^{*} \to N$ recursively so that $h (w)$ counts the number of 0s in the bit string $w$ . Then compute $h (10100)$ step by step from your definition.

Show solution

Answer

$h (λ) = 0$ ; $h (w b) = h (w) + (1 - b)$ . $h (10100) = 3$ .

Basis: $h (λ) = 0$ .
Recursive step: for $w \in {0, 1}^{*}$ and $b \in {0, 1}$ : $h (w b) = h (w) + (1 - b)$ . A trailing 0 adds 1; a trailing 1 adds 0.

$h (10100) = h (1010) + 1 = h (101) + 2 = h (10) + 2 = h (1) + 3 = h (λ) + 3 = 3$ .

Custom Core Structural induction Not from HW

Let $S$ be the set of ordered pairs of integers defined by: Basis: $(0, 0) \in S$ . Recursive step: if $(a, b) \in S$ , then $(a + 2, b + 3) \in S$ and $(a + 3, b + 2) \in S$ .

a) List the elements produced by the first two applications of the recursive step.
b) Use structural induction to show $5 ∣ (a + b)$ whenever $(a, b) \in S$ .

Show solution

a) First application: $(2, 3)$ , $(3, 2)$ . Second: from $(2, 3)$ : $(4, 6)$ , $(5, 5)$ ; from $(3, 2)$ : $(5, 5)$ , $(6, 4)$ . New elements: $(4, 6), (5, 5), (6, 4)$ .

Basis: $0 + 0 = 0$ , and $5 ∣ 0$ . ✓
Recursive step. Assume $(a, b) \in S$ with $5 ∣ a + b$ . Then
- $(a + 2) + (b + 3) = (a + b) + 5$ , divisible by 5. ✓
- $(a + 3) + (b + 2) = (a + b) + 5$ , divisible by 5. ✓

So $5 ∣ a + b$ for every $(a, b) \in S$ . ∎

Next: 6.1 The Basics of Counting