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?
sum
: $sum(a_1...a_n) = sum(a_1...a_{n-1}) + a_n$. $\endgroup$