Sigma Notation In Inductive Proofs

When using proof by induction to demonstrate the result of a sum, we can often use sigma notation to make these proofs more concise. Suppose we want to show that

$\sum_{n=1}^{N}{\frac1{(2n-1)(2n+1)}} = \frac{N}{2N+1}$

To use proof by induction to demonstrate this, we need to:

Establish the base case,
Demonstrate the inductive step

If we consider the most general case of this problem, we are trying to show that

$\sum_{n=1}^{N}{f(n)} = g(N)$

where $f(n)$ are the terms of our series, and $g(N)$ is an analytic expression which we want to show can be used to evaluate the value of the series directly. To prove that this expression hold for all $N \in \N$ , we need to show that it holds for $N = 1$ , which means we need to show that

\begin{aligned} \sum_{n=1}^{1}{f(n)} &= g(1) \\ f(1) &= g(1) \\ \end{aligned}

And then for our inductive step, we assume that the expression holds for $N = k$ , and we need to prove it for $N = k + 1$ . Since the series between these two cases differ only in the final term, we typically use the following approach

\begin{aligned} \sum_{n=1}^{k+1}{f(n)} &= \sum_{n=1}^{k}{f(n)} + f(k+1) \\ \sum_{n=1}^{k+1}{f(n)} &= g(k) + f(k+1) \\ \end{aligned}

From here, if we can then show that $g(k) + f(k+1) = g(k+1)$ , then we are able to conclude that

$\sum_{n=1}^{k+1}{f(n)} = g(k+1)$

which then completes our proof.

...