3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As far as I can tell (and I may be wrong), we cannot presume the hint's statement to be true. Advice: Use strong induction. Your hypothesis/premise should lead to the hint's statement and, by extension, the proof's completion. $\endgroup$ – Corellian Dec 7 '15 at 5:50
  • $\begingroup$ @Brody Thanks, that is helpful. $\endgroup$ – YouKnowNothing Dec 7 '15 at 5:59
  • 2
    $\begingroup$ I think the hint is true. It's just saying that there is an addition that is "outermost" in scope (that is, the last addition that would be performed if you started adding things according to the parentheses). This should follow directly from your definition of a valid parenthesized sum (which, for example, excludes $(a+b)+c+(d+e)$). $\endgroup$ – Greg Martin Feb 12 '16 at 4:51
  • $\begingroup$ Actually, the hint is obvious. The only way to make the statement any more precise would be a precise study of the syntax of terms. In that case, the problem becomes one of definitions as much as proof. These topics are typically discussed in books on logic, such as the one by Cori and Lascar (translated from French). In that situation, the fact that every term $t$ in the language $\{+\}$ has the form $t + t'$ (or technically $+tt'$ in Polish notation) could conceivably be proved by induction on the complexity of $t$. My advice is not to worry about a rigorous treatment of syntax at... $\endgroup$ – David Feb 16 '16 at 17:58
  • $\begingroup$ ...this stage of your studies. Correction: every term of length greater than $1$. $\endgroup$ – David Feb 16 '16 at 17:58
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I believe OP might not have been totally clear, but the actual question in Spivak's text does not state that $\,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 ))$. In fact, this is what must be proven. This is what it says. The exercise is multi-part so I will not quote the whole thing. "24. Let us agree for definiteness that $a_1 + a_2...a_n$ will denote $a_1+(a_2+(\dots+(a_{n-1}+a_n) \dots))$. Let $s(a_1,...,a_k)$ be some sum formed from $(a_1,\dots,a_k)$. Prove $s(a_1,\dots,a_k) = a_1 + a_2...a_n $." The hint is given for this question. $\endgroup$ – MathematicsStudent1122 Feb 16 '16 at 16:07
  • $\begingroup$ With $s(a_1,\dots,a_k)$, the idea is that the parentheses could be anywhere. We must show that, given the parentheses are "randomly" placed, the sum works out to be the same as the standard definition $a_1 + a_2...a_n$. As noted, the idea is to show that parentheses do not make a difference in sums. $\endgroup$ – MathematicsStudent1122 Feb 16 '16 at 16:09
  • $\begingroup$ @MathematicsStudent1122: The point is that the parentheses can't be placed randomly, as I'm sure you're aware since you put the word "randomly" in quotation marks. The moment you start to formulate precisely what sorts of parenthesized expressions are legitimate and which aren't, I think you'll be well on your way toward answering your question. $\endgroup$ – Will Orrick Feb 16 '16 at 23:53
  • $\begingroup$ @WillOrrick The precise definition of $s(a_1,a_1,...a_n)$ is given in the first comment from the author himself. The word "randomly"--in retrospect obviously not the best word choice--is used informally by me in the subsequent comment merely to get the idea across. It should also be noted that this is not my question; I was struggling with this exercise and stumbled on this question here. $\endgroup$ – MathematicsStudent1122 Feb 17 '16 at 0:05
  • $\begingroup$ Are you speaking of these sentences: "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."? $\endgroup$ – Will Orrick Feb 17 '16 at 0:10
0
+50
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I will be temporarily deleting this answer shortly to encourage others to post answers before the bounty expires. I do believe, however, that this answer describes the right way to think about the problem, so I plan to undelete it once the bounty period is over (unless something much better comes along). The point I wanted to make is that recursive definitions are generally the best way to go about describing structures that can be deeply nested, and that any recursive definition of this type of expression is likely to contain the stated property as part of the definition. $\endgroup$ – Will Orrick Feb 15 '16 at 2:10
  • $\begingroup$ Since there are now lots of answers, I've decided it's OK to undelete mine. $\endgroup$ – Will Orrick Feb 16 '16 at 17:44
0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ The "obvious" aspect is that there is a "last operation $\oplus$ in the buildup". This is taken for granted in your answer. The question essentially boils down to, can this be taken for granted or is it proven? $\endgroup$ – MathematicsStudent1122 Feb 16 '16 at 19:51
  • $\begingroup$ Some other respondents say it may be taken for granted; perhaps you could share your opinion. $\endgroup$ – MathematicsStudent1122 Feb 16 '16 at 20:02

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.