Generalized Associative Law

[Mr Davis 97]

I am trying to prove the generalized associative law with induction, but am being tripped up by one aspect. I am reading a solution and it says for the induction step argue that any bracketing of the product $a_1 \cdot a_2 \cdot \cdots a_n$ must break into two subproducts $(a_1 \cdot \cdots \cdot a_k) \cdot (a_{k+1} \cdot \cdots \cdot a_n)$ where each subproduct is bracketed in some fashion. Why is this true? As a concrete example, what are the subproducts of $(a_1 \cdot (a_2 \cdot (a_3 \cdot a_4))) \cdot a_5$, where the first product as two elements and the second has three, for example?

 

[fresh_42]

I am trying to prove the generalized associative law with induction, but am being tripped up by one aspect. I am reading a solution and it says for the induction step argue that any bracketing of the product $a_1 \cdot a_2 \cdot \cdots a_n$ must break into two subproducts $(a_1 \cdot \cdots \cdot a_k) \cdot (a_{k+1} \cdot \cdots \cdot a_n)$ where each subproduct is bracketed in some fashion. Why is this true? As a concrete example, what are the subproducts of $(a_1 \cdot (a_2 \cdot (a_3 \cdot a_4))) \cdot a_5$, where the first product as two elements and the second has three, for example?

It would help to see all the steps. Otherwise we can only repeat the proof.
We start with $a_1(a_2a_3)=(a_1a_2)a_3$. Now how is the statement worded? $a_1\ldots a_n$ doesn't exist, yet.

 

[Mr Davis 97]

It would help to see all the steps. Otherwise we can only repeat the proof.
We start with $a_1(a_2a_3)=(a_1a_2)a_3$. Now how is the statement worded? $a_1\ldots a_n$ doesn't exist, yet.

It says after proving the trivial base cases, suppose that for any $k < n$ that any bracketing of the product of $k$ elements can be reduced without altering the value to an expression of the form $b_1 \cdot (b_2 \cdot (b_3 \cdot ( \cdots \cdot b_k)) \dots)$. Given this assumption we are supposed to argue that any bracketing of $n$ elements must break into two subproducts so that we can apply the induction assumption to each subproduct.

My problem is that I don't know how the breaking into two subproducts given any bracketing of $n$ elements in justified.

 

[fresh_42]

It says after proving the trivial base cases, suppose that for any $k < n$ that any bracketing of the product of $k$ elements can be reduced without altering the value to an expression of the form $b_1 \cdot (b_2 \cdot (b_3 \cdot ( \cdots \cdot b_k)) \dots)$. Given this assumption we are supposed to argue that any bracketing of $n$ elements must break into two subproducts so that we can apply the induction assumption to each subproduct.

My problem is that I don't know how the breaking into two subproducts given any bracketing of $n$ elements in justified.

So this is the induction hypothesis:

Suppose that [if] for any $k < n$ that any [given] bracketing of the product of $k$ elements then ...

Now we have to prove:

Suppose that if $k=n$ that some given bracketing of the product then: ...

It is part of our IF clause. We have some given bracketing of $n$ elements. In case it is of the form $a_1(a_2(\ldots a_n)\ldots )$ we are done. All other cases are of the form $(a_1 \ldots a_k)(a_{k+1}\ldots a_n)$ with some bracketing of the two parts and $1<k$. I assume we have commutativity, too, so we may assume $k<n-1$, too. For the non commutative case, the expression $a_1\ldots a_n$ has to be explained, as e.g. in the case of functions. It is sloppy to write $fg$ and not mentioning whether $g(f(x))$ or $f(g(x))$ is meant. It's usually the latter, but purists prefer the first version.