Proof verification for showing that the sum of real numbers is independent of parenthesis using induction

Question

Let $S_n = x_1+x_2+\ldots + x_n$ be the sum of n real numbers and $P(n)$ be the property that $S_n$ is independent of parenthesis and E$:= \{ i \in \Bbb N : P(i) \}$ , then,

$$ (S_1 = x_1 = (x_1) ) \implies P(1) \implies (1 \in E) $$

$$ S_r = x_1 +x_2 + x_3 + \ldots + x_r = (x_1+\ldots+x_{r-1})+x_r =\ ...\ = (...((x_1+x_2)+x_3)+...)+x_{r-1})+x_r$$

thus,$$S_r = (...((S_2+x_3)+x_4)+...)+x_{r-1})+x_r = (...(S_3+x_4)+...+x_{r-1})+x_r =\ \ldots \ =S_{r-1}+x_r$$

thus if P(r-1) is true,i.e, all permutations for within parenthesis level is true, then, $$(r-1 \in E)\implies P(r-1) \implies P(r) \implies (r \in E)$$

Is this proof valid? If not then what am I doing wrong or what can be done further?

Answer 1

You seem only to be considering the special case in the induction step where the expression has the form $( \ldots ) + x_r$, but it could have the form $( \ldots ) + (\ldots)$.

I would approach this by thinking about an algorithm to put an arbitrary well-formed expression $t$ formed from variables $x_1, x_2, \ldots$ using addition and brackets into a normal form. Like you, I will assume that the variables in $t$ are listed in order as $x_1, x_2 \ldots, x_n$ and I will assume that $t$ is fully bracketed: i.e., every sub-expression of the form $X + Y$ is enclosed in brackets (so that $t$ contains $n-1$ pairs of matching brackets). The normal form I will choose is the right associative form $(x_1 + (x_2 + (x_3 + (\ldots ))\cdots)$ (where $\cdots$ stands for a string of right brackets). The algorithm looks for for the left-most left bracket in $t$ that begins a sub-expression of the form $(X + Y) + Z$ (for some sub-expressions $X$, $Y$ and $Z$) and, if it finds one, it replaces that sub-expression by $X + (Y + Z)$ to give a new expression $t'$. The algorithm terminates if no left brackets in $t$ begin a sub-expression of the form $(X + Y) + Z$, i.e., if every left bracket in $t$ begins a sub-expression of the form $(x_i + Y)$.

To prove the algorithm works, you do induction on the number $N(t)$, say, that sums over each right bracket in $t$ the number of variables following that right bracket. If $N(t) = 0$, then $t$ must have the form $(x_1 + (x_2 + (x_3 + (\ldots )) \cdots)$. If $N(t) > 0$, then one step of the algorithm will give a new expression $t'$ with $N(t') < N(t)$ and with $t = t'$ (for any assignment of real numbers to the $x_i$). By induction $t'$ is equal to $((x_1 + (x_2 + (x_3 + (\ldots )) \cdots)$ and hence so is $t$ and we are done.

Answer 2

First you need to reason by strong induction and assume that the sums are independent of the placement of parentheses for any $i < r$.

Then, consider some sum $S_r$ of $r$ numbers, with some admissible parentheses.

Then one may write $$ S_r = (\text{some term with $+$ and $x_1$, ..., $x_k$}) + (\text{some term with $+$ and $x_{k+1}$, ..., $x_r$}), $$ with $1 \leq k < r$. By the induction hypothesis, the left operand equals $(...(x_1 + x_2) + x_3) + ... ) + x_k) = (S_k) = S_k$. Now consider two cases. If $k+1 = r$, then we have $$ S_r = (...(x_1 + x_2) + x_3) + ... ) + x_{n-1}) + x_n $$ and it is over. If $k+1 < n$, then the right operand can be (again by the induction hypothesis) written $S' = T + x_n$, where $ T = (...(x_{k+1} + x_{k+2}) + ...) + x_{n-1}) $ Thus, by associativity of $+$ (this has to appear somewhere) $$ S_r = S_k + (T + x_{n}) = (S_k + T) + x_{n} $$ and so is independent of the parentheses.