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.

  • $\begingroup$ You cool with Peano's axioms? $\endgroup$ – Daniel W. Farlow Jan 29 '15 at 5:55
  • $\begingroup$ @qqqqq Peano's axioms are a definition of integers. $\endgroup$ – Alice Ryhl Jan 29 '15 at 5:56
  • $\begingroup$ @induktio Yeah from wiki it all seems familiar(except written full set theoretic). Equivalence relations, abelian group and ring construction, looks good $\endgroup$ – qqqqq Jan 29 '15 at 6:00

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.