I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$:
$$ |xy| = |x| + |y| $$
with $x, y \in \Sigma^*$.
To prove this, I am expected to make use of the following two definitions:
- for $x=\epsilon$ we have $|x|=0$
- for $x=au$, being $u \in \Sigma^*$ and $a \in \Sigma$ we have $|x|=1+|u|$
Intuitively it is easy to understand what is being asked here. The idea is to prove that the length of the concatenation of any two strings is equal to the sum of their individual lenghts.
What I am failing to realise is how to tackle the problem. Should I make use of induction? Just algebraic manipulation?
Any pointers would be welcome.
Best Answer
See this answer and this one for general advice and discussion on induction. Your argument above is, alas, neither very clear nor correct.
So, we have that $|\epsilon|=0$, and that if $x=au$ with $a\in\Sigma$, $u\in\Sigma^*$, then $|x|=1+|u|$. We want to prove that for all $x,y\in\Sigma^*$, we have $|xy|=|x|+|y|$.
What you really need here is an explicit definition of $\Sigma^*$, because you need to be able to handle elements of $\Sigma^*$. I'm guessing, pending you posting the definition, that you have a certain "alphabet" $\Sigma$, and then define $\Sigma^*$ as the collection of all strings of letters from $\Sigma$ in some way.
Assuming the intended definition is the definition in this page, we can proceed as follows.
If we can prove this, it will follow that for all $x$ in $\cup\Sigma^n = \Sigma^*$, we have $|xy|=|x|+|y|$, which is what we want to prove.
We will prove the proposition above by induction on $n$.
Base. $n=0$. Let $x\in\Sigma^0$. Then $x=\epsilon$, so $xy = y$ and $|x|=0$ by definition of $|\epsilon|$. Therefore, $|xy|=|y|=0+|y| = |x|+|y|$, so the equality holds.
Inductive step. We want to prove that if it is true that for all $z\in \Sigma^k$, $|zy|=|z|+|y|$, then it is true that for all $x\in\Sigma^{k+1}$, we also have $|xy|=|x|+|y|$.
Induction hypothesis. If $z\in\Sigma^k$, then $|zy|=|z|+|y|$.
Let $x\in\Sigma^{k+1}$. We want to prove that $|xy|=|x|+|y|$.
Since $x\in\Sigma^{k+1}$, then $x=au$ with $a\in\Sigma$ and $u\in\Sigma^k$.
Then we have by the definition of $|\cdot|$ that $$|xy| = |(au)y| = |a(uy)| = 1 + |uy|.$$ And by the Induction Hypothesis, since $|u|\in\Sigma^k$, we get $$|xy| = 1+|uy| = 1+(|u|+|y|) = (1+|u|)+|y|.$$ But by the definition of $|\cdot|$ we have $|x| = |au| = 1+|u|$, so $$|xy| = (1+|u|)+|y| = |x|+|y|,$$ as desired.
Thus, if for every $z\in\Sigma^k$ we have $|zy|=|z|+|y|$, then for every $x\in\Sigma^{k+1}$ we have $|xy|=|x|+|y|$.
By induction, we conclude that for all $n$, if $x\in\Sigma^n$ then $|xy|=|x|+|y|$.
Therefore, we have that for all $x\in\mathop{\cup}\limits_{n=0}^{\infty}\Sigma^n$, $|xy| = |x|+|y|$.
Thus, for all $x\in \Sigma^*$, $|xy|=|x|+|y|$.
Since $y\in\Sigma^*$ is arbitrary, we conclude that
as claimed. QED