Induction on strings (words)

Question

Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word.

$quer : \Sigma^*\to \Bbb N$ with:

$$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\ quer(v)+x, &\text{when } w=vx, x\in\Sigma \end{cases}$$

Where $\epsilon$ is the empty string.

Prove by Induction on words that $\forall w\in\Sigma^*$, $quer(w)\le 2*|w|$.

I can prove that the statement holds for $\epsilon$.

Base case: $quer(\epsilon) = 0 \le 2 * |\epsilon| = 0 $

How can I show that the statement holds in the inductive step?

Answer 1

I suppose you are already familiar with the idea behind mathematical induction, but just to recap the general idea, the goal is to use the inductive hypothesis to help us get the desired statement. It is helpful to construct the words in a way that will simplify how you can relate back to the original word.

Suppose it works for all words $v \in \Sigma^*$ such as $\lvert v \rvert = n$ (we can do this because you proved the base case for words of length 0). Now, take $w = vx$ for any $x \in \Sigma$. Note that the length of $w$ is $\lvert v \rvert + 1$ by construction ($\lvert w \rvert = n + 1$).

$$ quer(w) = quer(vx) = quer(v) + x \leq quer(v) + 2 \\ \leq 2\cdot \lvert v \rvert + 2\\ = 2 \cdot (\lvert w \lvert -1) + 2\\ = 2\lvert w \rvert - 2 + 2 \\ = 2 \lvert w \rvert $$