Ok so i don't know how to prove the following:

Let S be a string and |S| its length.

Let [i..j] be an interval such that 0 < i <= |S| and 0 < j <= |S|. You can also refer to [i..j] as a substring of S.

Let [i..j] be a maximum repeat such that [i..j] is repeated and [i..j+1] and [i-1..j] are not.

Let A be an alphabet and every character in S is an element of A and every character in S is repeated at leas twice.

Let p be a non-negative integer.

Prove that the length of p number of overlapping maximum repeats in S is smaller then p number of concatenated maximum repeats .

so ma max repeat is

Code:

|------------------------|

Prove that

Code:

|-------------------|
|---------------------|
|<---------------------------->|

is shorter than

Code:

|-----------------||---------------------|
|<-------------------------------------->|

Now this is the case for p = 2 but p in what i want to prove is arbitrary.

How would you do this? would you just show that for non-overlapping intervals $\displaystyle \cap_{i=1}^{p} \mbox{Interval} = 0$ and therefore non-overlaps are longer then overlaps or would you first show that for p=2 overlapped intervals are smaller then two concatenated ones and then by induction on p proved that this holds for all p.

What confuses me if i choose to prove by induction on p how would i do it? how would i start, what would be my induction hypothesis and what would my cases be ?? This second question is much more important if someone could help me with it, because i have different examples that i would like to do but there are not much examples on how to apply induction in cases as the one described above.

Thank you

baxy

PS

i know that this is probably trivial but pleas help because this will clear many other confusions and i will be able to make my questions more precise and clear.