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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I have updated the post. No information about v is given anywhere. $\endgroup$
    – Monika
    Jan 20, 2019 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, 2019 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$
    – John L.
    Jan 20, 2019 at 21:47

1 Answer 1

Reset to default
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 $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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