# Summation Equivalent definition

Given the definition:

Prove Lemma 6.1.1:

However, when the proof gets to the following case, I don't understand the second "step" (marked with a red question mark).

Can you provide some clarification? As fully detailed and justified as possible, please. I tried proving Lemma 6.1.1 myself using induction but I couldn't, here's my attempt:

Let $$a,b\in \mathbb{Z}$$. Note: Here induction "runs" on $$\mathbb{N}$$ starting from $$1$$ (not $$0$$):

1. $$a=b$$ \begin{align} \sum_{n=a}^{b} f(n) &= f(n)\\ &= f(b) && \text{n=a=b}\\ &= f(b) + 0\\ &= f(b) + \sum_{n=a}^{a-1} f(n) && \text{Definition (6.1.1)} \\ &= f(b) + \sum_{n=a}^{b-1} f(n) \end{align}
2. For $$a, we use induction over $$b$$,
• [Base case] For $$b=a+1$$, \begin{align*} \sum_{n=a}^{b=a+1} f(n) &= f(a) + \sum_{n=a+1}^{a+1} f(n) && \text{Definition (6.1.1)}\\ &= f(a) + \sum_{n=b}^{b} f(n)\\ &= f(a) + f(b)\\ &= f(b) + f(a)\\ &= f(b) + \sum_{n=a}^{a} f(n)\\ &= f(b) + \sum_{n=a}^{b-1} f(n) && \text{b=a+1 \Rightarrow b-1=a} \end{align*}
• [Induction hypothesis] Assume that for $$b=a+k$$, with $$k\in \mathbb{N}$$ we have that: \begin{align*} \sum_{n=a}^{a+k} f(n) &= f(b) + \sum_{n=a}^{b-1} f(n) \end{align*}
• For $$b=a+k$$ we have: \begin{align*} \sum_{n=a}^{b=a+k+1} f(n) &= f(a) + \sum_{n=a+1}^{a+k+1} f(n) && \text{Definition (6.1.1)}\\ \end{align*}

From that point on I don't know what goes next, please help.

## 2 Answers

The induction in proof 6.1.1 is on $$b-a$$.

The induction hypothesis would assume the lemma is true for any LHS where the the upper and lower bounds differ by $$b-a-1$$. This includes assuming the lemma is true for LHS like:

\begin{align*} \sum_{i=a}^{b-1}f(i) &= \cdots\\ \sum_{i=a-1}^{b-2}f(i) &= \cdots\\ \sum_{i=a+1}^{b}f(i) &= \cdots \tag{*}\\ \sum_{i=1}^{b-a}f(i) &= \cdots\\ \end{align*}

Then your $$(\color{red}?)$$ line is applying one particular case $$(*)$$ of the induction hypothesis, where the LHS has lower bound $$a+1$$ and upper bound $$b$$:

$$\sum_{i=a+1}^{b}f(i) = \begin{cases} 0 & \text{if b

The summation on the RHS of the last line should have upper limits of a+k. Then you might be able to use the first term on the RHS to arrive at something that lets you use induction.

• Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
– Community Bot
Oct 2 at 2:18