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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top