# Induction on strings (words)

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?

• I have updated the post. No information about v is given anywhere. – user1221 Jan 20 at 19:34
• @apass: it's a simple recursive definition of sum: $sum(a_1...a_n) = sum(a_1...a_{n-1}) + a_n$. – rici Jan 20 at 19:55
• @user1221 as a first step, can you given a recursive definition of $w\to |w|$ in the same fashion of the definition for $quer$? – Apass.Jack Jan 20 at 21:47

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$$