---
# System prepended metadata

title: 'Lab 2 - Formal Proof (Jax Seiler, Ally Rogers, Kevin Wang)'

---

# Lab 2 - Formal Proof (Jax Seiler, Ally Rogers, Kevin Wang)
Problem 1  
1. Let $S$ be the set of all strings. Let $x \in S$ be an arbitary string. Let $+$ be the string concatenation operation. The definition of the empty string is such that concatenating it with any other string does not change the target string, and thus $x + \epsilon = \epsilon + x = x$.  
2. Let $x$ and $y$ be strings such that $x$ is a prefix of $y$ and $y$ is a prefix of $x$. By the definition of prefix, there must exist strings $z_1$ and $z_2$ such that $x + z_1 = y$ and $y + z_2 = x$. By substitution, we get $y + z_2 + z_1 = y$. Because strings cannot cancel each other out, we know that $z_1 = z_2 = \epsilon$, and thus because $\epsilon$ is a unit, $x = y$.  

Problem 2  
1. This will be a proof by induction.  
* Base case ($n = 0$). The 0th level of the tree is the root, which has 1 node. $2^0 = 1$. $1 = 1$, and thus the base case is proven.  
* Inductive step: Case $n = k + 1$. Assume inductive hypothesis holds for $k$, which states that there are $2^k$ nodes at level $k$. Because the tree is complete, every possible node in level $k$ is therefore filled. Thus, because the tree is perfect and complete, every node on level $k$ has two children. Thus, on level $n$, there are $2(2^k)$ nodes. $2(2^k) = 2^{(k+1)} = 2^n$, and thus the inductive step is proven.  