1
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.