Clarification regarding Spivak, exercise 1-24

Question

The 24th problem in the first chapter of Spivak's Calculus has to do with proving that the placement of parentheses in a sum is irrelevant. Let $s(a_1, a_2,... a_{n})$ denote some sum formed from $a_1, a_2,...a_n$. For example, if $n=5$, $s(a_1, a_2,... a_{5})$ may represent $(a_1 + a_2) + (a_3 + (a_4 + a_5))$, $((a_1 + a_2) + (a_3 + a_4)) + a_5$, etcetera.

Part C of the question asks us to prove that $s(a_1, a_2,... a_{n}) = a_1 + a_2 + .... a_n$.

Note that $a_1 + a_2 + .... a_n$ is defined as $a_1 + (a_2 + (a_3 +....+ (a_{n-2} + (a_{n-1} + a_n)))..))$

A very helpful hint was given for this exercise. He tells us that there must be two sums $s'(a_1, a_2,... a_{l})$ and $s''(a_{l+1}, a_2,... a_{n})$ such that $s'(a_1, a_2,... a_{l}) + s''(a_{l+1}, a_2,... a_{n}) = s(a_1, a_2,... a_{n})$. Then we may use complete induction since the statement for $n=1$ is (trivially) true (as well as another identity proven in part B of the exercise, namely $(a_1 + a_2 + .... a_k) + (a_{k+1} + a_{k+2} + .... a_n) = a_1 + a_2 + .... a_n$) to obtain the desired result.

The problem I have is proving the hint itself! Namely that $s(a_1, a_2,... a_{n})$ may be "partitioned" such that for some $l<n$ there exists two sums which satisfy $s'(a_1, a_2,... a_{l}) + s''(a_{l+1}, a_2,... a_{n}) = s(a_1, a_2,... a_{n})$. I am inclined to dismiss the hint as obvious but I cannot---the purpose of the exercise is to rigorously prove the most obvious facts about addition. I've tried been playing around with various tricks using induction but so far have had no luck. I can't think of any other method given the sheer multitude of variations on parentheses, especially for large $n$. Any help would be appreciated.

Answer 1

Greg Martin's comment contains the answer, but it may be worth elaborating a bit. Perhaps you should say what definition of fully parenthesized sum you are using. I will give mine below, but it may disappoint you since the property you are trying to prove becomes true by definition. If you are using some other definition, I would be happy to delete or modify my answer.

I define a fully parenthesized summand to be either a primitive element (an indeterminate or number) or an expression of the form $(A+B)$, where both $A$ and $B$ are fully parenthesized summands. With this definition, it is always clear what the two summands are for each plus sign; an expression like $(x+y+z)$ is ambiguous, since it is not clear whether the right summand of the first plus sign is $y$ or $y+z$, but $(x+y+z)$ is not a fully parenthesized summand by my definition. Then define fully parenthesized sum to be either a primitive element or an expression of the form $A+B$, where both $A$ and $B$ are fully parenthesized summands. The definition is structured this way (distinguishing sum from summand) to avoid having an extra pair of parentheses around the entire expression. (Summands differ from sums, for expressions of two or more terms, only in having these extra outer parentheses.)

Given an ordered list of, say, indeterminates, $a_1,a_2,\ldots,a_n$, a fully parenthesized sum of those elements should be an expression in which $a_i$ appears to the left of $a_j$ in the expression if $i<j$. To enforce this, we make the following definitions. A fully parenthesized summand of $a_1,a_2,\ldots,a_n$ is $a_1$ if $n=1$ and an expression of the form $(A+B)$ if $n>1$, where $A$ is a fully parenthesized summand of $a_1,a_2,\ldots,a_l$ and $B$ is a fully parenthesized summand of $a_{l+1},a_{l+2},\ldots,a_n$ for some $1\le l<n$. A fully parenthesized sum of $a_1,a_2,\ldots,a_n$ is $a_1$ if $n=1$ and an expression of the form $A+B$ if $n>1$, where $A$ is a fully parenthesized summand of $a_1,a_2,\ldots,a_l$ and $B$ is a fully parenthesized summand of $a_{l+1},a_{l+2},\ldots,a_n$ for some $1\le l<n$.

