How to prove the generalized associative law for addition on $\mathbb N$?

Question

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 $1\leq 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.

1. $(a+b)+c=a+(b+c)$

2. $a+b=b+a$

Please help me with some hints!

Answer 1

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!

Answer 2

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.