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$):
- $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}
- For $a<b$, 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.
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<a+1$}\\ f(b)+\sum_{i=a+1}^{b-1} f(i) &\text{otherwise} \end{cases} $$