The statement you are trying to prove is now true by definition: $s'(a_1,\ldots,a_l)$ and $s''(a_{l+1},\ldots,a_n)$ are the $A$ and $B$ of the definition. I don't see any straightforward alternative definition that captures the needed properties, namely, that the left and right summands of every addition operation are unambiguously identified, and that the indeterminates appear an a specified left-to-right ordering.

Incidentally, a lot is known about fully parenthesized sums. Here are the first several. $$ \begin{aligned} &x_1 && \text{($1$ sum)}\\ &x_1+x_2 &&\text{($1$ sum)}\\ &(x_1+x_2)+x_3,\ x_1+(x_2+x_3) && \text{($2$ sums)}\\ &((x_1+x_2)+x_3)+x_4,\ (x_1+(x_2+x_3))+x_4,\ (x_1+x_2)+(x_3+x_4),\\ &\qquad x_1+((x_2+x_3)+x_4),\ x_1+(x_2+(x_3+x_4)) && \text{($5$ sums)}\\ \end{aligned} $$ For five indeterminates, there are $14$ sums; for six, there are $42$. These are the Catalan numbers, which enumerate many different combinatorial structures. Our definitions imply that if $C_n$ is defined to be the number of fully parenthesized sums in $n+1$ indeterminates, then $C_n$ satisfies the recurrence $$ \begin{aligned} C_0&=1,\\ C_n&=\sum_{j=0}^{n-1}C_jC_{n-1-j} && \text{if $n\ge1$.} \end{aligned} $$ These sums are closely related to full binary trees (see the linked article on Catalan numbers).

Answer 2

By definition \begin{equation} \forall n\in\mathbb{N},\,a_1,\dots,a_n\in\mathbb{R},\,s(a_1,\dots,a_n)=a_1+(a_2+(\dots+(a_{n-1}+a_n)\dots)); \end{equation} in particular: \begin{gather} s(a_1)=a_1,\\ s(a_1,a_2)=a_1+a_2=s(a_1)+s(a_2). \end{gather} The claim is prove that \begin{equation} \mathscr{P}(l,n)\equiv s(a_1,\dots,a_l,a_{l+1},\dots,a_n)=s(a_1,\dots,a_l)+s(a_{l+1},\dots,a_n) \end{equation} is true for any $l\leq n\in\mathbb{N}_{\geq1}$; for $l=n=1$ and $l=1,n=2\,\mathscr{P}(l,n)$ holds.

Fixed $l=1$, trivially by definition: $\mathscr{P}(1,n)$ holds forn any $n$; explicitly: \begin{gather} \forall n\in\mathbb{N},\,a_1,\dots,a_n\in\mathbb{R},\,s(a_1,\dots,a_n)=a_1+(a_2+(\dots+(a_{n-1}+a_n)\dots))=\dots\\ \dots=s(a_1)+s(a_2,\dots,a_n). \end{gather} By previous reasoning: \begin{gather} \forall n\in\mathbb{N},\,a_1,\dots,a_n\in\mathbb{R},\,s(a_1,\dots,a_n)=\dots\\ \dots=s(a_1,a_2)+s(a_3,\dots,a_n) \end{gather} that is $\mathscr{P}(2,n)$ holds for any $n\geq 2$; as inductive hypothesis, we can assume that $\mathscr{P}(l,n)$ holds for any $n$ and for a fixed $l+1<n$, then: \begin{gather} \forall n\in\mathbb{N},\,a_1,\dots,a_n\in\mathbb{R},\,s(a_1,\dots,a_n)=s(a_1,\dots,a_l)+s(a_{l+1},\dots,a_n)=\\ =s(a_1,\dots,a_l)+a_{l+1}+s(a_{l+2},\dots,a_n)=\\ =s(a_1,\dots,a_{l+1})+s(a_{l+2},\dots,a_n) \end{gather} that is $\mathscr{P}(l+1,n)$ holds for any $n$ and for any $l+1\leq n$; then by induction: $\mathscr{P}(l,n)$ holds for any $l\leq n\in\mathbb{N}_{\geq1}$.

