1.4: Induction on a Summation

Last updated
Save as PDF

Page ID: 49261

Wikibooks - Data Structures
Wikipedia

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The next example of induction we consider is more algebraic in nature:

Let's say we are given the formula \(\dfrac {(n)(n+1)}{2}\) and we want to prove that this formula gives us the sum of the first \(n\) numbers. As a first attempt, we might try to just show that this is true for 1

\[\dfrac {(1)(1+1)}{2}=1=1,\nonumber\]

for 2

\[\dfrac {(2)(2+1)}{2}=3=1+2,\nonumber\]

for 3

\[\dfrac {(3)(3+1)}{2}=6=1+2+3\nonumber\]

and so on, however we'd quickly realize that our so called proof would take infinitely long to write out! Even if you carried out this proof and showed it to be true for the first billion numbers, that doesn't nescessarily mean that it would be true for one billion and one or even a hundred billion. This is a strong hint that maybe induction would be useful here.

Let's say we want to prove that the given formula really does give the sum of the first n numbers using induction. The first step is to prove the base case; i.e. we have to show that it is true when n = 1. This is relatively easy; we just substitute 1 for the variable n and we get (\(\dfrac {(1)(1+1)}{2}=1\)), which shows that the formula is correct when n = 1.

Now for the inductive step. We have to show that if the formula is true for j, it is also true for j + 1. To phrase it another way, assuming we've already proven that the sum from 1 to (j) is \(\dfrac {((j))((j)+1)}{2}\), we want to prove that the sum from 1 to (j+1) is \(\dfrac {((j+1))((j+1)+1)}{2}\). Note that those two formulas came about just by replacing n with (j) and (j+1) respectively.

To prove this inductive step, first note that to calculate the sum from 1 to j+1, you can just calculate the sum from 1 to j, then add j+1 to it. We already have a formula for the sum from 1 to j, and when we add j+1 to that formula, we get this new formula: \(\dfrac {((j))((j)+1)}{2}+(j+1)\). So to actually complete the proof, all we'd need to do is show that \(\dfrac {((j))((j)+1)}{2}+(j+1)=\dfrac {((j+1))((j+1)+1)}{2}\).

We can show the above equation is true via a few simplification steps:

\[\dfrac {((j))((j)+1)}{2}+(j+1)=\dfrac {((j+1))((j+1)+1)}{2}\nonumber\]

\[\dfrac {(j)(j+1)}{2}+j+1=\dfrac {(j+1)(j+1+1)}{2}\nonumber\]

\[\dfrac {(j)(j+1)}{2}+\dfrac {2(j+1)}{2}=\dfrac {(j+1)(j+2)}{2}\nonumber\]

\[\dfrac {(j)(j+1)+2(j+1)}{2}=\dfrac {(j+1)(j+2)}{2}\nonumber\]

\[\dfrac {j^{2}+j+2j+2}{2}=\dfrac {(j+1)(j+2)}{2}\nonumber\]

\[\dfrac {j^{2}+3j+2}{2}=\dfrac {(j+1)(j+2)}{2}\nonumber\]

\[\dfrac {(j+1)(j+2)}{2}=\dfrac {(j+1)(j+2)}{2}\nonumber\]