1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I left parts of the proof there just for understanding where the problem comes from. $\endgroup$ – Greg P. Feb 10 '14 at 9:33
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's clear to me that you use p(1) up to p(n) for induction. I'm just concerned with getting those l,m. So my question is: Why can you split up arbitrary bracket terms? $\endgroup$ – Greg P. Feb 8 '14 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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