Showing associativity holds over n elements Say we have a set $X$, with an associative binary operator $*$. How can we show that for any string $x_1 x_2 \ldots x_n$, when we insert brackets or the operation $*$, we will always get the same output?
Clearly this requires induction on $n$. The base case $n=1$ is trivial, but I cannot figure out how to move from my induction hypothesis, that the claim holds for strings of length less than $n$, to the fact that it holds for strings of length $n$.
The issue is that when I start with a string of length $n-1$, for example, there are so many ways to add the $x_n$ that I get lost. I think I need to split the string of length $n$ into small ones of lengths less than $n$ but I cannot figure out how to account for all possible forms of the string.
Thanks!
 A: Claim:

Any string including $x_1,x_2,\ldots,x_n$ as above is equal to 
  $$x = x_1 * (x_2 * ( \ldots *  (x_{n-1} * x_n ) \ldots ))) \in X$$

Proof:
Proceed by induction on $n$. The base case $n=1$ is trivial. Assume the above claim holds when the length is $k < n$.
Let $\phi$ be any such string of length $n$ that evaluates to $a \in X$. Then $\phi$ can be uniquely written as the * product of two shorter strings. Note that for expressions of length less than $n$, we will write simply $(x_1 x_2 \ldots x_l)$ because of the associativity guaranteed by the induction hypothesis. So:
$$\phi = (x_1 x_2 \ldots x_k) * (x_k x_{k+1} \ldots x_n)$$
And we can move the * all the way to the left by using associativity of three elements:
$$
\begin{aligned}
\phi \, &= (x_1 x_2 \ldots x_k) * (x_{k+1} \ldots x_n) \\
&= ((x_1 x_2 \ldots x_{k-1}) * x_k) * (x_{k+1} \ldots x_n) \\
&= (x_1 x_2 \ldots x_{k-1}) * (x_k x_{k+1} \ldots x_n) \\
&= ((x_1 x_2 \ldots x_{k-2}) * x_{k-1}) * (x_k \ldots x_n) \\
&= (x_1 x_2 \ldots x_{k-2}) * (x_{k-1} x_k \ldots x_n)
\end{aligned}
$$
and eventually
$$\phi = x_1 * (x_2 x_3 \ldots x_n)$$
which has the form
$$x = x_1 * (x_2 * ( \ldots *  (x_{n-1} * x_n ) \ldots ))) \in X$$
