Generalized Associative Law

  • #1
1,462
44
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?
 

Answers and Replies

  • #2
14,358
11,671
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.
 
  • #3
1,462
44
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.
 
  • #4
14,358
11,671
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.
 
  • Like
Likes Mr Davis 97

Related Threads on Generalized Associative Law

Replies
6
Views
4K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
20
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
4
Views
2K
Replies
2
Views
7K
  • Last Post
Replies
5
Views
3K
Top