- Last updated
- Save as PDF
- Page ID
- 19389
\( \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}}\)
Gauss, when only a child, found a formula for summing the first \(100\) natural numbers (or so the story goes. . . ). This formula, and his clever method for justifying it, can be easily generalized to the sum of the first \(n\) naturals. While learning calculus, notably during the study of Riemann sums, one encounters other summation formulas. For example, in approximating the integral of the function \(f(x) = x^2\) from \(0\) to \(100\) one needs the sum of the first \(100\) squares. For this reason, somewhere in almost every calculus book one will find the following formulas collected:
\[ \sum_{j=1}^{n} j =\dfrac{n(n+1)}{2} \\ \sum_{j=1}^{n} j^2 =\dfrac{n(n+1)(2n+1)}{6} \\ \sum_{j=1}^{n} j^3 =\dfrac{n^2(n+1)^2}{4} \]
A really industrious author might also include the sum of the fourth powers. Jacob Bernoulli (a truly industrious individual) got excited enough to find formulas for the sums of the first ten powers of the naturals. Actually, Bernoulli went much further. His work on sums of powers lead to the definition of what are now known as Bernoulli numbers and let him calculate \(\sum^{1000}_{j=1} j^{10}\) in about seven minutes – long before the advent of calculators! In [16, p. 320], Bernoulli is quoted:
With the help of this table it took me less than half of a quarter of an hour to find that the tenth powers of the first \(1000\) numbers being added together will yield the sum \(91, 409, 924, 241, 424, 243, 424, 241, 924, 242, 500\).
To the beginning calculus student, the beauty of the above relationships may be somewhat dimmed by the memorization challenge that they represent. It is fortunate then, that the right-hand side of the third formula is just the square of the right-hand side of the first formula. And of course, the right-hand side of the first formula is something that can be deduced by a six year old child (provided that he is a super-genius!) This happy coincidence leaves us to apply most of our rote memorization energy to formula number two, because the first and third formulas are related by the following rather bizarre-looking equation,
\[\sum_{j=1}^{n} j^3 = \left( \sum_{j=1}^{n} j \right)^2. \]
The sum of the cubes of the first \(n\) numbers is the square of their sum.
For completeness, we should include the following formula which should be thought of as the sum of the zeroth powers of the first \(n\) naturals.
\[\sum_{j=1}^{n} 1 = n\]
Practice
Use the above formulas to approximate the integral
\(\int_{x=0}^{10} x^3 − 2x + 3dx\)
Our challenge today is not to merely memorize these formulas but to prove their validity. We’ll use PMI.
Before we start in on a proof, it’s important to figure out where we’re trying to go. In proving the formula that Gauss discovered by induction we need to show that the \(k + 1\)–th version of the formula holds, assuming that the \(k\)–th version does. Before proceeding on to read the proof do the following
Practice
Write down the \(k + 1\)–th version of the formula for the sum of the first \(n\) naturals. (You have to replace every \(n\) with a \(k + 1\).)
Theorem \(\PageIndex{1}\)
\[∀n ∈ \mathbb{N}, \sum^{n}_{j=1} j = \dfrac{n(n + 1)}{2}\]
- Proof
-
We proceed by induction on \(n\).
Basis: Notice that when \(n = 0\) the sum on the left-hand side has no terms in it! This is known as an empty sum, and by definition, an empty sum’s value is \(0\). Also, when \(n = 0\) the formula on the right-hand side becomes \(\dfrac{(0 · 1)}{2}\) and this is \(0\) as well.1
Inductive step: Consider the sum on the left-hand side of the \(k + 1\)–th version of our formula.
\(\sum^{k+1}_{j=1} j\)
We can separate out the last term of this sum.
\( = (k+1) + \sum^{k}_{j=1} j\)
Next, we can use the inductive hypothesis to replace the sum (the part that goes from \(1\) to \(k\)) with a formula.
\(= (k + 1) + \dfrac{k(k + 1)}{2}\)
From here on out it’s just algebra . . .
\(= \dfrac{2(k + 1)}{2} + \dfrac{k(k + 1)}{2} \\ = \dfrac{2(k + 1) + k(k + 1)}{2} \\ = (k + 1) · \dfrac{(k + 2)}{2} \)
Q.E.D.
Notice how the inductive step in this proof works. We start by writing down the left-hand side of \(P_{k+1}\), we pull out the last term so we’ve got the lefthand side of \(P_k\) (plus something else), then we apply the inductive hypothesis and do some algebra until we arrive at the right-hand side of \(P_{k+1}\). Overall, we’ve just transformed the left-hand side of the statement we wish to prove into its right-hand side.
There is another way to organize the inductive steps in proofs like these that works by manipulating entire equalities (rather than just one side or the other of them).
Inductive step (alternate): By the inductive hypothesis, we can write
\(\sum_{j=1}^{k} j = \dfrac{k(k+1)}{2} .\)
Adding \((k + 1)\) to both side of this yields
\(\sum_{j=1}^{k+1} j = (k + 1) + \dfrac{k(k+1)}{2} .\)
Next, we can simplify the right-hand side of this to obtain
\(\sum_{j=1}^{k+1} j = \dfrac{(k + 1)(k + 2)}{2} .\)
Q.E.D.
Oftentimes one can save considerable effort in an inductive proof by creatively using the factored form during intermediate steps. On the other hand, sometimes it is easier to just simplify everything completely, and also, completely simplify the expression on the right-hand side of \(P(k + 1)\) and then verify that the two things are equal. This is basically just another take on the technique of “working backwards from the conclusion.” Just remember that in writing-up your proof you need to make it look as if you reasoned directly from the premises to the conclusion. We’ll illustrate what we’ve been discussing in this paragraph while proving the formula for the sum of the squares of the first \(n\) positive integers.
Theorem \(\PageIndex{2}\)
\[∀n ∈ \mathbb{Z}^+, \sum^{n}_{j=1} j^2 = \dfrac{n(n + 1)(2n + 1)}{6}\]
- Proof
-
We proceed by induction on \(n\).
Basis: When \(n = 1\) the sum has only one term, \(1^2 = 1\). On the other hand, the formula is \(\dfrac{1(1 + 1)(2 · 1 + 1)}{6} = 1\). Since these are equal, the basis is proved.
Before proceeding with the inductive step, in this box, we will figure out what the right-hand side of our theorem looks like when \(n\) is replaced with \(k + 1\):
\(\dfrac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6} \\ = \dfrac{(k + 1)(k + 2)(2k + 3)}{6} \\ = \dfrac{(k^2 + 3k + 2)(2k + 3)}{6} \\ = \dfrac{2k^3 + 9k^2 + 13k + 6}{6} \)
Inductive step: By the inductive hypothesis,
\(\sum_{j=1}^{k} j^2 = \dfrac{k(k + 1)(2k + 1) }{6}\).
Adding \((k + 1)^2\) to both sides of this equation gives
\((k + 1)^2 + \sum_{j=1}^{k} j^2 = \dfrac{k(k + 1)(2k + 1)}{6} + (k + 1)^2\).
Thus,
\(\sum_{j=1}^{k+1} j^2 = \dfrac{k(k + 1)(2k + 1)}{6} + \dfrac{6(k + 1)^2}{6} \)
Therefore,
\(\sum_{j=1}^{k+1} j^2 = \dfrac{k(k + 1)(2k + 1)}{6} + \dfrac{6(k^2 + 2k + 1)}{6} \\ = \dfrac{(2k^3 + 3k^2 + k) + (6k^2 + 12k + 6)}{6} \\ = \dfrac{2k^3 + 9k^2 + 13k + 6}{6} \\ = \dfrac{(k^2 + 3k + 2)(2k + 3)}{6} \\ = \dfrac{(k + 1)(k + 2)(2k + 3)}{6} \\ = \dfrac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6}.\)
This proves the inductive step, so the result is true.
Q.E.D.
Notice how the last four lines of the proof are the same as those in the box above containing our scratch work? (Except in the reverse order.)
We’ll end this section by demonstrating one more use of this technique. This time we’ll look at a formula for a product rather than a sum.
Theorem \(\PageIndex{3}\)
\[∀n ≥ 2 ∈ \mathbb{Z}, \prod^{n}_{j=2} \left(1 − \dfrac{1}{j^2} \right) = \dfrac{n + 1}{2n} .\]
Before preceding with the proof let’s look at an example (although this has nothing to do with proving anything, it’s really not a bad idea – it can keep you from wasting a lot of time trying to prove something that isn’t actually true!) When \(n = 4\) the product is
\( \left( 1 − \dfrac{1}{2^2} \right) · \left( 1 − \dfrac{1}{3^2} \right) · \left( 1 − \dfrac{1}{4^2} \right) .\)
This simplifies to
\( \left( 1 − \dfrac{1}{4} \right) · \left( 1 − \dfrac{1}{9} \right) · \left( 1 − \dfrac{1}{16} \right) = \left( \dfrac{3}{4} \right) \cdot \left( \dfrac{8}{9} \right) \cdot \left( \dfrac{15}{16} \right) = \dfrac{360}{576} .\)
The formula on the right-hand side is
\(\dfrac{4 + 1}{2 \cdot 4} = \dfrac{5}{8}. \)
Well! These two expressions are clearly not equal to one another. . .What? You say they are? Just give me a second with my calculator. . .
Alright then. I guess we can’t dodge doing the proof. . .
- Proof
-
(Using mathematical induction on \(n\).)
Basis: When \(n = 2\) the product has only one term, \(1 − \dfrac{1}{2}^2 = \dfrac{3}{4}\). On the other hand, the formula is \(\dfrac{2 + 1}{2 · 2} = \dfrac{3}{4}\). Since these are equal, the basis is proved.
Inductive step:
Let \(k\) be a particular but arbitrarily chosen integer such that
\( \prod^{k}_{j=2} \left( 1 − \dfrac{1}{j^2} \right) = \dfrac{k + 1}{2k}.\)
Multiplying2 both sides by the \(k + 1\)-th term of the product gives \(1 − \dfrac{1}{(k + 1)^2} · \prod^{k}_{j=2} \left( 1 − \dfrac{1}{j^2} \right) = \dfrac{k + 1}{2k} · \left( 1 − \dfrac{1}{(k + 1)^2} \right)\).
Thus
\( \begin{array} \prod^{k+1}_{j=2} \left( 1 − \dfrac{1}{j^2} \right) &= \dfrac{k + 1}{2k} · \left( 1 − \dfrac{1}{(k + 1)^2} \right) \\ &= \dfrac{k + 1}{2k} − \dfrac{(k + 1)}{2k(k + 1)^2} \\ &= \dfrac{k + 1}{2k} − \dfrac{(1)}{2k(k + 1)} \\ &= \dfrac{(k + 1)^2 − 1}{2k(k + 1)} \\ &= \dfrac{k^2 + 2k}{2k(k + 1)} \\ &= \dfrac{k(k + 2)}{2k(k + 1)} \\ &= \dfrac{k + 2}{2(k + 1)}. \end{array}\)
Q.E.D.
Exercises:
Exercise \(\PageIndex{1}\)
Write an inductive proof of the formula for the sum of the first \(n\) cubes.
Exercise \(\PageIndex{2}\)
Find a formula for the sum of the first \(n\) fourth powers.
Exercise \(\PageIndex{3}\)
The sum of the first \(n\) natural numbers is sometimes called the \(n\)-th triangular number \(T_n\). Triangular numbers are so-named because one can represent them with triangular-shaped arrangements of dots.
The first several triangular numbers are \(1, 3, 6, 10, 15\), et cetera. Determine a formula for the sum of the first \(n\) triangular numbers \(\left( \sum^{n}_{i=1} T_i \right) \)! and prove it using PMI.
Exercise \(\PageIndex{4}\)
Consider the alternating sum of squares:
\(1 \\ 1 − 4 = −3 \\ 1 − 4 + 9 = 6 \\ 1 − 4 + 9 − 16 = −10 \\ \text{et cetera}\)
Guess a general formula for \(\sum^{n}_{i=1} (−1)^{i−1} i^2\), and prove it using PMI.
Exercise \(\PageIndex{5}\)
Prove the following formula for a product.
\(\prod^{n}_{i=2} \left( 1 − \dfrac{1}{i} \right) = \dfrac{1}{n}\)
Exercise \(\PageIndex{6}\)
Prove \(\sum^{n}_{j=0} (4j + 1) = 2n^2 + 3n + 1\) for all integers \(n ≥ 0\).
Exercise \(\PageIndex{7}\)
Prove \(\sum^{n}_{i=1} \dfrac{1}{(2i − 1)(2i + 1)} = \dfrac{n}{2n + 1}\) for all natural numbers \(n\).
Exercise \(\PageIndex{8}\)
The Fibonacci numbers are a sequence of integers defined by the rule that a number in the sequence is the sum of the two that precede it.
\(F_{n+2} = F_n + F_{n+1}\)
The first two Fibonacci numbers (actually the zeroth and the first) are both \(1\).
Thus, the first several Fibonacci numbers are
\(F_0 = 1, F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, F_5 = 8, F_6 = 13, F_7 = 21,\)
et cetera Use mathematical induction to prove the following formula involving Fibonacci numbers.
\(\sum^{n}_{i=0} (F_i)^2 = F_n · F_{n+1}\)
