🍈 Zettelkasten

❯

❯

Structural Induction String Example

Structural Induction String Example

Nov 11, 20251 min read

programming
math

Example 2

Given a string $e \in Σ^{*}$ For example, $e = x yz + x y + x () \div$ we define:

$v r (e)$ be the number of occurrences of variables in $e$
- For example, $v r (x yz + x y + x () \div) = 6$
$o p (e)$ be the number of occurrences operators in $e$
- For example, $o p (x yz + x y + x () \div) = 3$ We define $P (e) : v r (e) = o p (e) + 1$ Prove that $\forall e \in E, P (e)$

Base Case

Consider 3 cases:

$e = x$
$e = y$
$e = z$ Then, notice that for all cases $v r (e) = 1 = 0 + 1 = o p (e) + 1$

Induction Step

Let $e_{1}, e_{2} \in E$ Suppose $P (e_{1}), P (e_{2})$ Induction Hypothesis Then, given four cases:

$e_{1} + e_{2}$
- Note that $v r (e_{1} + e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} + e_{2}) + 1$
$e_{1} - e_{2}$
- Note that $v r (e_{1} - e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} - e_{2}) + 1$
$e_{1} \times e_{2}$
- Note that $v r (e_{1} \times e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} \times e_{2}) + 1$
$e_{1} \div e_{2}$
- Note that $v r (e_{1} \div e_{2}) = v r (e_{1}) + v r (e_{2}) + 1 = o p (e_{1}) + o p (e_{2}) + 2 ⟹ v r (e_{1} + e_{2}) = o p (e_{1} \div e_{2}) + 1$ Thus, we get $\forall e \in E, P (e)$

Graph View

Backlinks

Proof by Structural Induction

Created with Quartz v4.4.0 © 2025

GitHub
Discord Community