Calculus – Sequences and series – Finite sums and mathematical induction

Principle of mathematical induction

Let \(S_n\) be a statement about a positive integer \(n\). Suppose that

1. \(S_1\) is true,


2. \(S_{k+1}\) is true whenever \(S_k\) is true.

Then \(S_n\) is true for all positive integers \(n\).

Examples

1) \(\displaystyle\sum_{k=1}^nk=\tfrac{1}{2}n(n+1)\) for all \(n\in\{1,2,3,\ldots\}\).

For \(n=1\) the statement is true: \(1=\frac{1}{2}\cdot1\cdot2\). If we assume that the statement is true for a certain value of \(n\), then

\[\sum_{k=1}^{n+1}k=\sum_{k=1}^nk+(n+1)=\frac{1}{2}n(n+1)+(n+1)=\frac{1}{2}(n+1)(n+2).\]

Since this is exactly the formula with \(n\) replaced by \(n+1\), this proves the statement for all \(n\in\{1,2,3,\ldots\}\).

2) \(\displaystyle\sum_{k=1}^nk^2=\tfrac{1}{6}n(n+1)(2n+1)\) for all \(n\in\{1,2,3,\ldots\}\).

For \(n=1\) this reads: \(1=\frac{1}{6}\cdot1\cdot2\cdot3\) which is true. If we assume that the statement is true for a certain value of \(n\), then

\begin{align*} \sum_{k=1}^{n+1}k^2&=\sum_{k=1}^nk^2+(n+1)^2=\frac{1}{6}n(n+1)(2n+1)+(n+1)^2=\frac{1}{6}(n+1)\left\{n(2n+1)+6(n+1)\right\}\\[2.5mm] &=\frac{1}{6}(n+1)(2n^2+7n+6)=\frac{1}{6}(n+1)(n+2)(2n+3). \end{align*}

Since this is exactly the formula with \(n\) replaced by \(n+1\), this proves the statement for all \(n\in\{1,2,3,\ldots\}\).

3) \(\displaystyle\sum_{k=1}^nk^3=\left(\sum_{k=1}^nk\right)^2=\tfrac{1}{4}n^2(n+1)^2\) for all \(n\in\{1,2,3,\ldots\}\).

For \(n=1\) this reads: \(1=\frac{1}{4}\cdot1^2\cdot2^2\) which is true. If we assume that the statement is true for a certain value of \(n\), then

\begin{align*} \sum_{k=1}^{n+1}k^3&=\sum_{k=1}^nk^3+(n+1)^3=\frac{1}{4}n^2(n+1)^2+(n+1)^3=\frac{1}{4}(n+1)^2\left\{n^2+4(n+1)\right\}\\[2.5mm] &=\frac{1}{4}(n+1)^2(n^2+4n+4)=\frac{1}{4}(n+1)^2(n+2)^2. \end{align*}

Since this is exactly the formula with \(n\) replaced by \(n+1\), this proves the statement for all \(n\in\{1,2,3,\ldots\}\).

Another interesting result is: \(\displaystyle\sum_{k=n^2+1}^{(n+1)^2}k=n^3+(n+1)^3\) for all \(n\in\{1,2,3,\ldots\}\).

This can be shown directly: note that the sum has \(2n+1\) terms, so we have

\[\sum_{k=n^2+1}^{(n+1)^2}k=\frac{1}{2}(2n+1)\left\{n^2+1+(n+1)^2\right\}=(2n+1)(n^2+n+1)=2n^3+3n^2+3n+1=n^3+(n+1)^3.\]

---

Last modified on March 15, 2021