Splitting up bracket terms

349 Views Asked by At

I found a statement saying: Let $\circledast $ be an associative binary operation on a set $\mathbb{X}$. A bracket term of length n, consisting of n elements $a_1, ..., a_n$ and arbitrary brackets, e.g. $K_4 = a_1 \circledast (a_2 \circledast a_3) \circledast a_4$, can be written as $K_n= (...(a_1 \circledast a_2)\circledast a_3) \circledast ...) \circledast a_{n-1})\circledast a_n$.

In other words: You can leave out the brackets.

Induction hypothesis: $K_k = (...(a_1 \circledast a_2)\circledast a_3) \circledast ...) \circledast a_{k-1})\circledast a_k $ for every bracket term of length $k, 3\leq k\leq n$.

The proof is simple, but in the induction step it makes use of the assumption that there are always $l, m \in \mathbb{N} \backslash \{0\}$ so that $l+m=n+1$ and $K_{n+1} = K_l \circledast K_m$

To my mind, this means that you can always split up a bracket expression at a certain position l (from left) or m (from right). Is this just a trivial fact or can/must this be further explained?

Edit: I have no problems with understanding the proof for the actual statement, but what's the reason for being able to split up arbitrary bracket terms?

Thanks in advance.

1

There are 1 best solutions below

1
On

Yes. That is what is usually called "strong induction," prove $p(n + 1)$ using $p(1)$ up to $p(n)$ true as the induction step.

As an aside, I'd try to get another text (at least as a complement). This looks like written for maximal pedantry, not clarity of understanding.