I am studying for one of my exams, and and this question appeared in the practice problems for the exam. I tried proving it but got stuck midway. What I tried was using strong induction to induct on the number of brackets in a given expression. However, I am not quite sure how to build my proof based on this. I was able to do the base case and inductive hypothesis, but when it came to the inductive case, I was unsure how to proceed. Would inducting on the number of brackets be helpful in this scenario?
Any sort of help will be immensely appreciated.
Best Answer
Strong induction.
Suppose we know that any group of $k < n$ terms the product will be the same no matter which order we do the operations in.
So if we have any $(a_1.....a_k)(a_{k+1}.....a_n)$ where $k <n$ then in wont matter which order we do them within parenthesis.
So that mean every way of arranging $n$ terms will have the same result as any other way of arranging them provided the two largest subgroupings are broken into the same to groups of $k$ and $n-k$ terms.
[For example: $(a_1a_2a_3)(a_4a5a6)$ will be the same value whether $a_1a_2a_3$ is done as $a_1(a_2a_3)$ or as $(a_1a_2)a_3$ and the same for how we arrange $a_4a_5a_6$. And we know that $(a_1a_2)(a_3a_4a_5a_6)$ will be the same no matter how we arrange that $a_3a_4a_5a_6$. But we currently DON'T know if $(a_1a_2)(a_3a_4a_5a_6)$ must be the same as $(a_1a_2a_3)(a_4a5a6)$.]
[That will be the next thing we have to show. That $(a_1.....a_j)(a_{j+1}....a_n) = (a_1.....a_k)(a_{k+1}.....a_n)$ for any $j$ and $k$. Will prove that with induction. Basic induction.]
Now as it doesn't matter how we arrange the $a_1...a_k$ or the $a_{k+1}...a_n$ terms we have
$(a_1....a_k)(a_{k+1}....a_n)=$
$(\color{red}{(a_1....a_{k-1})}\color{blue}{a_k})\color{green}{(a_{k+1}....a_n)}$ is a product with three terms so
$(\color{red}{(a_1....a_{k-1})}\color{blue}{a_k})\color{green}{(a_{k+1}....a_n)}=$
$\color{red}{(a_1....a_{k-1})}(\color{blue}{a_k}\color{green}{(a_{k+1}....a_n)})=$
$(a_1....a_{k-1})(a_k.... a_n)=(a_1....a_k)(a_{k+1}....a_n)$.
And likewise $(a_1....a_k)(a_{k+1}....a_n)=$
$(\color{red}{(a_1....a_{k})}(\color{blue}{a_{k+1}}\color{green}{(a_{k+2}....a_n)})$
$(\color{red}{(a_1....a_{k})}\color{blue}{a_{k+1}})\color{green}{(a_{k+2}....a_n)})=$
$(a_1....a_{k+1})(a_{k+2}.... a_n)=(a_1....a_k)(a_{k+1}....a_n)$.
And thus by induction every way of arranging $n$ terms regardless of how you split them into two groups will have the same result.