How does one actually show from associativity that one can drop parentheses?

Solution 1:

You can prove by induction on the number of factors that all such products are equal. We show that if you have $a_1,\ldots,a_n$, then any way to place the parenthesis will yield the same result as $a_1(a_2(\cdots(a_{n-1}a_n)\cdots))$.

If the number of factors is $1$ or $2$, then the result is immediate. If the number of factors is $3$, then it follows precisely by associativity: $(a_1a_2)a_3 = a_1(a_2a_3)$.

Assume the result holds for any $k$, $1\leq k\lt n$, and you have some product of $n$ elements $a_1,\ldots,a_n$, in order, with parentheses placed in some arbitrary (but valid) manner. Then there exists $k$, $1\leq k\lt n$, such that the product is of the form $$w_1(a_1,\ldots,a_k)\cdot w_2(a_{k+1},\ldots,a_n)$$ where $w_1(a_1,\ldots,a_k)$ is just an expression involving the product of $a_1,\ldots,a_k$ with parentheses placed in some fashion, and similarly with $w_2$. (We are just looking at the "last" product to be done; e.g., if you have $((a_1a_2)a_3)(a_4a_5)$, we would have $k=3$, $w_1(a_1,a_2,a_3) = (a_1a_2)a_3$, and $w_2(a_4,a_5) = a_4a_5$; if you have $a_1((a_2a_3)(a_4a_5))$, then $k=1$, $w_1(a_1) = a_1$, and $w_2(a_2,a_3,a_4,a_5) = (a_2a_3)(a_4a_5)$; etc).

By induction we can write $$w_1(a_1,\ldots,a_k) = a_1(a_2(\cdots(a_{k-1}a_k)\cdots))$$ so \begin{align*} w_1(a_1,\ldots,a_k)w_2(a_{k+1},\ldots,a_n) &= \Bigl(a_1\bigl(a_2(\cdots(a_{k-1}a_k)\cdots)\Bigr)\cdot w_2(a_{k+1},\ldots,a_n)\\\ &= a_1\cdot\Bigl(a_2(\cdots(a_{k-1}a_k)\cdots)w_2(a_{k+1},\ldots,a_n)\Bigr) \\\ &= a_1\cdot\Bigl( a_2(a_3(\cdots(a_{n-1}a_n)\cdots)\Bigr) \end{align*} where the last equality follows from the induction hypothesis applied to a product with $n-1$ factors, and the immediately preceding equality by simple associativity of three factors, applied to $a_1$, $a_2(\cdots(a_{k-1}a_k)\cdots)$, and $w_2(a_{k+1},\ldots,a_n)$. (Note: If $k=1$, then you can skip directly from the first line to the last line without having to invoke associativity; the argument still holds.)

Thus, any expression of a product of $a_1,\ldots,a_n$, in that order, with parentheses placed in an arbitrary but valid manner, is equal to $$a_1(a_2(\cdots(a_{n-1}a_n)\cdots)),$$ This completes the induction and the proof.

Since all ways of associating a product of $n$ factors, $a_1,\ldots,a_n$ yield results that are equal to one another, we may freely write any such product simply as $a_1\cdots a_n$ to represent their common value.

Solution 2:

Hint $ $ It's very easy: keep pushing ')'s rightward using the rewrite rule $\rm\ (xy)z\ \to\ x(yz).\,$ This process terminates with the right-associated normal form where all ')'s are at the right end, namely $\rm\ a(b(c(d(\cdots))),\, $ written $\rm\ abc\cdots $ (unambiguous - since every bracketing rewrites to it by below).

Below is a proof sketch, by induction on the length $\rm\:\ell(Z) = $ number of operands (factors)

$\rm \ell(Z)\, =\, 1\!:\ \ \ Z = a\ $ is in normal form

$\rm \ell(Z)\, >\, 1\!:\ \ \ Z = XY\ $ where $\rm\:\ell(X),\ell(Y)< \ell(Z)\,$ splits into $2$ cases:

$\rm\ \ \ell(X)\! =\! 1\!:\ \ \ XY = aY = a(b(c(\cdots)))\ $ by induction applied to $\rm Y$

$\rm\ \ \ell(X)\! >\! 1\!:\ \ \ XY = \underbrace{(a \bar X)Y = a(\bar X Y)}_{\rm associative\ law} = a(b(c(\cdots)))\ $ by induction applied to $\rm X,\, $ then $\rm\bar XY$

The proof used only the associative law $\rm\, (XY)Z = X(YZ)\,$ so works for any associative operation.