In this lab, we’ll work on authoring proofs. Try to be as rigorous, yet concise in your proofs as possible. If you have any questions about levels of formality or formatting, please don’t hesitate to ask!

## Problem 1: Formal Proof

Formally prove the following claims over strings.

**Claim 1**: Call an element \(u\) of a set \(S\) and an associated binary operation over that set \((+) : S → S\) a *unit* if \(\forall x \in S \ldotp x + u = u + x = x\). We claim that \(ϵ\) is a unit for strings and concatenation over strings.

**Claim 2**: Let \(x\) and \(y\) be strings. If \(x\) is a prefix of \(y\) and \(y\) is a prefix of \(x\) then \(x = y\).

(*Hint*: make this an algebraic argument based on the definition of prefix from the book!)

## Problem 2: Induction Revisited

Consider the following definitions regarding binary trees.

**Definition (Binary Tree)**: a binary tree is either:

- A
*leaf*or - A
*node*with two sub-trees, its*children*.

We define the *root* of a binary tree to be a node that is not the child of any other node in the tree.

**Definition (Level and Height)**: the *level* of a node in a binary tree is the length of the path from the root to that node. The *height* of a binary tree is the maximal level of any node in the tree. We also use “level” to denote the *set of all nodes* that share the same level in the tree.

**Definition (Complete and Perfect Trees)**: a tree is *complete* if each of its levels contain its maximal number of possible nodes. A tree is *perfect* if each node of the tree contains zero or two children.

Now prove the following claim by structural induction.

Let \(h\) be the height of a complete, perfect binary tree. If \(n \leq h\), then there are \(2^n\) nodes at level \(n\) of this tree.

## Problem 3: Constructive Proof (Optional)

Chess is played on a \(n \times n\) board (usually \(n = 8\)). Consider the *rook* piece, which can move in any number of squares in a cardinal (non-diagonal) direction. A *rook’s tour* is a sequence of moves for a single rook that causes the piece to visit *every* square of the board *exactly once*. When considering a tour, we are free to place our piece on the board at any position initially. Also, we only consider a square visited if the piece *ends its movement* on that square.

Prove via induction that there exists a rook’s tour for any chessboard of size \(n ≥ 1\).

(*Hint 1*: note that proving the existence of a rook’s tour means constructing a rook’s tour for an arbitrary board, *i.e.*, designing an algorithm that generates the tour!)

(*Hint 2:* pay attention to the details! This is not as straightforward of a proof as you might think!)