Associative implies generalized associative
Statement
Let be a set and be a binary operation on . Suppose that is an associative binary operation; in other words:
Then, for any positive integer , every possible parenthesization of the expression:
is equivalent.
Proof
The technique of proof here is a strong form of induction: we assume the result is true for every , and we prove it for . Note that the cases are tautological. For the case , there are precisely two possible parenthesizations, and associativity tells us that they are both equal.
Thus, assume , and that the result holds for all . We will show that any way of parenthesization of:
is equal to the left-associated expression:
Let's prove this. For any method of parenthesization, there is an outermost multiplication, and in terms of this outermost multiplication, we can view the parenthesization as:
where and , both parenthesized in some unknown way, with . Applying the induction assumption, equals the left-associated expression for and equals the left-associated expression for .
Now, in the case that is a single letter (i.e., ), we are already done: equals the left-associated expression. If not, we can write as:
where is the left-associated expression for . Applying associativity, we get that the original expression equals:
which is precisely the left-associated expression for .
References
- Abstract Algebra by David S. Dummit and Richard M. Foote, 10-digit ISBN 0471433349, 13-digit ISBN 978-0471433347, ^{More info}, Page 18-19, Section 1.1, Proposition 1 (statement on page 18, proof on page 19)