1

I want to use induction to show that the sum $x_1 + \dots + x_n$ of real numbers is defined independently of parentheses to specify order of addition.

I know how to apply induction(base, assumption, k+1 applying inductive hypothesis). Here I am not sure what the base would be. I have two ideas:

1) First case is $(x_1 + x_2)+x_3+\dots+x_n$ and work through to $x_1+x_2+\dots+x_{n-2} + (x_{n-1} + x_n)$

2) Start with $(x_1+x_2)+x_3=x_1+(x_2+x_3)$ and work up in number of elements to the full case.

Both seem wrong, I have no idea what to actually do.

I imagine above is sufficient effort, although I have shown no working. Before you downvote, please tell me why you are planning it, and I will edit.

Asaf Karagila
  • 393,674
qqqqq
  • 11

1 Answers1

0

Your first idea is ambiguous, since the expressions aren't fully parenthesized. Note that for $4$ terms, there are $5$ possible parenthesizations: $((x_1+x_2)+x_3)+x_4$, $(x_1+(x_2+x_3))+x_4$, $(x_1+x_2)+(x_3+x_4)$, $x_1+((x_2+x_3)+x_4)$, and $x_1+(x_2+(x_3+x_4))$. (In general, the number of parenthesizations of an expression with $n$ terms is the Catalan number $C_{n-1}$.)

I wouldn't bother trying to go through all of the different parenthesizations in some order, but use your second idea instead. So the induction hypothesis is that every parenthesization of $k$ terms is equivalent to every other, and you want to prove the same for $k+1$ terms (for $k\geq3$). Actually, come to think of it, it will probably be easier to use strong induction: the induction hypothesis is that every parenthesization of $k$ terms is equivalent to every other whenever $k<n$, and prove the same for $n$ terms (for $n>3$). It may help to note that any given parenthesization has a position where the last operation (in the order that they are carried out) is applied.

Toby Bartels
  • 4,679