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:

  1. for $x=\epsilon$ we have $|x|=0$
  2. 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.

  • 2
    $\begingroup$ Induction over $|x|$ seems indicated. $\endgroup$
    – Did
    Feb 20, 2011 at 18:19
  • $\begingroup$ Induction should work. For instance, use induction on $|y|$. $\endgroup$
    – Myself
    Feb 20, 2011 at 18:20
  • $\begingroup$ Thanks guys, I think I did it. I will now post an answer on this. $\endgroup$ Feb 20, 2011 at 18:44
  • $\begingroup$ If this is a homework assignment, please say so. Could this be solved by observing that string concatenation is a monoid with $\epsilon$ as the identity and $|\cdot|$ mapping to integers with $+$ as operation and $0$ as identity? $\endgroup$ Feb 20, 2011 at 18:44
  • $\begingroup$ Well, I am studying this in my spare time and found some exercises on this on the net. So I guess yes, they are homework. And no, I do not gain anything by having someone do it for me. I know nothing about monoids. $\endgroup$ Feb 20, 2011 at 19:04

3 Answers 3


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.

For all $n$, if $y\in \Sigma^*$ and $x\in\Sigma^n$, then $|xy|=|x|+|y|$.

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

For all $x,y\in \Sigma^*$, $|xy|= |x|+|y|$

as claimed. QED

  • $\begingroup$ @Arturo If I understand your post correctly, the first two thirds are off topic. Simply put, there is no problem at all with the definitions of $\Sigma^*$ and of $|x|$ for $x$ in $\Sigma^*$. This is basic stuff of the field, see en.wikipedia.org/wiki/String_%28computer_science%29 for example (so I would not blame the OP for such an omission). In fact, one can forget all this top-down and bottom-up stuff (and I am not sure you really meant to write bottoms-up here...) and your recursive definition of $\Sigma^*$. .../... $\endgroup$
    – Did
    Mar 26, 2011 at 23:57
  • $\begingroup$ .../... Instead, why not use the classical Cartesian products $\Sigma^n$ for every positive integer $n$ (and not your sets $\Sigma_n$), as everybody else does? This would simplify the only relevant part of your post (the last third, where you perform the proof by induction that I hinted at one month ago, following exactly the way I explained then), where your $\Sigma_n$ sets only complicate things. $\endgroup$
    – Did
    Mar 26, 2011 at 23:57
  • $\begingroup$ @Didier: I don't know what definition of $\Sigma^*$ the OP has, or what properties he knows. If the definition is via the bottoms up approach and this is standard and assumed,, then yes, you can drop the entire first part and jump until the last part. The $\Sigma_n$ I defined are simply equal to $\cup_{i=1}^n\Sigma^n$ as per the definition in the Wikipedia page, though, so I don't see how they "complicate things"... $\endgroup$ Mar 27, 2011 at 0:14
  • $\begingroup$ @Arturo The so called Kleene closure $\Sigma^*$ of $\Sigma$ is by definition the union of the $\Sigma^n$, each Cartesian product $\Sigma^n$ is by definition the set of functions from $\{1,2,...,n\}$ to $\Sigma$. You still need to know how to compose a function from $\{1,2,...,n\}$ to $\Sigma$ with a function from $\{1,2,...,k\}$ to $\Sigma$, to produce a function from $\{1,2,...,n+k\}$ to $\Sigma$ (a not too difficult task), et voilà! No recursion. No bottom-up approach. Sorry to insist, but this is really basic stuff and yes, everybody defines $\Sigma^*$ in this way. $\endgroup$
    – Did
    Mar 27, 2011 at 0:33
  • $\begingroup$ @Didier: Yes, I know this is basic and easy. I could do it in my sleep and with one hand tied behind my back. And behind everything you say, there is an application of the recursion theorem which perhaps you aren't seeing. And yet, it's there. $\endgroup$ Mar 27, 2011 at 1:26

I have upvoted Arturo Magidin's answer. But aren't we shooting with cannons on sparrows here? A fundamental principle of counting is that it is additive on disjoint sets. Now count the number of cells that are occupied by your strings.


So, I will only cover here how to solve this for the inductive step, as the other is rather easy (not that the inductive step one isn't!).

Considering a string $x'=\lambda x$ we have

$$\begin{align} |x'y| &= |x'|+|y| \\ |\lambda xy| &= |\lambda x| + |y| \\ |\lambda z| &= 1 + |x| + |y| \\ 1 + |z| &= 1 + |x| + |y| \\ 1+|xy| &= 1 + |xy| \end{align}$$

  • 3
    $\begingroup$ Sorry to be blunt but this is not a proof. Not nearly. A proof by induction begins with stating precisely an induction hypothesis $H_n$. Then one proves that $H_1$ holds (for instance). Then one proves that, for every $n\ge1$, if $H_n$ holds, then $H_{n+1}$ holds. If you do all this, you won in the sense that you proved that $H_n$ holds for every $n\ge1$. $\endgroup$
    – Did
    Feb 20, 2011 at 19:50
  • 1
    $\begingroup$ as stated above, this is the inductive step (Hn+1). $\endgroup$ Feb 20, 2011 at 21:31
  • $\begingroup$ The inductive step is not to prove that $H_n$ holds nor to prove that $H_{n+1}$ holds. The inductive step is to prove that if $H_n$ holds then $H_{n+1}$ holds. For example, consider for $H_n$ the assertion that the sum of the powers of $2$ from $2^0=1$ to $2^n$ is $2^{n+1}+7$. Then, for every nonegative $n$, $H_n$ does imply $H_{n+1}$ even though every $H_n$ is false. $\endgroup$
    – Did
    Feb 20, 2011 at 22:24
  • 1
    $\begingroup$ If you want, you can show us noobs how to do it right as a separate answer (and have the 15 points, as although several people helped me understand the problem, they only did it as comments!). $\endgroup$ Feb 22, 2011 at 22:39
  • 4
    $\begingroup$ OK (but next time you could spare us this us noobs thing). As I said, A proof by induction begins with stating precisely an induction hypothesis $H_n$, so what is your $H_n$? Hint: the answer is in my first comment to your post. $\endgroup$
    – Did
    Feb 23, 2011 at 9:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .