Order of calculation in a Semigroup. If $(A,\cdot)$ is a semigroup, i.e. if we have:
$\forall (x,y,z)\in A^{3}, (x\cdot y)\cdot z=x\cdot(y\cdot z)$, then the order of calculations doesn't matter no matter the number of factors and we can do aways with the parenthesis, for example:
$\forall (w,x,y,z)\in A^{4}, (w\cdot(x\cdot y))\cdot z=(w\cdot x)\cdot(y\cdot z)=w\cdot x\cdot y\cdot z $
It seems obvious but I don't really know how to prove this for any n-uple of elements of A. It probably is a recurrence, but I don't see how to write it. Help?
 A: Prove, by induction on $n$, that every parenthesization of $n$ or fewer factors gives the same product as "parenthesization to the left".  The cases of $n=1$ and $2$ are trivial, and $3$ is the assumption of associativity; these provide the basis of the induction. For the induction step, regard any product of $n+1$ factors as the product of two pieces, each having $n$ or fewer factors. Apply the induction hypothesis to each of the two pieces; then apply associativity to put it in the form of a complicated product of $n$ elements times (on the right) a single element; finally, apply the induction hypothesis once more to that complicated product.
A: This is a standard thing, with a standard proof that I don't know. Here's a fairly simple proof.
Given $x_1,\dots,x_n$, define the standard grouping for the product $x_1\dots x_n$ to be "$\prod_{j=1}^nx_j$", defined recursively by $\prod_{j=1}^1x_j=x_1$ and $$\prod_{j=1}^{n+1}x_j=\left(\prod_{j=1}^nx_j\right)x_{n+1}.$$
It's enough to prove by induction on $n$ that if $\alpha$ is any grouping of the product $x_1\dots x_n$ then $\alpha$ is equal to the standard grouping.
Now, there exist a grouping $\beta$ of the product $x_1\dots x_k$ and a grouping $\gamma$ of the product $x_{k+1}\dots x_n$ such that $$\alpha=\beta\gamma.$$Here $1\le k<n$. Since both $\beta$ and $\gamma$ involve fewer variables, you can assume by induction that $$\beta=\prod_{j=1}^kx_j$$and$$\gamma=\prod_{j=k+1}^nx_j.$$So you only need to show that $$\left(\prod_{j=1}^{k}x_j\right)\left(\prod_{j=k+1}^{n}x_j\right)=\prod_{j=1}^nx_j.$$
And you prove that by an easy induction on $n-k$, the number of factors in $\gamma$. It's true for $n-k=1$ by the definition of the standard grouping, and the induction step is trivial: $$\begin{eqnarray}\left(\prod_{j=1}^{k}x_j\right)\left(\prod_{j=k+1}^{n+1}x_j\right)&=&\left(\prod_{j=1}^{k}x_j\right)\left(\left(\prod_{j=k+1}^{n}x_j\right)x_{n+1}\right)
\\&=&\left(\left(\prod_{j=1}^{k}x_j\right)\left(\prod_{j=k+1}^{n}x_j\right)\right)x_{n+1}
\\&=&\left(\prod_{j=1}^nx_j\right)x_{n+1}
\\&=&\prod_{j=1}^{n+1}x_j.\end{eqnarray}$$
