The associative law for addition states:
$a+(b+c)=(a+b)+c$
Considering only this law for the sum $a_{1}+...+a_{n}$ of $n$ numbers $a_{1}+...+a_{n}$. How many equivalent expressions exist?
Some context
I restarted reading Michael Spivak's Calculus and, just for fun, came up with this problem (I didn't check if maybe it's one of the exercises in the book...).
I am not a professional mathematician and my mathematical abilities are very rusty (to say the least) since I went to college, so I would ask to whoever wants to help me reach a solution to keep this in mind.
I don't understand how to reach a proof to this problem. If I manage to derive a formula, wouldn't I have to check with the pictorial representation of the sum whether it is right or not?
My attempt at a solution
So, I can start small, and say:
-> For $n=3$, the solution is $2$. Namely,
$(a_{1}+a_{2})+a_{3}\tag{1.1}$
$a_{1}+(a_{2}+a_{3})\tag{1.2}$
-> For $n=4$, the solution is $5$. Namely,
$((a_{1}+a_{2})+a_{3})+a_{4}\tag{2.1}$
$(a_{1}+(a_{2}+a_{3}))+a_{4}\tag{2.2}$
$a_{1}+((a_{2}+a_{3})+a_{4})\tag{2.3}$
$a_{1}+(a_{2}+(a_{3}+a_{4}))\tag{2.4}$
$(a_{1}+a_{2})+(a_{3}+a_{4})\tag{2.5}$
We can already see that when we plug in a new summand to the expressions in the previous solution, we obtain a valid equivalent expression for this number of elements. In addition to this, $2.3$ and $2.4$ are a mirror image of $2.1$ and $2.2$, respectively. So we can say that the solution for $n=4$ is two times the solution for $n=3$ plus something else.
-> When we plug in the fifth summand we have a n=3 case for each of the previous expressions. Following the previous reasoning, accounting for the mirror expressions, the solution for $n=5$ is going to be $5·2·2=20$.
From this, I think in cases where $n$ is odd, the solution is $2·f(n)$, where $f(n)$ is the product of all previous solutions. My suspicion is that, if $n$ is even, the solution is $2·f(n)+1$.
If this is true. How do I go about making sure of this without spending an eternity printing out expressions and comparing them?
If it isn't true. How did you disprove it?