Mixing
How to justify the definition of summation $s_n=sum_i=1^n a_i=a_1+cdots+a_n$?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I read https://www.wikiwand.com/en/Summation#/Formal_definition and found that they define summation via recursion, so I decided to formalize the proof that that this definition is actually valid. I've two questions:
Does my proof contain any error?
Are there other simple ways to define summation?
Thank you so much!
Suppose that $(a_1,cdots,a_n)$ is a finite sequence in $mathbb N$. Show that 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$.
My attempt:
We define mapping $f$ as follows: $f: mathbb Ntimesmathbb Ntomathbb Ntimesmathbb N: (i,a)mapstobegincases
(i+1,a+a_i+1)&textif i<n\
(i+1,a)&textif igeq n
endcases$
By recursion theorem, there is a unique sequence $(p_imid iinmathbb N)$ such that $p_0=(1,a_1)$ and $p_i+1=f(p_i)$. Let $pi:mathbb Ntimesmathbb Ntomathbb N$ be the projection to the second co-ordinate i.e. $pi(i,a)=a$. Let $s_i=pi(p_i)$ for all $1leq ileq n$, then $(s_imid 1leq ileq n)$ is the required sequence. It's clear from the definition of $s_i$ that $s_i+1=s_i+a_i+1$ for all $1leq i<n$.
proof-verification recurrence-relations definition
asked Jul 24 at 3:41
Le Anh Dung
767318
add a comment |Â
up vote
0
down vote
favorite
I read https://www.wikiwand.com/en/Summation#/Formal_definition and found that they define summation via recursion, so I decided to formalize the proof that that this definition is actually valid. I've two questions:
Does my proof contain any error?
Are there other simple ways to define summation?
Thank you so much!
Suppose that $(a_1,cdots,a_n)$ is a finite sequence in $mathbb N$. Show that 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$.
My attempt:
We define mapping $f$ as follows: $f: mathbb Ntimesmathbb Ntomathbb Ntimesmathbb N: (i,a)mapstobegincases
(i+1,a+a_i+1)&textif i<n\
(i+1,a)&textif igeq n
endcases$
By recursion theorem, there is a unique sequence $(p_imid iinmathbb N)$ such that $p_0=(1,a_1)$ and $p_i+1=f(p_i)$. Let $pi:mathbb Ntimesmathbb Ntomathbb N$ be the projection to the second co-ordinate i.e. $pi(i,a)=a$. Let $s_i=pi(p_i)$ for all $1leq ileq n$, then $(s_imid 1leq ileq n)$ is the required sequence. It's clear from the definition of $s_i$ that $s_i+1=s_i+a_i+1$ for all $1leq i<n$.
proof-verification recurrence-relations definition
asked Jul 24 at 3:41
Le Anh Dung
767318
Your definition is incorrect because you use $s_i+1$ 'directly' in your definition before you've shown that it exists. You're loosely on the right track, but you need to be very careful about it.
– Steven Stadnicki
Jul 24 at 3:58
@StevenStadnicki, I has appealed to Recursion Theorem in my poof to show the existence of $s_i+1$.
– Le Anh Dung
Jul 24 at 4:00
The point is that $s_i+1$ doesn't exist as an entity that you can use in the 'definition' of $f$ that you write; $f$ has to be 'internally' written. Do you have a typo, perhaps, in the $ilt n$ case of the mapping?
– Steven Stadnicki
Jul 24 at 4:04
1
$s_1=a_1$ and $s_i+1$=$s_i$+$a_i+1$ for all 1≤ i <n is a simple way to define summation.
– Steve B
Jul 24 at 4:33
@StevenStadnicki Thank you so much. It's actually a typo :). It should be $(i+1,a+a_i+1)$ rather than $(i+1,a+s_i+1)$. I've fixed this typo. Please have a check on my proof again!
– Le Anh Dung
Jul 24 at 7:40
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I read https://www.wikiwand.com/en/Summation#/Formal_definition and found that they define summation via recursion, so I decided to formalize the proof that that this definition is actually valid. I've two questions:
Does my proof contain any error?
Are there other simple ways to define summation?
Thank you so much!
Suppose that $(a_1,cdots,a_n)$ is a finite sequence in $mathbb N$. Show that 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$.
My attempt:
We define mapping $f$ as follows: $f: mathbb Ntimesmathbb Ntomathbb Ntimesmathbb N: (i,a)mapstobegincases
(i+1,a+a_i+1)&textif i<n\
(i+1,a)&textif igeq n
endcases$
By recursion theorem, there is a unique sequence $(p_imid iinmathbb N)$ such that $p_0=(1,a_1)$ and $p_i+1=f(p_i)$. Let $pi:mathbb Ntimesmathbb Ntomathbb N$ be the projection to the second co-ordinate i.e. $pi(i,a)=a$. Let $s_i=pi(p_i)$ for all $1leq ileq n$, then $(s_imid 1leq ileq n)$ is the required sequence. It's clear from the definition of $s_i$ that $s_i+1=s_i+a_i+1$ for all $1leq i<n$.
proof-verification recurrence-relations definition
asked Jul 24 at 3:41
Le Anh Dung
767318
I read https://www.wikiwand.com/en/Summation#/Formal_definition and found that they define summation via recursion, so I decided to formalize the proof that that this definition is actually valid. I've two questions:
Does my proof contain any error?
Are there other simple ways to define summation?
Thank you so much!
Suppose that $(a_1,cdots,a_n)$ is a finite sequence in $mathbb N$. Show that 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$.
My attempt:
We define mapping $f$ as follows: $f: mathbb Ntimesmathbb Ntomathbb Ntimesmathbb N: (i,a)mapstobegincases
(i+1,a+a_i+1)&textif i<n\
(i+1,a)&textif igeq n
endcases$
By recursion theorem, there is a unique sequence $(p_imid iinmathbb N)$ such that $p_0=(1,a_1)$ and $p_i+1=f(p_i)$. Let $pi:mathbb Ntimesmathbb Ntomathbb N$ be the projection to the second co-ordinate i.e. $pi(i,a)=a$. Let $s_i=pi(p_i)$ for all $1leq ileq n$, then $(s_imid 1leq ileq n)$ is the required sequence. It's clear from the definition of $s_i$ that $s_i+1=s_i+a_i+1$ for all $1leq i<n$.
proof-verification recurrence-relations definition
asked Jul 24 at 3:41
Le Anh Dung
767318
edited Jul 25 at 2:26
asked Jul 24 at 3:41
Le Anh Dung
767318
asked Jul 24 at 3:41
Le Anh Dung
767318
asked Jul 24 at 3:41
Le Anh Dung
767318
767318
Your definition is incorrect because you use $s_i+1$ 'directly' in your definition before you've shown that it exists. You're loosely on the right track, but you need to be very careful about it.
– Steven Stadnicki
Jul 24 at 3:58
@StevenStadnicki, I has appealed to Recursion Theorem in my poof to show the existence of $s_i+1$.
– Le Anh Dung
Jul 24 at 4:00
The point is that $s_i+1$ doesn't exist as an entity that you can use in the 'definition' of $f$ that you write; $f$ has to be 'internally' written. Do you have a typo, perhaps, in the $ilt n$ case of the mapping?
– Steven Stadnicki
Jul 24 at 4:04
1
$s_1=a_1$ and $s_i+1$=$s_i$+$a_i+1$ for all 1≤ i <n is a simple way to define summation.
– Steve B
Jul 24 at 4:33
@StevenStadnicki Thank you so much. It's actually a typo :). It should be $(i+1,a+a_i+1)$ rather than $(i+1,a+s_i+1)$. I've fixed this typo. Please have a check on my proof again!
– Le Anh Dung
Jul 24 at 7:40
add a comment |Â
Your definition is incorrect because you use $s_i+1$ 'directly' in your definition before you've shown that it exists. You're loosely on the right track, but you need to be very careful about it.
– Steven Stadnicki
Jul 24 at 3:58
@StevenStadnicki, I has appealed to Recursion Theorem in my poof to show the existence of $s_i+1$.
– Le Anh Dung
Jul 24 at 4:00
The point is that $s_i+1$ doesn't exist as an entity that you can use in the 'definition' of $f$ that you write; $f$ has to be 'internally' written. Do you have a typo, perhaps, in the $ilt n$ case of the mapping?
– Steven Stadnicki
Jul 24 at 4:04
1
$s_1=a_1$ and $s_i+1$=$s_i$+$a_i+1$ for all 1≤ i <n is a simple way to define summation.
– Steve B
Jul 24 at 4:33
@StevenStadnicki Thank you so much. It's actually a typo :). It should be $(i+1,a+a_i+1)$ rather than $(i+1,a+s_i+1)$. I've fixed this typo. Please have a check on my proof again!
– Le Anh Dung
Jul 24 at 7:40
Your definition is incorrect because you use $s_i+1$ 'directly' in your definition before you've shown that it exists. You're loosely on the right track, but you need to be very careful about it.
– Steven Stadnicki
Jul 24 at 3:58
Your definition is incorrect because you use $s_i+1$ 'directly' in your definition before you've shown that it exists. You're loosely on the right track, but you need to be very careful about it.
– Steven Stadnicki
Jul 24 at 3:58
@StevenStadnicki, I has appealed to Recursion Theorem in my poof to show the existence of $s_i+1$.
– Le Anh Dung
Jul 24 at 4:00
@StevenStadnicki, I has appealed to Recursion Theorem in my poof to show the existence of $s_i+1$.
– Le Anh Dung
Jul 24 at 4:00
The point is that $s_i+1$ doesn't exist as an entity that you can use in the 'definition' of $f$ that you write; $f$ has to be 'internally' written. Do you have a typo, perhaps, in the $ilt n$ case of the mapping?
– Steven Stadnicki
Jul 24 at 4:04
The point is that $s_i+1$ doesn't exist as an entity that you can use in the 'definition' of $f$ that you write; $f$ has to be 'internally' written. Do you have a typo, perhaps, in the $ilt n$ case of the mapping?
– Steven Stadnicki
Jul 24 at 4:04
1
1
$s_1=a_1$ and $s_i+1$=$s_i$+$a_i+1$ for all 1≤ i <n is a simple way to define summation.
– Steve B
Jul 24 at 4:33
$s_1=a_1$ and $s_i+1$=$s_i$+$a_i+1$ for all 1≤ i <n is a simple way to define summation.
– Steve B
Jul 24 at 4:33
@StevenStadnicki Thank you so much. It's actually a typo :). It should be $(i+1,a+a_i+1)$ rather than $(i+1,a+s_i+1)$. I've fixed this typo. Please have a check on my proof again!
– Le Anh Dung
Jul 24 at 7:40
@StevenStadnicki Thank you so much. It's actually a typo :). It should be $(i+1,a+a_i+1)$ rather than $(i+1,a+s_i+1)$. I've fixed this typo. Please have a check on my proof again!
– Le Anh Dung
Jul 24 at 7:40
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
There are still a few issues with this proof. Most notably, you're being a bit sloppy with the definitions of all of your 'entities' around the proof; for instance, you say that "$s_i+1=f(s_i)$," but $f$ is defined on $mathbbNtimesmathbbN$, and it's unclear whether individual elements $s_i$ are members of $mathbbN$ or $mathbbNtimes N$; at one point you say $s_0=langle 1,a_1rangle$ which suggests that each $s_i$ is a member of $mathbbNtimesmathbbN$, but then later you say $s_i+1=s_i+a_i+1$, which suggests that the $s_i$ are members of $mathbbN$.
Instead, I suggest writing it in this form:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that for all $ninmathbbN$, $s(n)=sum_i=1^na(i)$.
Now it's clear exactly what the domain of the quantities being worked with is, and you can be more precise in your usage of the recursion theorem: in particular, we can rewrite the statement above as follows:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that $s(1)=a(1)$ and such that for all $ninmathbbN$, $s(n+1)=s(n)+a(n+1)$.
And now it should be clear that we can take the function $f(i,m): mathbbNtimesmathbbNmapstomathbbN$ given by $f(i,m)=m+a(i)$ and apply the recursion theorem to $f()$. (Note that there's no need for cases in the definition of $f()$; the 'base case' is essentially passed directly into the recursion theorem.)
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
Please have a look at my fixed proof!
– Le Anh Dung
Jul 26 at 0:12
1
I believe the current version is correct; using the index $i$ in the mapping of the function $f$ isn't strictly necessary depending on which version of the recursion theorem you use, but neither does it really hurt anything.
– Steven Stadnicki
Jul 26 at 15:39
Thank you so much for your dedicated help!
– Le Anh Dung
Jul 26 at 16:58
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
There are still a few issues with this proof. Most notably, you're being a bit sloppy with the definitions of all of your 'entities' around the proof; for instance, you say that "$s_i+1=f(s_i)$," but $f$ is defined on $mathbbNtimesmathbbN$, and it's unclear whether individual elements $s_i$ are members of $mathbbN$ or $mathbbNtimes N$; at one point you say $s_0=langle 1,a_1rangle$ which suggests that each $s_i$ is a member of $mathbbNtimesmathbbN$, but then later you say $s_i+1=s_i+a_i+1$, which suggests that the $s_i$ are members of $mathbbN$.
Instead, I suggest writing it in this form:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that for all $ninmathbbN$, $s(n)=sum_i=1^na(i)$.
Now it's clear exactly what the domain of the quantities being worked with is, and you can be more precise in your usage of the recursion theorem: in particular, we can rewrite the statement above as follows:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that $s(1)=a(1)$ and such that for all $ninmathbbN$, $s(n+1)=s(n)+a(n+1)$.
And now it should be clear that we can take the function $f(i,m): mathbbNtimesmathbbNmapstomathbbN$ given by $f(i,m)=m+a(i)$ and apply the recursion theorem to $f()$. (Note that there's no need for cases in the definition of $f()$; the 'base case' is essentially passed directly into the recursion theorem.)
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
Please have a look at my fixed proof!
– Le Anh Dung
Jul 26 at 0:12
1
I believe the current version is correct; using the index $i$ in the mapping of the function $f$ isn't strictly necessary depending on which version of the recursion theorem you use, but neither does it really hurt anything.
– Steven Stadnicki
Jul 26 at 15:39
Thank you so much for your dedicated help!
– Le Anh Dung
Jul 26 at 16:58
add a comment |Â
up vote
0
down vote
accepted
There are still a few issues with this proof. Most notably, you're being a bit sloppy with the definitions of all of your 'entities' around the proof; for instance, you say that "$s_i+1=f(s_i)$," but $f$ is defined on $mathbbNtimesmathbbN$, and it's unclear whether individual elements $s_i$ are members of $mathbbN$ or $mathbbNtimes N$; at one point you say $s_0=langle 1,a_1rangle$ which suggests that each $s_i$ is a member of $mathbbNtimesmathbbN$, but then later you say $s_i+1=s_i+a_i+1$, which suggests that the $s_i$ are members of $mathbbN$.
Instead, I suggest writing it in this form:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that for all $ninmathbbN$, $s(n)=sum_i=1^na(i)$.
Now it's clear exactly what the domain of the quantities being worked with is, and you can be more precise in your usage of the recursion theorem: in particular, we can rewrite the statement above as follows:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that $s(1)=a(1)$ and such that for all $ninmathbbN$, $s(n+1)=s(n)+a(n+1)$.
And now it should be clear that we can take the function $f(i,m): mathbbNtimesmathbbNmapstomathbbN$ given by $f(i,m)=m+a(i)$ and apply the recursion theorem to $f()$. (Note that there's no need for cases in the definition of $f()$; the 'base case' is essentially passed directly into the recursion theorem.)
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
Please have a look at my fixed proof!
– Le Anh Dung
Jul 26 at 0:12
1
I believe the current version is correct; using the index $i$ in the mapping of the function $f$ isn't strictly necessary depending on which version of the recursion theorem you use, but neither does it really hurt anything.
– Steven Stadnicki
Jul 26 at 15:39
Thank you so much for your dedicated help!
– Le Anh Dung
Jul 26 at 16:58
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
There are still a few issues with this proof. Most notably, you're being a bit sloppy with the definitions of all of your 'entities' around the proof; for instance, you say that "$s_i+1=f(s_i)$," but $f$ is defined on $mathbbNtimesmathbbN$, and it's unclear whether individual elements $s_i$ are members of $mathbbN$ or $mathbbNtimes N$; at one point you say $s_0=langle 1,a_1rangle$ which suggests that each $s_i$ is a member of $mathbbNtimesmathbbN$, but then later you say $s_i+1=s_i+a_i+1$, which suggests that the $s_i$ are members of $mathbbN$.
Instead, I suggest writing it in this form:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that for all $ninmathbbN$, $s(n)=sum_i=1^na(i)$.
Now it's clear exactly what the domain of the quantities being worked with is, and you can be more precise in your usage of the recursion theorem: in particular, we can rewrite the statement above as follows:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that $s(1)=a(1)$ and such that for all $ninmathbbN$, $s(n+1)=s(n)+a(n+1)$.
And now it should be clear that we can take the function $f(i,m): mathbbNtimesmathbbNmapstomathbbN$ given by $f(i,m)=m+a(i)$ and apply the recursion theorem to $f()$. (Note that there's no need for cases in the definition of $f()$; the 'base case' is essentially passed directly into the recursion theorem.)
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
There are still a few issues with this proof. Most notably, you're being a bit sloppy with the definitions of all of your 'entities' around the proof; for instance, you say that "$s_i+1=f(s_i)$," but $f$ is defined on $mathbbNtimesmathbbN$, and it's unclear whether individual elements $s_i$ are members of $mathbbN$ or $mathbbNtimes N$; at one point you say $s_0=langle 1,a_1rangle$ which suggests that each $s_i$ is a member of $mathbbNtimesmathbbN$, but then later you say $s_i+1=s_i+a_i+1$, which suggests that the $s_i$ are members of $mathbbN$.
Instead, I suggest writing it in this form:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that for all $ninmathbbN$, $s(n)=sum_i=1^na(i)$.
Now it's clear exactly what the domain of the quantities being worked with is, and you can be more precise in your usage of the recursion theorem: in particular, we can rewrite the statement above as follows:
For each function $a():mathbbNmapstomathbbN$, there is a function $s():mathbbNmapstomathbbN$ such that $s(1)=a(1)$ and such that for all $ninmathbbN$, $s(n+1)=s(n)+a(n+1)$.
And now it should be clear that we can take the function $f(i,m): mathbbNtimesmathbbNmapstomathbbN$ given by $f(i,m)=m+a(i)$ and apply the recursion theorem to $f()$. (Note that there's no need for cases in the definition of $f()$; the 'base case' is essentially passed directly into the recursion theorem.)
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
answered Jul 24 at 17:10
Steven Stadnicki
40.1k765119
40.1k765119
Please have a look at my fixed proof!
– Le Anh Dung
Jul 26 at 0:12
1
I believe the current version is correct; using the index $i$ in the mapping of the function $f$ isn't strictly necessary depending on which version of the recursion theorem you use, but neither does it really hurt anything.
– Steven Stadnicki
Jul 26 at 15:39
Thank you so much for your dedicated help!
– Le Anh Dung
Jul 26 at 16:58
add a comment |Â
Please have a look at my fixed proof!
– Le Anh Dung
Jul 26 at 0:12
1
I believe the current version is correct; using the index $i$ in the mapping of the function $f$ isn't strictly necessary depending on which version of the recursion theorem you use, but neither does it really hurt anything.
– Steven Stadnicki
Jul 26 at 15:39
Thank you so much for your dedicated help!
– Le Anh Dung
Jul 26 at 16:58
Please have a look at my fixed proof!
– Le Anh Dung
Jul 26 at 0:12
Please have a look at my fixed proof!
– Le Anh Dung
Jul 26 at 0:12
1
1
I believe the current version is correct; using the index $i$ in the mapping of the function $f$ isn't strictly necessary depending on which version of the recursion theorem you use, but neither does it really hurt anything.
– Steven Stadnicki
Jul 26 at 15:39
I believe the current version is correct; using the index $i$ in the mapping of the function $f$ isn't strictly necessary depending on which version of the recursion theorem you use, but neither does it really hurt anything.
– Steven Stadnicki
Jul 26 at 15:39
Thank you so much for your dedicated help!
– Le Anh Dung
Jul 26 at 16:58
Thank you so much for your dedicated help!
– Le Anh Dung
Jul 26 at 16:58
add a comment |Â
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%2f2860987%2fhow-to-justify-the-definition-of-summation-s-n-sum-i-1n-a-i-a-1-cdotsa-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
Your definition is incorrect because you use $s_i+1$ 'directly' in your definition before you've shown that it exists. You're loosely on the right track, but you need to be very careful about it.
– Steven Stadnicki
Jul 24 at 3:58
@StevenStadnicki, I has appealed to Recursion Theorem in my poof to show the existence of $s_i+1$.
– Le Anh Dung
Jul 24 at 4:00
The point is that $s_i+1$ doesn't exist as an entity that you can use in the 'definition' of $f$ that you write; $f$ has to be 'internally' written. Do you have a typo, perhaps, in the $ilt n$ case of the mapping?
– Steven Stadnicki
Jul 24 at 4:04
1
$s_1=a_1$ and $s_i+1$=$s_i$+$a_i+1$ for all 1≤ i <n is a simple way to define summation.
– Steve B
Jul 24 at 4:33
@StevenStadnicki Thank you so much. It's actually a typo :). It should be $(i+1,a+a_i+1)$ rather than $(i+1,a+s_i+1)$. I've fixed this typo. Please have a check on my proof again!
– Le Anh Dung
Jul 24 at 7:40