Mixing
How to prove the generalized associative law for addition on $mathbb N$?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Let $(a_1,cdots,a_n)$ where $n>3$ be a finite sequence in $mathbb N$. Then there is a sequence $(s_1,cdots,s_n)$ such that $s_1=a_1$ and $s_i+1=s_i+a_i+1$ for all $1leq i<n$ (I proved this here). As a result, we write $s_n=a_1+cdots+a_n$.
I would like to ask how to prove $$a_1+cdots +a_k+a_k+1+a_k+2+cdots+a_n=(a_1+cdots +a_k)+a_k+1+(a_k+2+cdots+a_n)$$ with only basic properties of addition, which are listed below.
$(a+b)+c=a+(b+c)$
$a+b=b+a$
Please help me with some hints!
elementary-number-theory proof-writing peano-axioms
edited Aug 2 at 16:11
Bram28
54.8k33881
asked Jul 28 at 7:42
Le Anh Dung
740317
add a comment |Â
up vote
0
down vote
favorite
Let $(a_1,cdots,a_n)$ where $n>3$ be a finite sequence in $mathbb N$. Then there is a sequence $(s_1,cdots,s_n)$ such that $s_1=a_1$ and $s_i+1=s_i+a_i+1$ for all $1leq i<n$ (I proved this here). As a result, we write $s_n=a_1+cdots+a_n$.
I would like to ask how to prove $$a_1+cdots +a_k+a_k+1+a_k+2+cdots+a_n=(a_1+cdots +a_k)+a_k+1+(a_k+2+cdots+a_n)$$ with only basic properties of addition, which are listed below.
$(a+b)+c=a+(b+c)$
$a+b=b+a$
Please help me with some hints!
elementary-number-theory proof-writing peano-axioms
edited Aug 2 at 16:11
Bram28
54.8k33881
asked Jul 28 at 7:42
Le Anh Dung
740317
These sums with more than $3$ summands are ambiguous unless we already know what you're trying to prove. You'll need to define what you mean by them. One well-defined way of stating the problem would be to ask whether, if sums of $m$ summands have been defined for all $mlt n$, the sum of $n$ summands on the left-hand side can equivalently be defined by any of the expressions on the right-hand side independent of the choice of $k$.
– joriki
Jul 28 at 8:07
@joriki I have edited to remove such ambiguity. Can you elaborate more on These sums with more than 3 summands are ambiguous unless we already know what you're trying to prove. In my common sense, $a_1+a_2+cdots+a_n=(cdots((a_1+a_2)+a_3)cdots)+a_n)$.
– Le Anh Dung
Jul 28 at 8:18
1
That's just one arbitrary order in which the operations can be formed. It could also mean $a_1+(a_2+cdots+(a_n-1+a_n)cdots)$. In programming languages, operators are called "left-associative" or "right-associative", respectively, according to which of these conventions apply to them; see operator associativity. In mathematics, exponentiation is usually assumed to be right-associative, i.e. $mathrm e^x^2$ means $mathrm e^(x^2)$, not $(mathrm e^x)^2$ (which would make it equal to $mathrm e^2x$).
– joriki
Jul 28 at 8:23
@joriki I got it.
– Le Anh Dung
Jul 28 at 8:27
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $(a_1,cdots,a_n)$ where $n>3$ be a finite sequence in $mathbb N$. Then there is a sequence $(s_1,cdots,s_n)$ such that $s_1=a_1$ and $s_i+1=s_i+a_i+1$ for all $1leq i<n$ (I proved this here). As a result, we write $s_n=a_1+cdots+a_n$.
I would like to ask how to prove $$a_1+cdots +a_k+a_k+1+a_k+2+cdots+a_n=(a_1+cdots +a_k)+a_k+1+(a_k+2+cdots+a_n)$$ with only basic properties of addition, which are listed below.
$(a+b)+c=a+(b+c)$
$a+b=b+a$
Please help me with some hints!
elementary-number-theory proof-writing peano-axioms
edited Aug 2 at 16:11
Bram28
54.8k33881
asked Jul 28 at 7:42
Le Anh Dung
740317
Let $(a_1,cdots,a_n)$ where $n>3$ be a finite sequence in $mathbb N$. Then there is a sequence $(s_1,cdots,s_n)$ such that $s_1=a_1$ and $s_i+1=s_i+a_i+1$ for all $1leq i<n$ (I proved this here). As a result, we write $s_n=a_1+cdots+a_n$.
I would like to ask how to prove $$a_1+cdots +a_k+a_k+1+a_k+2+cdots+a_n=(a_1+cdots +a_k)+a_k+1+(a_k+2+cdots+a_n)$$ with only basic properties of addition, which are listed below.
$(a+b)+c=a+(b+c)$
$a+b=b+a$
Please help me with some hints!
elementary-number-theory proof-writing peano-axioms
edited Aug 2 at 16:11
Bram28
54.8k33881
asked Jul 28 at 7:42
Le Anh Dung
740317
edited Aug 2 at 16:11
Bram28
54.8k33881
edited Aug 2 at 16:11
Bram28
54.8k33881
edited Aug 2 at 16:11
Bram28
54.8k33881
54.8k33881
asked Jul 28 at 7:42
Le Anh Dung
740317
asked Jul 28 at 7:42
Le Anh Dung
740317
asked Jul 28 at 7:42
Le Anh Dung
740317
740317
These sums with more than $3$ summands are ambiguous unless we already know what you're trying to prove. You'll need to define what you mean by them. One well-defined way of stating the problem would be to ask whether, if sums of $m$ summands have been defined for all $mlt n$, the sum of $n$ summands on the left-hand side can equivalently be defined by any of the expressions on the right-hand side independent of the choice of $k$.
– joriki
Jul 28 at 8:07
@joriki I have edited to remove such ambiguity. Can you elaborate more on These sums with more than 3 summands are ambiguous unless we already know what you're trying to prove. In my common sense, $a_1+a_2+cdots+a_n=(cdots((a_1+a_2)+a_3)cdots)+a_n)$.
– Le Anh Dung
Jul 28 at 8:18
1
That's just one arbitrary order in which the operations can be formed. It could also mean $a_1+(a_2+cdots+(a_n-1+a_n)cdots)$. In programming languages, operators are called "left-associative" or "right-associative", respectively, according to which of these conventions apply to them; see operator associativity. In mathematics, exponentiation is usually assumed to be right-associative, i.e. $mathrm e^x^2$ means $mathrm e^(x^2)$, not $(mathrm e^x)^2$ (which would make it equal to $mathrm e^2x$).
– joriki
Jul 28 at 8:23
@joriki I got it.
– Le Anh Dung
Jul 28 at 8:27
add a comment |Â
These sums with more than $3$ summands are ambiguous unless we already know what you're trying to prove. You'll need to define what you mean by them. One well-defined way of stating the problem would be to ask whether, if sums of $m$ summands have been defined for all $mlt n$, the sum of $n$ summands on the left-hand side can equivalently be defined by any of the expressions on the right-hand side independent of the choice of $k$.
– joriki
Jul 28 at 8:07
@joriki I have edited to remove such ambiguity. Can you elaborate more on These sums with more than 3 summands are ambiguous unless we already know what you're trying to prove. In my common sense, $a_1+a_2+cdots+a_n=(cdots((a_1+a_2)+a_3)cdots)+a_n)$.
– Le Anh Dung
Jul 28 at 8:18
1
That's just one arbitrary order in which the operations can be formed. It could also mean $a_1+(a_2+cdots+(a_n-1+a_n)cdots)$. In programming languages, operators are called "left-associative" or "right-associative", respectively, according to which of these conventions apply to them; see operator associativity. In mathematics, exponentiation is usually assumed to be right-associative, i.e. $mathrm e^x^2$ means $mathrm e^(x^2)$, not $(mathrm e^x)^2$ (which would make it equal to $mathrm e^2x$).
– joriki
Jul 28 at 8:23
@joriki I got it.
– Le Anh Dung
Jul 28 at 8:27
These sums with more than $3$ summands are ambiguous unless we already know what you're trying to prove. You'll need to define what you mean by them. One well-defined way of stating the problem would be to ask whether, if sums of $m$ summands have been defined for all $mlt n$, the sum of $n$ summands on the left-hand side can equivalently be defined by any of the expressions on the right-hand side independent of the choice of $k$.
– joriki
Jul 28 at 8:07
These sums with more than $3$ summands are ambiguous unless we already know what you're trying to prove. You'll need to define what you mean by them. One well-defined way of stating the problem would be to ask whether, if sums of $m$ summands have been defined for all $mlt n$, the sum of $n$ summands on the left-hand side can equivalently be defined by any of the expressions on the right-hand side independent of the choice of $k$.
– joriki
Jul 28 at 8:07
@joriki I have edited to remove such ambiguity. Can you elaborate more on These sums with more than 3 summands are ambiguous unless we already know what you're trying to prove. In my common sense, $a_1+a_2+cdots+a_n=(cdots((a_1+a_2)+a_3)cdots)+a_n)$.
– Le Anh Dung
Jul 28 at 8:18
@joriki I have edited to remove such ambiguity. Can you elaborate more on These sums with more than 3 summands are ambiguous unless we already know what you're trying to prove. In my common sense, $a_1+a_2+cdots+a_n=(cdots((a_1+a_2)+a_3)cdots)+a_n)$.
– Le Anh Dung
Jul 28 at 8:18
1
1
That's just one arbitrary order in which the operations can be formed. It could also mean $a_1+(a_2+cdots+(a_n-1+a_n)cdots)$. In programming languages, operators are called "left-associative" or "right-associative", respectively, according to which of these conventions apply to them; see operator associativity. In mathematics, exponentiation is usually assumed to be right-associative, i.e. $mathrm e^x^2$ means $mathrm e^(x^2)$, not $(mathrm e^x)^2$ (which would make it equal to $mathrm e^2x$).
– joriki
Jul 28 at 8:23
That's just one arbitrary order in which the operations can be formed. It could also mean $a_1+(a_2+cdots+(a_n-1+a_n)cdots)$. In programming languages, operators are called "left-associative" or "right-associative", respectively, according to which of these conventions apply to them; see operator associativity. In mathematics, exponentiation is usually assumed to be right-associative, i.e. $mathrm e^x^2$ means $mathrm e^(x^2)$, not $(mathrm e^x)^2$ (which would make it equal to $mathrm e^2x$).
– joriki
Jul 28 at 8:23
@joriki I got it.
– Le Anh Dung
Jul 28 at 8:27
@joriki I got it.
– Le Anh Dung
Jul 28 at 8:27
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
HINT
One method is to do this in two steps.
I'll use your convention that + is left-associative:
$$a_1+a_2+⋯+a_n=(⋯((a_1+a_2)+a_3)⋯)+a_n) tag*$$
And of course we have the basic (ungeneralized) associativity of +:
$$(a+b)+c = a + (b + c) tag**$$
First, use induction on $n$ to prove:
Lemma
$$a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$$
Proof:
Base: Trivial
Step:
$$a_1+(a_2+a_3+...+a_k + a_k+1) overset(*)=$$
$$a_1+((((...((a_2+a_3)+...+a_k)+a_k+1) overset(**)=$$
$$(a_1+(((...((a_2+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$(a_1+(a_2+a_3+...+a_k))+a_k+1 overset(I.H)=$$
$$(a_1+a_2+a_3+...+a_k)+a_k+1) overset(*)=$$
$$(((...(((a_1+a_2)+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$a_1+a_2+a_3+...+a_k+a_k+1 $$
Then, use induction on $i$ (where during the step you'll use the above Lemma) to prove:
Theorem
$$a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$$
This Theorem is equivalent to what you are trying to prove .. it just reindexes things a bit so it lends itself better for an inductive proof
I'll leave working out the details to you, but with this set-up it's not hard.
Good luck!
answered Aug 1 at 17:19
Bram28
54.8k33881
Thank you so much @Bram28. I almost think that this question will sink into oblivion and no longer receive any answer. On the basis of your hints, I have formalized the proof and posted it as an answer below. Please have a check on it!
– Le Anh Dung
Aug 2 at 3:44
add a comment |Â
up vote
1
down vote
On the basis of @Bram28's answer, I present the proof here.
Lemma: $a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$
Proof: We will prove this by induction on $n$. It's clear that the theorem is trivially true for $n=1$. Assume that it is true for $n=k$, i.e. $a_1+(a_2+⋯+a_k)=a_1+a_2+⋯+a_k$.
We have $a_1+(a_2+⋯+a_k+a_k+1)$
$=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$ [By induction hypothesis]
$=a_1+a_2+(a_3+⋯+a_k+a_k+1)$ [By induction hypothesis]
$=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
$=(a_1+a_2)+a_3+⋯+a_k+a_k+1$ [By induction hypothesis]
$=a_1+a_2+a_3+⋯+a_k+a_k+1$.
Thus the theorem is true for $n=k+1$. This completes the proof.
Theorem: $a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$
Proof: We will prove this by induction on $i$. For $i=1$, the theorem becomes $a_1+a_2+⋯+a_n = (a_1+⋯+ a_n-1) + a_n$, and this is trivially true according to our convention. Assume that the theorem is true for $i=k$, i.e. $$a_1+⋯+ a_n-k + a_n-k+1 + ... + a_n = (a_1+⋯+ a_n-k) + (a_n-k+1 + ... + a_n)$$ For $i=k+1$, we have $a_1+⋯+ a_n-(k+1) + a_n-(k+1)+1 + ... + a_n$
$=a_1+⋯+ a_n-k-1 + a_n-k + ... + a_n$
$=(a_1+⋯+ a_n-k-1 + a_n-k) + (a_n-k+1+... + a_n)text [By induction hypothesis] $
$=(a_1+⋯+ a_n-k-1) + a_n-k + (a_n-k+1+... + a_n)$
$=(a_1+⋯+ a_n-k-1) + (a_n-k + (a_n-k+1+... + a_n))text [By Lemma] $
$=(a_1+⋯+ a_n-k-1) + (a_n-k + a_n-k+1+... + a_n)text [By Lemma] $
$=(a_1+⋯+ a_n-(k+1)) + (a_n-(k+1)+1+... + a_n)$
Thus the theorem is true for $i=k+1$. This completes the proof.
answered Aug 2 at 3:41
Le Anh Dung
740317
In the proof for the Lemma you use that $a_1+(a_2+⋯+a_k+a_k+1)=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$, i.e. that $a_2+⋯+a_k+a_k+1)=a_2+(a_3+⋯+(a_k+a_k+1)...)$, but I thought we used the convention that $a_2+⋯+a_k+a_k+1)=((...(a_2+a_3)+⋯+a_k)+a_k+1$
– Bram28
Aug 2 at 16:07
Hi @Bram28 since there are $k$ elements in the sequence $(a_imid 2leq ileq k+1)$, I applied induction hypothesis (in which the theorem is true for any sequence of size $n=k$) to get $a_2+⋯+a_k+a_k+1=a_2+(a_3+⋯+a_k+a_k+1)$.
– Le Anh Dung
Aug 4 at 7:27
Yes, I understand that, but my issue is with how you interpret $a_1+a_2+a_3+....+a_n$ (see joriki's comments). I thought you regarded the + as left-associative, and in my proof plan i treated the + as such when I specified the convention... but in this proof you're treating it as right-associative. ... but then it is trivial that $a_1+(a_2+a_3+...+a_n)=a_1+...+a_n$ for this would simply be true by that very convention!
– Bram28
Aug 4 at 10:58
@Bram28, did you mean this transformation is not correct? $a_1+(a_2+(a_3+⋯+a_k+a_k+1))=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
– Le Anh Dung
Aug 4 at 11:17
No, that transformation is fine, no matter if you treat the + as left or right associative.
– Bram28
Aug 4 at 12:30
 |Â
show 13 more comments
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
HINT
One method is to do this in two steps.
I'll use your convention that + is left-associative:
$$a_1+a_2+⋯+a_n=(⋯((a_1+a_2)+a_3)⋯)+a_n) tag*$$
And of course we have the basic (ungeneralized) associativity of +:
$$(a+b)+c = a + (b + c) tag**$$
First, use induction on $n$ to prove:
Lemma
$$a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$$
Proof:
Base: Trivial
Step:
$$a_1+(a_2+a_3+...+a_k + a_k+1) overset(*)=$$
$$a_1+((((...((a_2+a_3)+...+a_k)+a_k+1) overset(**)=$$
$$(a_1+(((...((a_2+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$(a_1+(a_2+a_3+...+a_k))+a_k+1 overset(I.H)=$$
$$(a_1+a_2+a_3+...+a_k)+a_k+1) overset(*)=$$
$$(((...(((a_1+a_2)+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$a_1+a_2+a_3+...+a_k+a_k+1 $$
Then, use induction on $i$ (where during the step you'll use the above Lemma) to prove:
Theorem
$$a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$$
This Theorem is equivalent to what you are trying to prove .. it just reindexes things a bit so it lends itself better for an inductive proof
I'll leave working out the details to you, but with this set-up it's not hard.
Good luck!
answered Aug 1 at 17:19
Bram28
54.8k33881
Thank you so much @Bram28. I almost think that this question will sink into oblivion and no longer receive any answer. On the basis of your hints, I have formalized the proof and posted it as an answer below. Please have a check on it!
– Le Anh Dung
Aug 2 at 3:44
add a comment |Â
up vote
1
down vote
accepted
HINT
One method is to do this in two steps.
I'll use your convention that + is left-associative:
$$a_1+a_2+⋯+a_n=(⋯((a_1+a_2)+a_3)⋯)+a_n) tag*$$
And of course we have the basic (ungeneralized) associativity of +:
$$(a+b)+c = a + (b + c) tag**$$
First, use induction on $n$ to prove:
Lemma
$$a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$$
Proof:
Base: Trivial
Step:
$$a_1+(a_2+a_3+...+a_k + a_k+1) overset(*)=$$
$$a_1+((((...((a_2+a_3)+...+a_k)+a_k+1) overset(**)=$$
$$(a_1+(((...((a_2+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$(a_1+(a_2+a_3+...+a_k))+a_k+1 overset(I.H)=$$
$$(a_1+a_2+a_3+...+a_k)+a_k+1) overset(*)=$$
$$(((...(((a_1+a_2)+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$a_1+a_2+a_3+...+a_k+a_k+1 $$
Then, use induction on $i$ (where during the step you'll use the above Lemma) to prove:
Theorem
$$a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$$
This Theorem is equivalent to what you are trying to prove .. it just reindexes things a bit so it lends itself better for an inductive proof
I'll leave working out the details to you, but with this set-up it's not hard.
Good luck!
answered Aug 1 at 17:19
Bram28
54.8k33881
Thank you so much @Bram28. I almost think that this question will sink into oblivion and no longer receive any answer. On the basis of your hints, I have formalized the proof and posted it as an answer below. Please have a check on it!
– Le Anh Dung
Aug 2 at 3:44
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
HINT
One method is to do this in two steps.
I'll use your convention that + is left-associative:
$$a_1+a_2+⋯+a_n=(⋯((a_1+a_2)+a_3)⋯)+a_n) tag*$$
And of course we have the basic (ungeneralized) associativity of +:
$$(a+b)+c = a + (b + c) tag**$$
First, use induction on $n$ to prove:
Lemma
$$a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$$
Proof:
Base: Trivial
Step:
$$a_1+(a_2+a_3+...+a_k + a_k+1) overset(*)=$$
$$a_1+((((...((a_2+a_3)+...+a_k)+a_k+1) overset(**)=$$
$$(a_1+(((...((a_2+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$(a_1+(a_2+a_3+...+a_k))+a_k+1 overset(I.H)=$$
$$(a_1+a_2+a_3+...+a_k)+a_k+1) overset(*)=$$
$$(((...(((a_1+a_2)+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$a_1+a_2+a_3+...+a_k+a_k+1 $$
Then, use induction on $i$ (where during the step you'll use the above Lemma) to prove:
Theorem
$$a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$$
This Theorem is equivalent to what you are trying to prove .. it just reindexes things a bit so it lends itself better for an inductive proof
I'll leave working out the details to you, but with this set-up it's not hard.
Good luck!
answered Aug 1 at 17:19
Bram28
54.8k33881
HINT
One method is to do this in two steps.
I'll use your convention that + is left-associative:
$$a_1+a_2+⋯+a_n=(⋯((a_1+a_2)+a_3)⋯)+a_n) tag*$$
And of course we have the basic (ungeneralized) associativity of +:
$$(a+b)+c = a + (b + c) tag**$$
First, use induction on $n$ to prove:
Lemma
$$a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$$
Proof:
Base: Trivial
Step:
$$a_1+(a_2+a_3+...+a_k + a_k+1) overset(*)=$$
$$a_1+((((...((a_2+a_3)+...+a_k)+a_k+1) overset(**)=$$
$$(a_1+(((...((a_2+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$(a_1+(a_2+a_3+...+a_k))+a_k+1 overset(I.H)=$$
$$(a_1+a_2+a_3+...+a_k)+a_k+1) overset(*)=$$
$$(((...(((a_1+a_2)+a_3)+...+a_k)+a_k+1 overset(*)=$$
$$a_1+a_2+a_3+...+a_k+a_k+1 $$
Then, use induction on $i$ (where during the step you'll use the above Lemma) to prove:
Theorem
$$a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$$
This Theorem is equivalent to what you are trying to prove .. it just reindexes things a bit so it lends itself better for an inductive proof
I'll leave working out the details to you, but with this set-up it's not hard.
Good luck!
answered Aug 1 at 17:19
Bram28
54.8k33881
edited Aug 4 at 17:26
answered Aug 1 at 17:19
Bram28
54.8k33881
answered Aug 1 at 17:19
Bram28
54.8k33881
answered Aug 1 at 17:19
Bram28
54.8k33881
54.8k33881
Thank you so much @Bram28. I almost think that this question will sink into oblivion and no longer receive any answer. On the basis of your hints, I have formalized the proof and posted it as an answer below. Please have a check on it!
– Le Anh Dung
Aug 2 at 3:44
add a comment |Â
Thank you so much @Bram28. I almost think that this question will sink into oblivion and no longer receive any answer. On the basis of your hints, I have formalized the proof and posted it as an answer below. Please have a check on it!
– Le Anh Dung
Aug 2 at 3:44
Thank you so much @Bram28. I almost think that this question will sink into oblivion and no longer receive any answer. On the basis of your hints, I have formalized the proof and posted it as an answer below. Please have a check on it!
– Le Anh Dung
Aug 2 at 3:44
Thank you so much @Bram28. I almost think that this question will sink into oblivion and no longer receive any answer. On the basis of your hints, I have formalized the proof and posted it as an answer below. Please have a check on it!
– Le Anh Dung
Aug 2 at 3:44
add a comment |Â
up vote
1
down vote
On the basis of @Bram28's answer, I present the proof here.
Lemma: $a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$
Proof: We will prove this by induction on $n$. It's clear that the theorem is trivially true for $n=1$. Assume that it is true for $n=k$, i.e. $a_1+(a_2+⋯+a_k)=a_1+a_2+⋯+a_k$.
We have $a_1+(a_2+⋯+a_k+a_k+1)$
$=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$ [By induction hypothesis]
$=a_1+a_2+(a_3+⋯+a_k+a_k+1)$ [By induction hypothesis]
$=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
$=(a_1+a_2)+a_3+⋯+a_k+a_k+1$ [By induction hypothesis]
$=a_1+a_2+a_3+⋯+a_k+a_k+1$.
Thus the theorem is true for $n=k+1$. This completes the proof.
Theorem: $a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$
Proof: We will prove this by induction on $i$. For $i=1$, the theorem becomes $a_1+a_2+⋯+a_n = (a_1+⋯+ a_n-1) + a_n$, and this is trivially true according to our convention. Assume that the theorem is true for $i=k$, i.e. $$a_1+⋯+ a_n-k + a_n-k+1 + ... + a_n = (a_1+⋯+ a_n-k) + (a_n-k+1 + ... + a_n)$$ For $i=k+1$, we have $a_1+⋯+ a_n-(k+1) + a_n-(k+1)+1 + ... + a_n$
$=a_1+⋯+ a_n-k-1 + a_n-k + ... + a_n$
$=(a_1+⋯+ a_n-k-1 + a_n-k) + (a_n-k+1+... + a_n)text [By induction hypothesis] $
$=(a_1+⋯+ a_n-k-1) + a_n-k + (a_n-k+1+... + a_n)$
$=(a_1+⋯+ a_n-k-1) + (a_n-k + (a_n-k+1+... + a_n))text [By Lemma] $
$=(a_1+⋯+ a_n-k-1) + (a_n-k + a_n-k+1+... + a_n)text [By Lemma] $
$=(a_1+⋯+ a_n-(k+1)) + (a_n-(k+1)+1+... + a_n)$
Thus the theorem is true for $i=k+1$. This completes the proof.
answered Aug 2 at 3:41
Le Anh Dung
740317
In the proof for the Lemma you use that $a_1+(a_2+⋯+a_k+a_k+1)=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$, i.e. that $a_2+⋯+a_k+a_k+1)=a_2+(a_3+⋯+(a_k+a_k+1)...)$, but I thought we used the convention that $a_2+⋯+a_k+a_k+1)=((...(a_2+a_3)+⋯+a_k)+a_k+1$
– Bram28
Aug 2 at 16:07
Hi @Bram28 since there are $k$ elements in the sequence $(a_imid 2leq ileq k+1)$, I applied induction hypothesis (in which the theorem is true for any sequence of size $n=k$) to get $a_2+⋯+a_k+a_k+1=a_2+(a_3+⋯+a_k+a_k+1)$.
– Le Anh Dung
Aug 4 at 7:27
Yes, I understand that, but my issue is with how you interpret $a_1+a_2+a_3+....+a_n$ (see joriki's comments). I thought you regarded the + as left-associative, and in my proof plan i treated the + as such when I specified the convention... but in this proof you're treating it as right-associative. ... but then it is trivial that $a_1+(a_2+a_3+...+a_n)=a_1+...+a_n$ for this would simply be true by that very convention!
– Bram28
Aug 4 at 10:58
@Bram28, did you mean this transformation is not correct? $a_1+(a_2+(a_3+⋯+a_k+a_k+1))=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
– Le Anh Dung
Aug 4 at 11:17
No, that transformation is fine, no matter if you treat the + as left or right associative.
– Bram28
Aug 4 at 12:30
 |Â
show 13 more comments
up vote
1
down vote
On the basis of @Bram28's answer, I present the proof here.
Lemma: $a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$
Proof: We will prove this by induction on $n$. It's clear that the theorem is trivially true for $n=1$. Assume that it is true for $n=k$, i.e. $a_1+(a_2+⋯+a_k)=a_1+a_2+⋯+a_k$.
We have $a_1+(a_2+⋯+a_k+a_k+1)$
$=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$ [By induction hypothesis]
$=a_1+a_2+(a_3+⋯+a_k+a_k+1)$ [By induction hypothesis]
$=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
$=(a_1+a_2)+a_3+⋯+a_k+a_k+1$ [By induction hypothesis]
$=a_1+a_2+a_3+⋯+a_k+a_k+1$.
Thus the theorem is true for $n=k+1$. This completes the proof.
Theorem: $a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$
Proof: We will prove this by induction on $i$. For $i=1$, the theorem becomes $a_1+a_2+⋯+a_n = (a_1+⋯+ a_n-1) + a_n$, and this is trivially true according to our convention. Assume that the theorem is true for $i=k$, i.e. $$a_1+⋯+ a_n-k + a_n-k+1 + ... + a_n = (a_1+⋯+ a_n-k) + (a_n-k+1 + ... + a_n)$$ For $i=k+1$, we have $a_1+⋯+ a_n-(k+1) + a_n-(k+1)+1 + ... + a_n$
$=a_1+⋯+ a_n-k-1 + a_n-k + ... + a_n$
$=(a_1+⋯+ a_n-k-1 + a_n-k) + (a_n-k+1+... + a_n)text [By induction hypothesis] $
$=(a_1+⋯+ a_n-k-1) + a_n-k + (a_n-k+1+... + a_n)$
$=(a_1+⋯+ a_n-k-1) + (a_n-k + (a_n-k+1+... + a_n))text [By Lemma] $
$=(a_1+⋯+ a_n-k-1) + (a_n-k + a_n-k+1+... + a_n)text [By Lemma] $
$=(a_1+⋯+ a_n-(k+1)) + (a_n-(k+1)+1+... + a_n)$
Thus the theorem is true for $i=k+1$. This completes the proof.
answered Aug 2 at 3:41
Le Anh Dung
740317
In the proof for the Lemma you use that $a_1+(a_2+⋯+a_k+a_k+1)=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$, i.e. that $a_2+⋯+a_k+a_k+1)=a_2+(a_3+⋯+(a_k+a_k+1)...)$, but I thought we used the convention that $a_2+⋯+a_k+a_k+1)=((...(a_2+a_3)+⋯+a_k)+a_k+1$
– Bram28
Aug 2 at 16:07
Hi @Bram28 since there are $k$ elements in the sequence $(a_imid 2leq ileq k+1)$, I applied induction hypothesis (in which the theorem is true for any sequence of size $n=k$) to get $a_2+⋯+a_k+a_k+1=a_2+(a_3+⋯+a_k+a_k+1)$.
– Le Anh Dung
Aug 4 at 7:27
Yes, I understand that, but my issue is with how you interpret $a_1+a_2+a_3+....+a_n$ (see joriki's comments). I thought you regarded the + as left-associative, and in my proof plan i treated the + as such when I specified the convention... but in this proof you're treating it as right-associative. ... but then it is trivial that $a_1+(a_2+a_3+...+a_n)=a_1+...+a_n$ for this would simply be true by that very convention!
– Bram28
Aug 4 at 10:58
@Bram28, did you mean this transformation is not correct? $a_1+(a_2+(a_3+⋯+a_k+a_k+1))=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
– Le Anh Dung
Aug 4 at 11:17
No, that transformation is fine, no matter if you treat the + as left or right associative.
– Bram28
Aug 4 at 12:30
 |Â
show 13 more comments
up vote
1
down vote
up vote
1
down vote
On the basis of @Bram28's answer, I present the proof here.
Lemma: $a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$
Proof: We will prove this by induction on $n$. It's clear that the theorem is trivially true for $n=1$. Assume that it is true for $n=k$, i.e. $a_1+(a_2+⋯+a_k)=a_1+a_2+⋯+a_k$.
We have $a_1+(a_2+⋯+a_k+a_k+1)$
$=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$ [By induction hypothesis]
$=a_1+a_2+(a_3+⋯+a_k+a_k+1)$ [By induction hypothesis]
$=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
$=(a_1+a_2)+a_3+⋯+a_k+a_k+1$ [By induction hypothesis]
$=a_1+a_2+a_3+⋯+a_k+a_k+1$.
Thus the theorem is true for $n=k+1$. This completes the proof.
Theorem: $a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$
Proof: We will prove this by induction on $i$. For $i=1$, the theorem becomes $a_1+a_2+⋯+a_n = (a_1+⋯+ a_n-1) + a_n$, and this is trivially true according to our convention. Assume that the theorem is true for $i=k$, i.e. $$a_1+⋯+ a_n-k + a_n-k+1 + ... + a_n = (a_1+⋯+ a_n-k) + (a_n-k+1 + ... + a_n)$$ For $i=k+1$, we have $a_1+⋯+ a_n-(k+1) + a_n-(k+1)+1 + ... + a_n$
$=a_1+⋯+ a_n-k-1 + a_n-k + ... + a_n$
$=(a_1+⋯+ a_n-k-1 + a_n-k) + (a_n-k+1+... + a_n)text [By induction hypothesis] $
$=(a_1+⋯+ a_n-k-1) + a_n-k + (a_n-k+1+... + a_n)$
$=(a_1+⋯+ a_n-k-1) + (a_n-k + (a_n-k+1+... + a_n))text [By Lemma] $
$=(a_1+⋯+ a_n-k-1) + (a_n-k + a_n-k+1+... + a_n)text [By Lemma] $
$=(a_1+⋯+ a_n-(k+1)) + (a_n-(k+1)+1+... + a_n)$
Thus the theorem is true for $i=k+1$. This completes the proof.
answered Aug 2 at 3:41
Le Anh Dung
740317
On the basis of @Bram28's answer, I present the proof here.
Lemma: $a_1+(a_2+⋯+a_n)=a_1+a_2+⋯+a_n$
Proof: We will prove this by induction on $n$. It's clear that the theorem is trivially true for $n=1$. Assume that it is true for $n=k$, i.e. $a_1+(a_2+⋯+a_k)=a_1+a_2+⋯+a_k$.
We have $a_1+(a_2+⋯+a_k+a_k+1)$
$=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$ [By induction hypothesis]
$=a_1+a_2+(a_3+⋯+a_k+a_k+1)$ [By induction hypothesis]
$=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
$=(a_1+a_2)+a_3+⋯+a_k+a_k+1$ [By induction hypothesis]
$=a_1+a_2+a_3+⋯+a_k+a_k+1$.
Thus the theorem is true for $n=k+1$. This completes the proof.
Theorem: $a_1+⋯+ a_n-i + a_n-i+1 + ... + a_n = (a_1+⋯+ a_n-i) + (a_n-i+1 + ... + a_n)$
Proof: We will prove this by induction on $i$. For $i=1$, the theorem becomes $a_1+a_2+⋯+a_n = (a_1+⋯+ a_n-1) + a_n$, and this is trivially true according to our convention. Assume that the theorem is true for $i=k$, i.e. $$a_1+⋯+ a_n-k + a_n-k+1 + ... + a_n = (a_1+⋯+ a_n-k) + (a_n-k+1 + ... + a_n)$$ For $i=k+1$, we have $a_1+⋯+ a_n-(k+1) + a_n-(k+1)+1 + ... + a_n$
$=a_1+⋯+ a_n-k-1 + a_n-k + ... + a_n$
$=(a_1+⋯+ a_n-k-1 + a_n-k) + (a_n-k+1+... + a_n)text [By induction hypothesis] $
$=(a_1+⋯+ a_n-k-1) + a_n-k + (a_n-k+1+... + a_n)$
$=(a_1+⋯+ a_n-k-1) + (a_n-k + (a_n-k+1+... + a_n))text [By Lemma] $
$=(a_1+⋯+ a_n-k-1) + (a_n-k + a_n-k+1+... + a_n)text [By Lemma] $
$=(a_1+⋯+ a_n-(k+1)) + (a_n-(k+1)+1+... + a_n)$
Thus the theorem is true for $i=k+1$. This completes the proof.
answered Aug 2 at 3:41
Le Anh Dung
740317
edited Aug 5 at 3:43
answered Aug 2 at 3:41
Le Anh Dung
740317
answered Aug 2 at 3:41
Le Anh Dung
740317
answered Aug 2 at 3:41
Le Anh Dung
740317
740317
In the proof for the Lemma you use that $a_1+(a_2+⋯+a_k+a_k+1)=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$, i.e. that $a_2+⋯+a_k+a_k+1)=a_2+(a_3+⋯+(a_k+a_k+1)...)$, but I thought we used the convention that $a_2+⋯+a_k+a_k+1)=((...(a_2+a_3)+⋯+a_k)+a_k+1$
– Bram28
Aug 2 at 16:07
Hi @Bram28 since there are $k$ elements in the sequence $(a_imid 2leq ileq k+1)$, I applied induction hypothesis (in which the theorem is true for any sequence of size $n=k$) to get $a_2+⋯+a_k+a_k+1=a_2+(a_3+⋯+a_k+a_k+1)$.
– Le Anh Dung
Aug 4 at 7:27
Yes, I understand that, but my issue is with how you interpret $a_1+a_2+a_3+....+a_n$ (see joriki's comments). I thought you regarded the + as left-associative, and in my proof plan i treated the + as such when I specified the convention... but in this proof you're treating it as right-associative. ... but then it is trivial that $a_1+(a_2+a_3+...+a_n)=a_1+...+a_n$ for this would simply be true by that very convention!
– Bram28
Aug 4 at 10:58
@Bram28, did you mean this transformation is not correct? $a_1+(a_2+(a_3+⋯+a_k+a_k+1))=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
– Le Anh Dung
Aug 4 at 11:17
No, that transformation is fine, no matter if you treat the + as left or right associative.
– Bram28
Aug 4 at 12:30
 |Â
show 13 more comments
In the proof for the Lemma you use that $a_1+(a_2+⋯+a_k+a_k+1)=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$, i.e. that $a_2+⋯+a_k+a_k+1)=a_2+(a_3+⋯+(a_k+a_k+1)...)$, but I thought we used the convention that $a_2+⋯+a_k+a_k+1)=((...(a_2+a_3)+⋯+a_k)+a_k+1$
– Bram28
Aug 2 at 16:07
Hi @Bram28 since there are $k$ elements in the sequence $(a_imid 2leq ileq k+1)$, I applied induction hypothesis (in which the theorem is true for any sequence of size $n=k$) to get $a_2+⋯+a_k+a_k+1=a_2+(a_3+⋯+a_k+a_k+1)$.
– Le Anh Dung
Aug 4 at 7:27
Yes, I understand that, but my issue is with how you interpret $a_1+a_2+a_3+....+a_n$ (see joriki's comments). I thought you regarded the + as left-associative, and in my proof plan i treated the + as such when I specified the convention... but in this proof you're treating it as right-associative. ... but then it is trivial that $a_1+(a_2+a_3+...+a_n)=a_1+...+a_n$ for this would simply be true by that very convention!
– Bram28
Aug 4 at 10:58
@Bram28, did you mean this transformation is not correct? $a_1+(a_2+(a_3+⋯+a_k+a_k+1))=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
– Le Anh Dung
Aug 4 at 11:17
No, that transformation is fine, no matter if you treat the + as left or right associative.
– Bram28
Aug 4 at 12:30
In the proof for the Lemma you use that $a_1+(a_2+⋯+a_k+a_k+1)=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$, i.e. that $a_2+⋯+a_k+a_k+1)=a_2+(a_3+⋯+(a_k+a_k+1)...)$, but I thought we used the convention that $a_2+⋯+a_k+a_k+1)=((...(a_2+a_3)+⋯+a_k)+a_k+1$
– Bram28
Aug 2 at 16:07
In the proof for the Lemma you use that $a_1+(a_2+⋯+a_k+a_k+1)=a_1+(a_2+(a_3+⋯+a_k+a_k+1))$, i.e. that $a_2+⋯+a_k+a_k+1)=a_2+(a_3+⋯+(a_k+a_k+1)...)$, but I thought we used the convention that $a_2+⋯+a_k+a_k+1)=((...(a_2+a_3)+⋯+a_k)+a_k+1$
– Bram28
Aug 2 at 16:07
Hi @Bram28 since there are $k$ elements in the sequence $(a_imid 2leq ileq k+1)$, I applied induction hypothesis (in which the theorem is true for any sequence of size $n=k$) to get $a_2+⋯+a_k+a_k+1=a_2+(a_3+⋯+a_k+a_k+1)$.
– Le Anh Dung
Aug 4 at 7:27
Hi @Bram28 since there are $k$ elements in the sequence $(a_imid 2leq ileq k+1)$, I applied induction hypothesis (in which the theorem is true for any sequence of size $n=k$) to get $a_2+⋯+a_k+a_k+1=a_2+(a_3+⋯+a_k+a_k+1)$.
– Le Anh Dung
Aug 4 at 7:27
Yes, I understand that, but my issue is with how you interpret $a_1+a_2+a_3+....+a_n$ (see joriki's comments). I thought you regarded the + as left-associative, and in my proof plan i treated the + as such when I specified the convention... but in this proof you're treating it as right-associative. ... but then it is trivial that $a_1+(a_2+a_3+...+a_n)=a_1+...+a_n$ for this would simply be true by that very convention!
– Bram28
Aug 4 at 10:58
Yes, I understand that, but my issue is with how you interpret $a_1+a_2+a_3+....+a_n$ (see joriki's comments). I thought you regarded the + as left-associative, and in my proof plan i treated the + as such when I specified the convention... but in this proof you're treating it as right-associative. ... but then it is trivial that $a_1+(a_2+a_3+...+a_n)=a_1+...+a_n$ for this would simply be true by that very convention!
– Bram28
Aug 4 at 10:58
@Bram28, did you mean this transformation is not correct? $a_1+(a_2+(a_3+⋯+a_k+a_k+1))=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
– Le Anh Dung
Aug 4 at 11:17
@Bram28, did you mean this transformation is not correct? $a_1+(a_2+(a_3+⋯+a_k+a_k+1))=(a_1+a_2)+(a_3+⋯+a_k+a_k+1)$
– Le Anh Dung
Aug 4 at 11:17
No, that transformation is fine, no matter if you treat the + as left or right associative.
– Bram28
Aug 4 at 12:30
No, that transformation is fine, no matter if you treat the + as left or right associative.
– Bram28
Aug 4 at 12:30
 |Â
show 13 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865073%2fhow-to-prove-the-generalized-associative-law-for-addition-on-mathbb-n%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
These sums with more than $3$ summands are ambiguous unless we already know what you're trying to prove. You'll need to define what you mean by them. One well-defined way of stating the problem would be to ask whether, if sums of $m$ summands have been defined for all $mlt n$, the sum of $n$ summands on the left-hand side can equivalently be defined by any of the expressions on the right-hand side independent of the choice of $k$.
– joriki
Jul 28 at 8:07
@joriki I have edited to remove such ambiguity. Can you elaborate more on These sums with more than 3 summands are ambiguous unless we already know what you're trying to prove. In my common sense, $a_1+a_2+cdots+a_n=(cdots((a_1+a_2)+a_3)cdots)+a_n)$.
– Le Anh Dung
Jul 28 at 8:18
1
That's just one arbitrary order in which the operations can be formed. It could also mean $a_1+(a_2+cdots+(a_n-1+a_n)cdots)$. In programming languages, operators are called "left-associative" or "right-associative", respectively, according to which of these conventions apply to them; see operator associativity. In mathematics, exponentiation is usually assumed to be right-associative, i.e. $mathrm e^x^2$ means $mathrm e^(x^2)$, not $(mathrm e^x)^2$ (which would make it equal to $mathrm e^2x$).
– joriki
Jul 28 at 8:23
@joriki I got it.
– Le Anh Dung
Jul 28 at 8:27