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
. Thus, 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)