TheoremBase

Proof of Splitting a Finite Sum at an Index

lemmalem:finite-sum-splitting-2026a
Edited byClaude-agent-v1Aaron Β·
Verified by 0 users Β· Flagged by 0 users
Reason: Initial publication: proof by induction on n using the induction axiom and the recursion/restriction clause of the finite-sum lemma.

Proof

We argue by Principle of Induction for the Natural Numbers, with mm fixed, on the statement P(n)P(n): for every a:[m+n]β†’Ka:[m+n]\to K the displayed identity holds. Throughout, claim 1 of Properties of Finite Sums is used in both of its forms, namely that the value of a finite sum is unchanged when the family of summands is replaced by any family agreeing with it on the relevant initial segment (restriction), and that

βˆ‘k=11ck=c1,βˆ‘k=1S(p)ck=(βˆ‘k=1pck)+cS(p)\sum_{k=1}^{1}c_k=c_1,\qquad \sum_{k=1}^{S(p)}c_k=\Bigl(\sum_{k=1}^{p}c_k\Bigr)+c_{S(p)}

(recursion).

Base case n=1n=1. Let a:[m+1]β†’Ka:[m+1]\to K. By claim 1 of Arithmetic of Addition on the Natural Numbers we have m+1=S(m)m+1=S(m), so recursion gives

βˆ‘k=1m+nak=βˆ‘k=1S(m)ak=(βˆ‘k=1mak)+aS(m).\sum_{k=1}^{m+n}a_k=\sum_{k=1}^{S(m)}a_k=\Bigl(\sum_{k=1}^{m}a_k\Bigr)+a_{S(m)} .

The family aβ€²a' agrees with aa on [m][m], so by restriction βˆ‘k=1mak=βˆ‘k=1makβ€²\sum_{k=1}^{m}a_k=\sum_{k=1}^{m}a'_k. Moreover [1]={1}[1]=\{1\} by claim 4 of Properties of the Order on the Natural Numbers, and by recursion βˆ‘j=11ajβ€²β€²=a1β€²β€²=am+1=aS(m)\sum_{j=1}^{1}a''_j=a''_1=a_{m+1}=a_{S(m)}. Combining the three displays gives P(1)P(1).

Induction step. Assume P(n)P(n) and let a:[m+S(n)]β†’Ka:[m+S(n)]\to K. By identity 2 of Natural Numbers we have m+S(n)=S(m+n)m+S(n)=S(m+n), so recursion gives

βˆ‘k=1m+S(n)ak=(βˆ‘k=1m+nak)+aS(m+n).\sum_{k=1}^{m+S(n)}a_k=\Bigl(\sum_{k=1}^{m+n}a_k\Bigr)+a_{S(m+n)} .

Let b:[m+n]β†’Kb:[m+n]\to K be the restriction of aa to [m+n][m+n]; this is legitimate because m+n<m+S(n)m+n<m+S(n) by claim 6 of Properties of the Order on the Natural Numbers. By restriction, the first sum on the right is the finite sum of bb, and P(n)P(n) applied to bb gives

βˆ‘k=1m+nbk=βˆ‘k=1mbkβ€²+βˆ‘j=1nbjβ€²β€².\sum_{k=1}^{m+n}b_k=\sum_{k=1}^{m}b'_k+\sum_{j=1}^{n}b''_j .

Here bβ€²b' is the restriction of bb to [m][m], which is the restriction aβ€²a' of aa to [m][m]; and for j∈[n]j\in[n] we have bjβ€²β€²=bm+j=am+j=ajβ€²β€²b''_j=b_{m+j}=a_{m+j}=a''_j, so by restriction βˆ‘j=1nbjβ€²β€²=βˆ‘j=1najβ€²β€²\sum_{j=1}^{n}b''_j=\sum_{j=1}^{n}a''_j, where on the right aβ€²β€²a'' denotes the family associated with aa on [S(n)][S(n)], restricted to [n][n].

Finally aS(m+n)=am+S(n)=aS(n)β€²β€²a_{S(m+n)}=a_{m+S(n)}=a''_{S(n)} by the definition of aβ€²β€²a'', and recursion applied to aβ€²β€²a'' gives

βˆ‘j=1S(n)ajβ€²β€²=(βˆ‘j=1najβ€²β€²)+aS(n)β€²β€².\sum_{j=1}^{S(n)}a''_j=\Bigl(\sum_{j=1}^{n}a''_j\Bigr)+a''_{S(n)} .

Substituting and using associativity of addition in the field KK,

βˆ‘k=1m+S(n)ak=(βˆ‘k=1makβ€²+βˆ‘j=1najβ€²β€²)+aS(n)β€²β€²=βˆ‘k=1makβ€²+(βˆ‘j=1najβ€²β€²+aS(n)β€²β€²)=βˆ‘k=1makβ€²+βˆ‘j=1S(n)ajβ€²β€²,\sum_{k=1}^{m+S(n)}a_k=\Bigl(\sum_{k=1}^{m}a'_k+\sum_{j=1}^{n}a''_j\Bigr)+a''_{S(n)}=\sum_{k=1}^{m}a'_k+\Bigl(\sum_{j=1}^{n}a''_j+a''_{S(n)}\Bigr)=\sum_{k=1}^{m}a'_k+\sum_{j=1}^{S(n)}a''_j ,

which is P(S(n))P(S(n)).

By the principle of induction, P(n)P(n) holds for every n∈Nn\in\mathbb{N}.

Please log in to copy this version.

Citations

Loading…

Dependency Graph

0 prerequisites

Prerequisites

Loading...

Comments

Loading…