Is it all clear?

Answer 3

Denote by $\oplus$ the addition operation taking exactly two inputs, by $s(1,2,\ldots,n)$ a sum $a_1+a_2+\ldots+a_n$ with unspecified parenthesization, and by ${\rm st}(1,2,\ldots,n)$ the same sum using Spivak's "standard summation convention". It follows that $$s(1)={\rm st}(1),\quad s(1,2)={\rm st}(1,2)\ .$$ Assume now that $n\geq3$, and that for all $r<n$ one has $$s(1,\ldots,r)={\rm st}(1,\ldots r)\ .$$ Let an $s(1,\ldots,n)$ be given. There is a "last" operation $\oplus$ in the buildup of $s(1,\ldots,n)$. This means that there is an $r$ with $1\leq r\leq n-1$ such that $$s(1,\ldots,n)=s(1,\ldots,r)\oplus s(r+1,\ldots, n)\ .\tag{1}$$ Apply the induction hypothesis to both parts on the right hand side of $(1)$, and obtain $$s(1,\ldots,n)={\rm st}(1,\ldots,r)\oplus{\rm st}(r+1,\ldots,n)\ .\tag{2}$$ If $r=1$ the right side of $(2)$ is equal to ${\rm st}(1,\ldots,n)$, by definition. If $r>1$ we obtain, using the associative law in the form $(a\oplus b)\oplus c=a\oplus(b\oplus c)$, and of course the induction hypothesis, that $$\eqalign{s(1,\ldots,n) &=\bigl(s(1)\oplus{\rm st}(2,r)\bigr)\oplus {\rm st}(r+1,\ldots, n)\cr &=s(1)\oplus\bigl({\rm st}(2,r)\oplus {\rm st}(r+1,\ldots, n)\bigr)\cr &=s(1)\oplus{\rm st}(2,\ldots,n)\cr &={\rm st}(1,\ldots,n)\ .\cr}$$

Answer 4

I will shortly describe a rigorous approach to this question. Let me first say, however, that if anything in Spivak's book is obvious to you, then the hint should be obvious too. If you begin asking questions about the syntax of terms (see below), then you are really asking about how mathematical statements are formalized rather than what those statements mean. And this is a level of precision that is rarely encountered except in discussing mathematical logic.

Define a word in the language $L = \{+\}$ to be any finite sequence of symbols taken from an alphabet consisting of the symbol $+$ and variables $x, y, z, \dots$. The set of terms in $L$, denoted $T_L$, is the smallest set of words satisfying the following conditions:

• The set $T_L$ contains all one-letter words consisting of a variable.

• If $t, t' \in T_L$, then the word $+tt'$ is in $T_L$. (This is Polish notation. A variant would be to use $(t + t')$. In that case, although it complicates things, you could add an additional optional rule that the outermost parentheses in a term can be removed at the end of the process.)

The fact that a smallest such set exists follows by considering the intersection of all sets of words satisfying the above two conditions.

Now we want to prove that every term $t$ that is not a variable is of the form $+t_1 t_2$ for two terms $t_1, t_2$ (which necessarily contain fewer $+$ symbols than does $t$).

Let $U$ be the set of all terms that are either a variable or of the form $+t_1 t_2$ for some terms $t_1$, $t_2$. Then $U$ satisfies the above two conditions. Since $T_L$ is the smallest set of words satisfying the two conditions, and $U \subseteq T_L$, we must in fact have $U = T_L$.

Note. The above definition of terms does not deal at all with how, given a term $t$, a numerical value is assigned to it once values have been assigned to the variables $x, y, z, \dots$. To do this, you need to prove a "unique reading lemma" that shows that given a term $t$ that is not a variable, the decomposition $t = +t_1 t_2$ stated above is unique. The definition of the value of the term for a given assignment of values to the variables $x, y, z, \dots$ can then proceed by induction, for example on the length of the term. The details of this are worked out in Mathematical Logic by Cori and Lascar.