5.2 Formulas for sums and products
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: \[\begin{gather*} \sum_{j=1}^n j = \frac{n(n+1)}{2}\\ \sum_{j=1}^n j^2 = \frac{n(n+1)(2n+1)}{6}\\ \sum_{j=1}^n j^3 = \frac{n^2(n+1)^2}{4}.\\ \end{gather*}\]
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\limits_{j=1}^{1000}j^{10}\) in about seven minutes — long before the advent of calculators! In Struik (1986) (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 \]
Exercise 5.2 Use the above formulas to approximate the integral \[ \int_{x=0}^{10} x^3 - 2x +3 \mbox{d}x \]
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
Exercise 5.3 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 5.2 \[ \forall n \in {\mathbb N}, \; \sum_{j=1}^n j = \frac{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 \((0 \cdot 1)/2\) and this is \(0\) as well.45
Inductive step: Consider the sum on the left-hand side of the \(k+1\)–th version of our formula.
\[ \sum_{j=1}^{k+1} j \]
We can separate out the last term of this sum. Thus, \[ \sum_{j=1}^{k+1} j = (k+1) + \sum_{j=1}^{k} j.\]
Next, we can use the inductive hypothesis to replace the sum (the part that goes from 1 to \(k\)) with a formula. It follows that \[ \sum_{j=1}^{k+1} j = (k+1) + \frac{k(k+1)}{2}.\]
From here on out it’s just algebra: \[\begin{align*} (k+1) + \frac{k(k+1)}{2} & = \frac{2(k+1)}{2} + \frac{k(k+1)}{2} \\ & = \frac{2(k+1) + k(k+1)}{2} \\ & = \frac{(k+1) \cdot (k+2)}{2}. \end{align*}\]
The statement of the theorem now from the principle of mathematical induction.
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 left-hand 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 = \frac{k(k+1)}{2}. \]
Adding \((k+1)\) to both side of this yields
\[ \sum_{j=1}^{k+1} j = (k+1) + \frac{k(k+1)}{2}. \]
Next, we can simplify the right-hand side of this to obtain
\[ \sum_{j=1}^{k+1} j = \frac{(k+1)(k+2)}{2}. \]
Oftentimes one can save considerable effort in an inductive proof by creatively using the factored form during intermediate steps. However, 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 5.3 \[ \forall n \in {\mathbb Z}_{> 0}, \; \sum_{j=1}^n j^2 = \frac{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 \(\displaystyle \frac{1(1+1)(2\cdot 1+1)}{6} = 1\). Since these are equal, the basis is proved.
Inductive step:
Before proceeding with the inductive step, we will figure out what the right-hand side of our theorem looks like when \(n\) is replaced with \(k+1\): \[\begin{gather*} \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} \\ = \frac{(k+1)(k+2)(2k+3)}{6} \\ = \frac{(k^2+3k+2)(2k+3)}{6} \\ = \frac{2k^3+9k^2+13k+6}{6}. \end{gather*}\]
By the inductive hypothesis, \[ \sum_{j=1}^k j^2 = \frac{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 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2. \]
Thus, \[ \sum_{j=1}^{k+1} j^2 = \frac{k(k+1)(2k+1)}{6} + \frac{6(k+1)^2}{6}. \]
Therefore, \[\begin{gather*} \sum_{j=1}^{k+1} j^2 = \frac{(k^2+k)(2k+1)}{6} + \frac{6(k^2+2k+1)}{6} \\ = \frac{(2k^3+3k^2+k)+(6k^2+12k+6)}{6}\\ = \frac{2k^3+9k^2+13k+6}{6}\\ = \frac{(k^2+3k+2)(2k+3)}{6}\\ = \frac{(k+1)(k+2)(2k+3)}{6} \\ = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}. \end{gather*}\]
This proves the inductive step, so the result is true.
Notice how the last four lines of the proof are the same as those in 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 5.4 \[\forall n \geq 2 \in {\mathbb Z}, \prod_{j=2}^n \left( 1 - \frac{1}{j^2} \right) \; = \; \frac{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-\frac{1}{2^2}\right) \cdot \left(1-\frac{1}{3^2}\right) \cdot \left(1-\frac{1}{4^2}\right). \]
This simplifies to \[ \left( 1-\frac{1}{4} \right) \cdot \left( 1-\frac{1}{9} \right) \cdot \left( 1-\frac{1}{16} \right) \; = \; \left( \frac{3}{4} \right) \cdot \left( \frac{8}{9} \right) \cdot \left( \frac{15}{16} \right) \; = \; \frac{360}{576}. \]
The formula on the right-hand side is
\[ \frac{4+1}{2 \cdot 4} \; = \; \frac{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-1/2^2 = 3/4\). On the other hand, the formula is \(\displaystyle \frac{2+1}{2\cdot2} = 3/4\). Since these are equal, the basis is proved.
Inductive step:
Let \(k\) be a particular but arbitrarily chosen integer such that
\[ \prod_{j=2}^k \left( 1 - \frac{1}{j^2} \right) \; = \; \frac{k+1}{2k}. \]
Multiplying46 both sides by the \(k+1\)–th term of the product gives
\[ \left( 1 - \frac{1}{(k+1)^2} \right) \; \cdot \; \prod_{j=2}^k \left( 1 - \frac{1}{j^2} \right) \; = \; \frac{k+1}{2k} \; \cdot \; \left( 1 - \frac{1}{(k+1)^2} \right). \]
Thus \[\begin{align*} \prod_{j=2}^{k+1} \left( 1 - \frac{1}{j^2} \right) & = \frac{k+1}{2k} \; \cdot \; \left( 1 - \frac{1}{(k+1)^2} \right) \\ & = \frac{k+1}{2k} - \frac{(k+1)}{2k(k+1)^2} \\ & = \frac{k+1}{2k} - \frac{(1)}{2k(k+1)} \\ & = \frac{(k+1)^2 - 1}{2k(k+1)} \\ & = \frac{k^2+2k}{2k(k+1)} \\ & = \frac{k (k+2)}{2k(k+1)} \\ & = \frac{k+2}{2(k+1)}. \end{align*}\]5.2.1 Exercises
Write an inductive proof of the formula for the sum of the first \(n\) cubes.
Find a formula for the sum of the first \(n\) fourth powers.
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.
Figure 5.3: Illustration of the first five triangular numbers.
The first five triangular numbers are 1, 3, 6, 10, 15. (See Figure 5.3.)
Determine a formula for the sum of the first \(n\) triangular numbers \(\displaystyle \left( \sum_{i=1}^n T_i \right)\) and prove it using PMI.
Consider the alternating sum of squares: \[\begin{gather*} 1 \\ 1 - 4 = -3 \\ 1 - 4 + 9 = 6 \\ 1 - 4 + 9 - 16 = -10 \\ \mbox{etc.} \end{gather*}\] Guess a general formula for \(\sum_{i=1}^n (-1)^{i-1} i^2\), and prove it using PMI.
Prove the following formula for a product.
\[ \prod_{i=2}^n \left(1 - \frac{1}{i}\right) = \frac{1}{n} \]
Prove \(\displaystyle \sum_{j=0}^{n}(4j+1) \; = \; 2n^{2}+3n+1\) for all integers \(n \geq 0\).
Prove \(\displaystyle \sum_{i=1}^{n}\frac{1}{(2i-1)(2i+1)} \; = \; \frac{n}{2n+1}\) for all natural numbers \(n\).
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, \; \mbox{etc.} \]
Use mathematical induction to prove the following formula involving Fibonacci numbers.
\[ \sum_{i=0}^n (F_i)^2 \, = \, F_n \cdot F_{n+1} \]
References
Struik, D. J. 1986. A Source Book in Mathematics, 1200-1800. Princeton University Press.
If you’d prefer to avoid the “empty sum” argument, you can choose to use \(n=1\) as the basis case. The theorem should be restated so the universe of discourse is positive naturals.↩
Really, the only reason I’m doing this silly proof is to point out to you that when you’re doing the inductive step in a proof of a formula for a product, you don’t add to both sides anymore, you multiply. You see that, right? Well, consider yourself to have been pointed out to or … oh, whatever.↩