Skip to main content

Section 9.5 Proofs of Explicit Formulas for Sums and Products

We have observed patterns and conjectured explicit formulas for sums and products in Section 9.3, including sums involving Fibonacci numbers, and in Section 9.4, including sums involving binomial coefficients. In a few special cases, we saw how to use the Binomial Theorem to prove summation formulas, but how do we prove the Binomial Theorem itself as well as other formulas? In this section, we look at two proof techniques, including new special cases of mathematical induction and an extension of combinatorial proofs to summations. We close by looking at special sums, such as the handshake formula from Theorem 1.1.4 and finite geometric sums.

Subsection 9.5.A Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas

We can use mathematical induction to prove explicit formulas for summations and products. We begin with the proof format for a summation.
The key first step in the last line of the proof uses the recursive definitions of partial sums, Remark 9.3.5.
Similarly, here is the proof format for a product.
The key first step in the last line of the proof uses the recursive definitions of partial products, Remark 9.3.18.
As usual, when we introduce a new proof format, we give you examples to copy and edit.

Activity 9.5.A Proving sum and product formulas using mathematical induction.

 
  1. Copy the following proof using mathematical induction to prove that \(\displaystyle \sum_{k=0}^n2^k=2^{n+1}-1\) for \(n \ge 0\text{.}\)

    Proof.
    Write \(f(n) = 2^{n+1}-1\text{.}\) Induct on \(n\text{.}\)
    First, when \(n=0\) we know that \(\displaystyle \sum_{k=0}^02^k=2^0=1\) and also
    \begin{equation*} f(0)=2^{0+1}-1=2-1=1. \end{equation*}
    Next, assume \(\displaystyle \sum_{k=0}^{n-1}2^k=f(n-1)= 2^{(n-1)+1}-1=2^n-1\) for some integer \(n > s\text{.}\)
    Then
    \begin{align*} \sum_{k=0}^n2^k \amp = \left(\sum_{k=0}^{n-1}2^k\right) + 2^n \\ \amp = f(n-1) + 2^n = \left(2^n-1\right)+2^n \\ \amp = 2^n+2^n-1=2\cdot2^n-1=2^{n+1}-1 \\ \amp = f(n)\text{.} \end{align*}
  2. Edit the proof in (a) to prove that \(\displaystyle \sum_{k=0}^n2 \cdot 3^k = 3^{n+1}-1\) for \(n\ge 0\text{.}\)
  3. Copy the following proof using mathematical induction to prove that \(\displaystyle \prod_{k=1}^nk=n!\) for \(n \ge 1\text{.}\)

    Proof.
    Write \(f(n) = n!\text{.}\) Induct on \(n\text{.}\)
    First, when \(n=1\) we know that \(\displaystyle \prod_{k=1}^1k=1=1\) and also \(f(1)=1!=1\text{.}\)
    Next, assume \(\displaystyle \prod_{k=1}^{n-1}k=f(n-1)= (n-1)!\) for some integer \(n > s\text{.}\)
    Then
    \begin{align*} \prod_{k=1}^nk \amp = \left(\prod_{k=1}^{n-1}k\right) \cdot n \\ \amp = f(n-1) \cdot n \\ \amp = \left((n-1)!\right) \cdot n \\ \amp = n(n-1)! =n! = f(n) \end{align*}
  4. Edit the proof in (c) to prove that \(\displaystyle \prod_{j=1}^n \frac{1}{j} = \frac{1}{n!}\) for \(n\ge1\text{.}\)
  5. Copy the following proof using mathematical induction to prove that \(\displaystyle \sum_{k=1}^nF_{2k}=F_{2n+1}-1\) for \(n \ge 1\) where, as usual, the Fibonacci numbers are defined by \(F_0=0\text{,}\) \(F_1=1\text{,}\) and \(F_n=F_{n-1} + F_{n-2}\) for \(n \ge 2\text{.}\)

    Proof.
    Write \(f(n) = F_{2n+1}-1\text{.}\) Induct on \(n\text{.}\)
    First, when \(n=1\) we have \(\displaystyle\sum_{k=1}^1F_{2k}=F_{2(1)}=F_2=1\) and also
    \begin{equation*} f(1) = F_{2(1)+1}-1=F_3-1=2-1=1\text{.} \end{equation*}
    Next, assume
    \begin{equation*} \sum_{k=1}^{n-1}F_{2k} = f(n-1) = F_{2(n-1)+1}-1 = F_{2n-1}-1 \end{equation*}
    for some integer \(n > 1\text{.}\)
    Then
    \begin{align*} \ sum_{k=1}^nF_{2k} \amp = \left( \sum_{k=1}^{n-1}F_{2k} \right) + F_{2n} = f(n-1) + F_{2n} \\ \amp = \left(F_{2n-1}-1\right)+F_{2n} \\ \amp = \left(F_{2n} + F_{2n-1}\right) -1 = F_{2n+1}-1 = f(n) \end{align*}
    The next-to-last equality uses the recursive definition the Fibonacci numbers to conclude that the sum of the consecutive terms \(F_{2n}\) and \(F_{2n-1}\) equals the next term, \(F_{2n+1}\text{.}\)
    Note: We saw this summation in Activity 9.3.C (a) and Example 9.3.25.
  6. Edit the proof from (e) to prove that \(\displaystyle \sum_{k=1}^{n}F_{2k-1} = F_{2n}\) for \(n \ge 1\text{.}\) Note: We saw this summation in Section 9.3 Exercise 25.

Subsection 9.5.B Proof Format: Combinatorial Proof of Sums

We can use mathematical induction to prove the explicit formula of a sum of the form \(\displaystyle \sum_{k=s}^na_k=f(n)\text{,}\) but the recursive step of these proofs is based on the fact that the terms \(a_k\) do not depend on the upper limit \(n\text{.}\) How can we prove an explicit formula for a summation where the terms depend on \(n\text{?}\) For example, in Section 9.4 we saw sums with binomial coefficients where the terms involved \(n\text{.}\) An option is to extend the proof format for a combinatorial proof, Theorem 2.3.13, to apply to sums. This extended proof format is especially useful for proofs involving binomial coefficients, since, by definition, they count objects.
The phrase “condition on \(k=\) (say what \(k\) counts)” indicates that we are considering a list of cases Case \(s\text{,}\) Case \(s+1\text{,}\) …, Case \(n\) where in Case \(k\text{,}\) there are \(k\) of some object. Let’s see this new proof format in action.

Activity 9.5.B Combinatorial proof of sum.

 
  1. Copy the following combinatorial proof to that
    \begin{equation*} \displaystyle \sum_{k=0}^n\binom{n}{k} =2^n \end{equation*}
    for any natural number \(n\text{.}\) We made this conjecture about the row sums of the arithmetic triangle in Activity 9.4.B (b).

    Proof.
    We use a combinatorial proof. Consider the following situation: we have the set \(T = \{1,2,\ldots, n\}\text{.}\) How many ways are there to choose a subset of \(T\text{?}\)
    First, condition on \(k=\) the number of elements in the subset. There are \(\binom{n}{k}\) subsets with \(k\) elements for \(k = 0, 1, 2, \ldots, n\text{.}\) Since cases add Theorem 2.2.7, there are a total of \(\displaystyle \sum_{k=0}^n\binom{n}{k}\) subsets.
    On the other hand, for each element of \(T\) we can decide whether it will be in the subset or not (2 choices). There are two choices for whether 1 is in the subset, two choices for whether 2 is in the subset, and so on up to two choices for whether \(n\) is in the subset. Since steps multiply Theorem 2.2.3, there are \(\underbrace{2\cdot 2 \cdots \cdots 2}_{n \text{ times } } = 2^n\) subsets.
    Since we counted the same quantity in two different ways, it follows that
    \begin{equation*} \sum_{k=0}^n\binom{n}{k} =2^n\text{.} \end{equation*}
  2. Edit the proof in (a) to prove that
    \begin{equation*} \displaystyle \sum_{k=1}^nk\binom{n}{k} =n2^{n-1} \end{equation*}
    for any integer \(n \ge 1\text{.}\) Hints: Out of a group of \(n\) people, choose a subset to be a committee (with at least one person) where one of the people on the committee is the chair. Condition on \(k =\) the number of people on the committee. In one way of counting, choose the committee members first and then the chair. In the other way of counting, choose the chair first and then the rest of the committee members.

Subsection 9.5.C Detour: Special Sums

We have seen a variety of specific summations that have an explicit formula. In this section, we look at several common classes of summations that have an explicit formula. We begin with an activity.

Activity 9.5.C Special sums.

 
  1. Consider a real number \(r \neq 1\) and the sum
    \begin{equation*} S = \sum_{k=0}^4r^k = 1 + r + r^2 + r^3 + r^4\text{.} \end{equation*}
    Note that \(S\) is a function of \(r\text{.}\) Evaluate \(S\) when \(r = 10\text{.}\)
  2. Expand \((r-1)S\) and simplify your answer.
  3. Use your answer to (b) to find a formula for \(S\) in terms of \(r\text{.}\) Hint: Since \(r \neq 1\text{,}\) you may divide both sides of your equation by \(r-1\text{.}\)
  4. Use your formula from (c) to evaluate \(S\) when \(r=10\text{.}\) Check that you get the same answer as in (a).
  5. Conjecture an explicit formula for \(\displaystyle \sum_{k=0}^nr^k = 1 + r + r^2 + \ldots + r^n\) when \(r \neq 1\text{.}\)
  6. Use your formula from (e) to show that \(\displaystyle \sum_{k=0}^n2^k = 2^{n+1}-1\text{.}\)
  7. In the Handshakes puzzle Activity 1.1.A, we saw a formula for the sum of the first \(n\) integers, namely Theorem 1.1.4, which says
    \begin{equation*} \sum_{k=1}^nk=\frac{n(n+1)}{2}\text{.} \end{equation*}
    Use this formula to evaluate \(\displaystyle \sum_{k=1}^{10}k\text{.}\)
  8. There is an explicit formula for the sum of the first \(n\) integers squared, namely
    \begin{equation*} \sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}\text{.} \end{equation*}
    Use this formula to evaluate \(\displaystyle \sum_{k=1}^{5}k^2\text{.}\)
  9. Check your answer to (h) by evaluating \(\displaystyle \sum_{k=1}^{5}k^2\) directly.
  10. Conjecture a formula for \(\displaystyle \sum_{k=1}^nk^3\) by considering the first few partial sums. Hint: Each partial sum is a square. What is the pattern in the integers being squared?
Make sure you complete Activity 9.5.C because we are about to reveal many of the answers.

Example 9.5.7 Finite geometric sum conjecture.

Consider real numbers \(a\) and \(r \neq 1\) and the sum
\begin{equation*} S = \sum_{k=0}^6 ar^k = a + ar + ar^2 + ar^3 + ar^4 + ar^5 + ar^ 6\text{.} \end{equation*}
Note that \(S\) is a function of \(a\) and \(r\text{.}\)
  1. Evaluate \(S\) when \(a=3\) and \(r=2\text{.}\)
    Solution.
    We get
    \begin{equation*} S = \sum_{k=0}^6 3 \cdot 2^k = 3 + 3 \cdot 2 + 3 \cdot 2^2 + 3 \cdot 2^3 + 3 \cdot 2^4 + 3 \cdot 2^5 + 3 \cdot 2^ 6= 381\text{.} \end{equation*}
  2. Expand \((r-1)S\) and simplify your answer.
    Solution.
    We get
    \begin{align*} (r-1)S \amp = (r-1)(a + ar + ar^2 + ar^3 + ar^4 + ar^5 + ar^ 6)\\ \amp = (ar + ar^2 + ar^3 + ar^4 + ar^5 + ar^6 + ar^ 7) - (a + ar + ar^2 + ar^3 + ar^4 + ar^5 + ar^ 6)\\ \amp = \cancel{ar} + \cancel{ar^2} + \cancel{ar^3} + \cancel{ar^4} + \cancel{ar^5} + \cancel{ar^6} + ar^7 - a - \cancel{ar} - \cancel{ar^2} - \cancel{ar^3} - \cancel{ar^4} - \cancel{ar^5} - \cancel{ar^ 6})\\ \amp = ar^7-a\\ \amp = a(r^7-1) \end{align*}
    Thus, \((r-1)S = a(r^7-1)\text{.}\)
  3. Use your answer to (b) to find a formula for \(S\) in terms of \(a\) and \(r\text{.}\)
    Solution.
    Since \(r \neq 1\text{,}\) we can divide each side of the equation by \(r-1\) to get \(\displaystyle S = \frac{a(r^7-1)}{r-1}\text{.}\)
  4. Use your formula from (b) to evaluate \(S\) when \(a = 3\) and \(r=2\text{.}\) Check that you get the same answer as in (a).
    Solution.
    We get \(\displaystyle S = \frac{3(2^7-1)}{2-1}= 3(127) = 381\text{.}\)
  5. Conjecture an explicit formula for \(\displaystyle \sum_{k=0}^nar^k = a + ar + ar^2 + \ldots + ar^n\) when \(r \neq 1\text{.}\)
    Solution.
    We conjecture that \(\displaystyle \sum_{k=0}^nar^k = \frac{a(r^7-1)}{r-1} = a\frac{r^7-1}{r-1}\text{.}\)
  6. Use your formula from (e) to show that \(\displaystyle \sum_{k=0}^n4\cdot5^k = 5^{n+1}-1\text{.}\)
    Solution.
    We get \(\displaystyle \sum_{k=0}^n4\cdot5^k = 4\frac{5^{n+1}-1}{5-1}= \cancel{4}\frac{5^{n+1}-1}{\cancel{4}} = 5^{n+1} - 1\text{.}\)
Let’s state the general formula for a geometric sum.
Here is an example using the finite geometric sum formula.

Example 9.5.9 Using the finite geometric sum formula.

Use the finite geometric sum formula Theorem 9.5.8 to evaluate
\begin{equation*} \displaystyle \sum_{k=0}^7(10\cdot2^k)=10 + 20 + 40 + \ldots + 1280. \end{equation*}
Solution.
Our sum is geometric with \(a=10\text{,}\) \(r=2 \neq 1\text{,}\) and \(n=7\) so by Theorem 9.5.8 we have
\begin{equation*} \sum_{k=0}^710\cdot2^k = 10 \left(\frac{2^{7+1}-1}{2-1}\right) = 10 \left(\frac{2^8-1}{1}\right) = 10(256-1) = 2,550 \end{equation*}
We can use the distributive property Definition 2.1.20 to derive linearity properties of sums.
We have seen the sum of the first \(n\) integers, the handshake numbers, in many places starting with Activity 1.1.A. There are also formulas for the sum of the first \(n\) squares and cubes.
Here is an example using these formulas.

Example 9.5.12 Using linearity properties and summation formulas.

Use linearity properties and summation formulas to evaluate each sum.
  1. Evaluate \(\displaystyle \sum_{k=1}^{10}k^2=1 + 4 + 9 + \ldots + 100\)
    Solution.
    By Theorem 9.5.11 (c) with \(n=10\) we have
    \begin{equation*} \sum_{k=1}^{10}k^2 = \frac{10(10+1)(2(10)+1)}{6} = \frac{(10)(11)(21)}{6} = 385\text{.} \end{equation*}
  2. Evaluate \(\displaystyle \sum_{k=1}^{10}k= 1 + 2 + 3 + \ldots + 10\)
    Solution.
    By Theorem 9.5.11 (b) with \(n=10\) we have
    \begin{equation*} \sum_{k=1}^{10}k= \frac{10(10+1)}{2} = \frac{(10)(11)}{2} = 55\text{.} \end{equation*}
  3. Evaluate \(\displaystyle \sum_{k=1}^{10}1=\underbrace{1+1+\ldots+1}_{10 \text{ times } }\)
    Solution.
    By Theorem 9.5.11 (a) with \(n=10\) we have \(\displaystyle \sum_{k=1}^{10}1=10\text{.}\) Not sure we really needed a formula here.
  4. Evaluate \(\displaystyle \sum_{k=1}^{10}(3k+1)(k+2)=(4)(3)+(7)(4)+(10)(5) + \ldots + (31)(12)\text{.}\)
    Solution.
    We begin by multiplying (using FOIL) to get \((3k+1)(k+2) = 3k^2+5k+2\text{.}\) Then we can apply the linearity properties of sums Theorem 9.5.10 and our answers from the previous parts to get
    \begin{align*} \sum_{k=1}^{10}(3k+1)(k+2) \amp =\sum_{k=1}^{10} (3k^2+5k+2)\\ \amp = \sum_{k=1}^{10}(3k^2)+\sum_{k=1}^{10}(5k)+\sum_{k=1}^{10}2\\ \amp = 3\left(\sum_{k=1}^{10}k^2\right)+5\left(\sum_{k=1}^{10}k\right)+2\left(\sum_{k=1}^{10}1\right)\\ \amp = 3(385) + 5(55)+2(10) = 1,450 \text{.} \end{align*}

Subsection 9.5.D Algebra: Fraction Arithmetic

Some of our summation formulas involve fractions. Let’s review fraction arithmetic.

Definition 9.5.13 Adding Fractions.

 
  1. For integers \(n\text{,}\) \(m\text{,}\) and \(d\) with \(d \neq 0\text{,}\) the sum of the fractions is given by
    \begin{equation*} \displaystyle \frac{n}{d} + \frac{m}{d} = \frac{n+m}{d}\text{.} \end{equation*}
    For example,
    \begin{equation*} \frac{3}{7} + \frac{2}{7} = \frac{3+2}{7} = \frac{5}{7} \end{equation*}
  2. To add two fractions using (a), we need the two fractions to have the same denominator (common denominator). If two fractions have different denominators, we can replace one or both fractions with equivalent fractions that have a common denominator using Theorem 4.1.14.
Let’s practice working with fractions.

Example 9.5.14 Adding and Subtracting Fractions.

In this example, we only use computational technology to check our answers.
  1. Write as one fraction and simplify \(\displaystyle \frac{3}{4} - \frac{1}{2}\text{.}\)
    Solution.
    We can use 4 as the common denominator.
    \begin{equation*} \displaystyle \frac{3}{4} - \frac{1}{2} = \frac{3}{4} - \frac{2(1)}{2(2)} = \frac{3}{4} - \frac{2}{4} = \frac{3-2}{4} = \frac{1}{4} \end{equation*}
  2. Write as one fraction and simplify \(\displaystyle \frac{1}{2} + \frac{2}{3}\text{.}\)
    Solution.
    We can use \((2)(3) = 6\) as the common denominator.
    \begin{equation*} \displaystyle \frac{1}{2} + \frac{2}{3} = \frac{3(1)}{3(2)} + \frac{2(2)}{2(3)} = \frac{3}{6} + \frac{4}{6} = \frac{3+4}{6} = \frac{7}{6} \end{equation*}
  3. Write as one fraction and simplify \(\displaystyle \frac{5}{3}-2\text{.}\)
    Solution.
    We can rewrite 2 as the fraction \(\frac{2}{1}\) and then use 3 as the common denominator.
    \begin{equation*} \displaystyle \frac{5}{3}-2 = \frac{5}{3}-\frac{2}{1} = \frac{5}{3}-\frac{3(2)}{3(1)} = \frac{5}{3}-\frac{6}{3} = \frac{5-6}{3} = \frac{-1}{3} =^-\frac{1}{3} \end{equation*}
  4. Write as one fraction and simplify \(\displaystyle \frac{1}{k-1} - \frac{1}{k}\text{.}\)
    Solution.
    We can use \(k(k-1)\) as the common denominator.
    \begin{equation*} \displaystyle \frac{1}{k-1} - \frac{1}{k} = \frac{k(1)}{k(k-1)} - \frac{(k-1)(1)}{(k-1)(k)} = \frac{k}{k(k-1)} - \frac{k-1}{(k)(k-1)} \end{equation*}
    \begin{equation*} = \frac{k-(k-1)}{(k)(k-1)} = \frac{k-k+1}{k(k-1)} = \frac{1}{k(k-1)} \end{equation*}
    By the way, it is sometimes useful to reverse this equation to write
    \begin{equation*} \frac{1}{k(k-1)} = \frac{1}{k-1} - \frac{1}{k} \end{equation*}
  5. Write as one fraction and simplify \(\displaystyle \frac{1}{2^{k-1}} + \frac{1}{2^k}\text{.}\)
    Solution.
    Recall that \(2\cdot 2^{k-1} =2^k\) so we can use \(2^k\) as the common denominator.
    \begin{equation*} \displaystyle \frac{1}{2^{k-1}} + \frac{1}{2^k} = \frac{2(1)}{2(2^{k-1})} + \frac{1}{2^k} = \frac{2}{2^k} + \frac{1}{2^k} = \frac{2+1}{2^k} = \frac{3}{2^k} \end{equation*}
  6. Write as one fraction and simplify \(\displaystyle \frac{1}{(n-1)!} + \frac{1}{n!}\text{.}\)
    Solution.
    Recall that \(n!=n(n-1)!\) so we can use \(n!\) as the common denominator to get
    \begin{equation*} \displaystyle \frac{1}{(n-1)!} + \frac{1}{n!} = \frac{n(1)}{n(n-1)!)} + \frac{1}{n!} = \frac{n}{n!} + \frac{1}{n!} = \frac{n+1}{n!} \end{equation*}
Adding or subtracting fractions is a bit complicated because we need to find a common denominator. Luckily, multiplying fractions is simpler.

Definition 9.5.15 Multiplying Fractions.

 
  1. For integers \(n, m, c, d\) with \(c,d \neq 0\text{,}\) the product of the fractions is given by
    \begin{equation*} \frac{m}{c} \cdot \frac{n}{d} = \frac{mn}{cd}\text{.} \end{equation*}
    For example,
    \begin{equation*} \frac{2}{3} \cdot \frac{7}{5} = \frac{(2)(7)}{(3)(5)} = \frac{14}{15}\text{.} \end{equation*}
Here is an example.

Example 9.5.16 Multiplying Fractions.

In this example, we only use computational technology to check our answers.
  1. Write as one fraction and simplify: \(\displaystyle \frac{1}{2} \cdot \frac{5}{6}\text{.}\)
    Solution.
    By Definition 9.5.15,
    \begin{equation*} \frac{1}{2} \cdot \frac{5}{6} = \frac{(1)(5)}{(2)(6)} = \frac{5}{12}\text{.} \end{equation*}
  2. Write as one fraction and simplify \(\displaystyle \frac{1}{2} \cdot \frac{2}{3}\text{.}\)
    Solution.
    We have
    \begin{equation*} \frac{1}{2} \cdot \frac{2}{3} = \frac{(1)(2)}{(2)(3)}= \frac{\cancel{2}(1)}{\cancel{2}(3)}=\frac{1}{3} \end{equation*}
  3. Write as one fraction and simplify \(\displaystyle 5 \cdot \frac{3}{10}\text{.}\)
    Solution.
    To use Definition 9.5.15, we need to write 5 as the fraction \(\frac{5}{1}\text{.}\) Next,
    \begin{equation*} 5 \cdot \frac{3}{10} = \frac{5}{1} \cdot \frac{3}{10} = \frac{(5)(3)}{(1)(10)} = \frac{\cancel{5}(3)}{\cancel{5}(2)} = \frac{3}{2}\text{.} \end{equation*}
  4. Simplify \(\displaystyle 4 \left(\frac{4^m-1}{3}\right)+1\)
    Solution.
    First, we can write 4 as \(\frac{4}{1}\) and multiply the fractions to get
    \begin{equation*} 4 \left(\frac{4^m-1}{3}\right)+1 = \frac{4}{1} \left(\frac{4^m-1}{3}\right)+1 = \frac{4\left(4^m-1\right)}{3}+1\text{.} \end{equation*}
    Next, we can use 3 as the common denominator and write 1 as \(\frac{3}{3}\) to get
    \begin{equation*} \frac{4\left(4^m-1\right)}{3}+1 = \frac{4\left(4^m-1\right)}{3}+\frac{3}{3} = \frac{4\left(4^m-1\right)+3}{3}\text{.} \end{equation*}
    Next, using the distributive property and simplifying we get
    \begin{equation*} \frac{4\left(4^m-1\right)+3}{3} = \frac{4\left(4^m\right)-4(1)+3}{3} =\frac{4\left(4^m\right)-1}{3}\text{.} \end{equation*}
    Last, we can simplify the power of 4 to get
    \begin{equation*} \frac{4\left(4^m\right)-1}{3} = \frac{4^{m+1}-1}{3} \end{equation*}
It is your turn to practice working with fractions.

Activity 9.5.D Fractions.

On this problem, you may only use technology to check your answers.
  1. Write as one fraction and simplify \(\displaystyle \frac{3}{10} - \frac{4}{5}\text{.}\)
  2. Write as one fraction and simplify \(\displaystyle \frac{3}{10} \cdot \frac{5}{6}\text{.}\)
  3. Write as one fraction \(\displaystyle \frac{1}{n}+ \frac{1}{n^2}\text{.}\)
  4. Write as one fraction and simplify \(\displaystyle \frac{1}{2^{k-1}} - \frac{1}{2^k}\)
  5. Write as one fraction and simplify \(\displaystyle 3 \left(\frac{3^m-1}{2}\right)-1\)

Subsection 9.5.E Exercises

Subsubsection Exercises for 9.5.A Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas

1. Practice.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^n(2k -1)=n^2\) for \(n\ge 1\text{.}\)
Check.
Hints: Make sure you use parentheses in \(f(n-1)=(n-1)^2\text{.}\)

2. Practice.

Use mathematical induction to prove that \(\displaystyle \sum_{j=1}^n(2j) = n(n+1)\) for \(n \ge 1\text{.}\)

3. Practice.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^nk(k!) = (n+1)!-1\) for \(n\ge 1\text{.}\) We saw this sum in Activity 9.1.B.
Check.
Hint: To simplify \(n!-1+nn!\text{,}\) first put the factorials together and factor to get
\begin{equation*} n!+nn!-1 = (1+n)n!-1\text{.} \end{equation*}
Now, simplify \((1+n)n!\) using \((1+n)=(n+1)\text{.}\)

4. Practice.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^n4 \cdot 5^k = 5^{n+1}-1\) for \(n\ge 1\text{.}\)
Check.
Hint: To simplify \(5^n-1+4\cdot5^n\text{,}\) first put the powers of five together and factor to get
\begin{equation*} 5^n+4\cdot5^n-1 = 5^n(1+4)-1 = 5^n\cdot5 - 1\text{.} \end{equation*}

5. Practice.

Use mathematical induction to prove that \(\displaystyle \prod_{k=1}^n \left(1 + \frac{1}{k}\right) = n+1\) for \(n\ge 1\text{.}\)
Check.
Hint: Note that \(\displaystyle 1 + \frac{1}{n} = \frac{n}{n} + \frac{1}{n} =\frac{n+1}{n}\text{.}\)

6. Practice.

Use mathematical induction to prove that \(\displaystyle \prod_{j=1}^n(2j) = 2^nn!\) for \(n \ge 1\text{.}\)
Check.
Hint: Note that \(f(n-1) = 2^{n-1}(n-1)!\text{.}\) Simplify \(\left(2^{n-1}(n-1)!\right)(2n)\) by collecting the powers of two and separately collecting the factorial.

7. Practice.

Use mathematical induction to prove that \(\displaystyle\sum_{k=1}^nF_k = F_{n+2}-1\) for \(n \ge 1\) where \(F_n\) are the Fibonacci numbers.
Check.
Hint: Note that \(f(n-1) = F_{n+1}-1\) and that the Fibonacci sequence includes
\begin{equation*} \ldots, F_n, F_{n+1}, F_{n+2}, \ldots \end{equation*}

8. Understand.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^n(4k-1) = n(2n+1)\) for \(n\ge 0\text{.}\)
Check.
Hint: Use two sets of parentheses to evaluate \(f(n-1)\text{.}\)

9. Understand.

Use mathematical induction to prove that \(\displaystyle \sum_{k=0}^n\frac{1}{2^k} = 2 - \frac{1}{2^n}\) for \(n \ge 1\text{.}\)

10. Understand.

Use mathematical induction to prove that \(\displaystyle\sum_{k=1}^nF_k^2= F_nF_{n+1}\) for \(n \ge 1\) where \(F_n\) are the Fibonacci numbers.
Check.
Hints: Note that
\begin{equation*} F_{n-1}F_n + F_n^2 = F_n(F_{n-1} + F_n) \end{equation*}

11. Understand.

Use mathematical induction to prove that \(\displaystyle\sum_{k=1}^n(-1)^{k+1}F_k = 1+(-1)^{n+1}F_{n-1}\) for \(n \ge 1\) where \(F_n\) are the Fibonacci numbers.

12. Understand.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^nk \cdot 2^k = (n-1)2^{n+1}+2\) for \(n \ge 1\text{.}\)
Check.
Hint: Make sure to use parentheses when evaluating \(f(n-1)\text{.}\) Also, note that
\begin{equation*} n2^n + n2^n = 2n2^n=n(2\cdot2^n) \end{equation*}
and
\begin{equation*} n2^{n+1}-2^{n+1}=(n-1)2^{n+1} \end{equation*}

13. Understand.

Use mathematical induction to prove that
\(\displaystyle \sum_{k=0}^n(-1)^kk^2 = (-1)^n ~ \frac{n(n+1)}{2}\) for \(n\ge 0\text{.}\)

14. Understand.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}\) for \(n\ge 1\text{.}\) This exercise proves Theorem 9.5.11 (c).

15. Understand.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^nk^3=\left(\frac{n(n+1)}{2}\right)^2\) for \(n\ge 1\text{.}\) This exercise proves Theorem 9.5.11 (d).

16. Understand.

Use mathematical induction to prove that
\(\displaystyle \sum_{k=1}^n(3k+1)(k+2) = n(n+2)(n+3)\) for \(n\ge 1\text{.}\)

17. Understand.

Use mathematical induction to prove that
\(\displaystyle \sum_{k=1}^n\frac{1}{(2k-1)(2k+1)}=\frac{n}{2n+1}\) for \(n\ge 1\text{.}\)

18. Understand.

Use mathematical induction to prove that \(\displaystyle \sum_{k=1}^n\frac{2}{k(k+1)}=\frac{2n}{n+1}\) for \(n\ge 1\text{.}\)

19. Recap.

Do you know …
  1. What the recursive definitions of partial sums and partial products are?
  2. How to use proof by mathematical induction to verify the explicit formula of a sum or product?

20. Explore.

Use mathematical induction to prove that
\(\displaystyle \sum_{k=0}^nar^k=a\left(\frac{r^{n+1}-1}{r-1}\right)\) for \(n \ge 0\text{.}\) This exercise proves Theorem 9.5.8.

Subsubsection Exercises for 9.5.B Proof Format: Combinatorial Proof of Sums

21. Practice.

Suppose there are \(n\) cats and \(n\) dogs and we want to choose \(n\) animals.
  1. If we picked \(k\) cats, then how many dogs do we need to choose?
  2. How many ways are there to pick \(k\) cats and the rest dogs?
  3. If we picked one favorite animal, how many ways are there to pick the rest? Hint: how many animals are left and how many more do we need?
Check.
  1. \(\displaystyle n-k\)
  2. Hint: Step 1 is to pick \(k\) out of \(n\) cats. Step 2 is to pick \(n-k\) out of \(n\) dogs. Steps multiply.
  3. Hint: There are \(n+n=2n\) animals to start, so after we pick a favorite animal there are \(2n-1\) animals remaining.

22. Understand.

Give a combinatorial proof that
\begin{equation*} \displaystyle \sum_{k=0}^n\binom{n}{k}^2 = \binom{2n}{n} \end{equation*}
for \(n \ge 1\text{.}\) Hint: Suppose there are \(n\) cats and \(n\) dogs and we want to choose \(n\) animals. Condition on \(k=\) the number of cats chosen.
Check.
Hints: Make sure to choose \(n\) animals in total. If you choose \(k\) cats, then you will need to choose \(n-k\) dogs. Look at Theorem 9.4.14.

23. Understand.

Give a combinatorial proof that
\begin{equation*} \sum_{k=1}^nk\binom{n}{k}^2 = n\binom{2n-1}{n-1} \end{equation*}
for \(n \ge 1\text{.}\) Hint: Suppose there are \(n\) cats and \(n\) dogs and we want to choose \(n\) animals including a favorite cat. Condition on \(k=\) the number of cats chosen.
Check.
Hints: Make sure to choose \(n\) animals in total. If you choose \(k\) cats, then you will need to choose \(n-k\) dogs. Also, look at Exercise 21 21.(c).

24. Recap.

Do you know …
  1. How to write a combinatorial proof of a sum?
  2. What the phrase “condition on \(k\)” indicates?

25. Explore.

Give a combinatorial proof that
\begin{equation*} \sum_{k=1}^nk = \binom{n+1}{2} \end{equation*}
for \(n \ge 1\text{.}\) Hint: How many 2-elements subsets does \(S = \{0, 1, 2, \ldots, n\}\) have? Condition on \(k =\) the larger number in the subset. Note that the other number in the subset must come from \(\{0, 1, 2, \ldots, k-1\}\text{.}\)

26. Explore.

Give a combinatorial proof (using Theorem 2.3.13) that
\begin{equation*} \sum_{k=m}^n \binom{k}{m} = \binom{n+1}{m+1} \end{equation*}
for \(m, n \ge 1\text{.}\) Hint: How many \((m+1)\)-element subsets does \(S = \{0, 1, 2, \ldots, n\}\) have? Condition on \(k =\) the largest number in the subset. Note that the other \(m\) numbers in the subset must come from \(\{0, 1, 2, \ldots, k-1\}\text{.}\) This proves the hockey stick conjecture from Example 9.4.18.

27. Explore.

Consider the set \(S = \{0, 1, 2, \ldots, n\}\text{.}\)
  1. How many nonidentity permutations of \(S\) are there? Hint: \(|S|=n+1\text{.}\)
  2. Consider an integer \(k\) with \(0 \le k \le n\text{.}\) How many permutations of \(S\) are there where \(k\) is the largest integer that is not fixed? Hint: Such a permutation has the format
    \begin{equation*} \sigma = \left(\begin{array}{ccccccccccc} 0 \amp 1 \amp 2 \amp \cdots \amp k-1 \amp k \amp k+1 \amp k+2 \amp \cdots \amp n-1 \amp n\\ \underline{~} \amp \underline{~} \amp \underline{~} \amp \cdots \amp \underline{~} \amp \underline{~} \amp k+1 \amp k+2 \amp \cdots \amp n-1 \amp n \end{array} \right) \end{equation*}
    Since \(\sigma(k) \neq k\text{,}\) the choices for \(\sigma(k)\) are \(0, 1, 2, \ldots, k-1\text{.}\) That fills in the blank under \(k\) and leaves \(k\) integers to be arranged into the remaining \(k\) blanks.
  3. Give a combinatorial proof that \(\displaystyle \sum_{k=1}^nk\cdot k! = (n+1)!-1\) for \(n \ge 1\text{.}\) Hint: Use part (a) for one count. For the other count, condition on \(k=\) the largest integer not fixed by the nonidentity permutation and use part (b).

28. Explore.

In Activity 2.1.A, we saw that the number of ways to tile a \(1 \times n\) board using \(1 \times 1\) squares and \(1 \times 2\) dominoes was \(F_{n+1}\text{,}\) where \(F_n\) are the Fibonacci numbers. In this exercise, we use this characterization of the Fibonacci numbers to give a combinatorial proof that
\begin{equation*} \sum_{k = 0}^n \binom{n-k}{k} = F_{n+1} \end{equation*}
  1. We want to tile the \(1 \times n\) board using \(s\) squares and \(k\) dominoes. Note that there are \(k+s\) tiles. In how many ways can we tile the board? Hint: Think of \(k+s\) places to put tiles. Choose which \(k\) places will be dominoes.
  2. Let’s rewrite the answer to 28.(a) using \(k\) and \(n\) (instead of \(s\)). First, explain why \(2k+s=n\text{.}\) Next, solve for \(s\text{.}\) Last, substitute into your answer to 28.(a) to get a count of the number of ways to tile the board using \(k\) dominoes in terms of \(k\) and \(n\text{.}\)
  3. Count the total number of ways to tile the \(1 \times n\) using squares and dominoes by using cases conditioned on \(k=\) the number of dominoes. Since cases add Theorem 2.2.7, your answer should be a summation.

Subsubsection Exercises for 9.5.C Detour: Special Sums

30. Practice.

Use Theorem 9.5.11 to evaluate each sum.
  1. Evaluate \(\displaystyle \sum_{k=1}^{8}k\text{.}\)
  2. Evaluate \(\displaystyle \sum_{k=1}^{8}k^2\text{.}\)
  3. Evaluate \(\displaystyle \sum_{k=1}^{8}k^3\text{.}\)
Check.
  1. Hint: The answer is less than 50.
  2. Hint: The answer is just over 200.
  3. Hint: The answer is just under 1,300.

32. Understand.

Use summation formulas to simplify each of the following expressions. (Yes, each uses summation formulas.)
  1. \(\displaystyle 1 + x + x^2 + \ldots + x^n\)
  2. \(\displaystyle xx^2x^3...x^n\)
Check.
  1. Hint: Use Theorem 9.5.8.
  2. Hint: Write the product as a single power of \(x\) where the exponent is a sum written in sigma notation.

33. Recap.

Do you know …
  1. What the formula is for a finite geometric sum and how to use it?
  2. What the linearity properties of sums say?
  3. How to use the formulas for the sum of the first \(n\) integers, their squares, and their cubes?

34. Explore.

The integer \(b\) is a proper divisor of \(n\) if \(b \mid n\) but \(b \lt n\text{.}\) An integer is perfect if it equals the sum of its proper divisors.
  1. Verify that the integer 28 is perfect.
  2. What is the smallest perfect integer? Justify your answer. That means justify that it’s perfect and also that it’s smallest.
  3. Can a prime number be perfect? Explain.
  4. Show how to use the finite geometric sum formula Theorem 9.5.8 to simplify \(\displaystyle \sum_{k=0}^{p-1}2^k\) where \(p\) is a positive integer.
  5. Suppose \(n = 2^{p-1}q\) where \(q\) is an odd prime. List the divisors of \(n\text{,}\) using \(\ldots\) as needed. Note that \(2^{p-1}q\) is the prime factorization of \(n\text{.}\)
  6. Calculate the sum of the divisors of \(n\) from 34.(e) and use your answer from 34.(d) to simplify your answer.
  7. Note that \(n\) is perfect if the sum of all of the divisors of \(n\) is \(n+n=2n\text{.}\) Suppose \(p\) is prime and \(q=2^p-1\) also happens to be prime. Observe that \(q\) is odd. Consider the integer \(n = 2^{p-1}q\) as before. Use 34.(f) to prove that \(n\) is perfect.

35. Explore.

For readers who have studied calculus, an infinite series is defined as a limit. For example,
\begin{equation*} \sum_{k=1}^\infty (ar^k) = \lim_{n \to \infty} \sum_{k=1}^n (ar^k) \end{equation*}
  1. Use the finite geometric sum formula Theorem 9.5.8 to simplify \(\displaystyle \sum_{k=1}^n (ar^k)\text{.}\)
  2. If \(-1\lt r\lt 1\text{,}\) explain why \(\displaystyle \lim_{n \to \infty} r^{n+1} = 0\text{.}\)
  3. Evaluate \(\displaystyle \sum_{k=1}^\infty (ar^k)\) when \(-1 \lt r \lt 1\text{.}\) Simplify your answer, including multiplying the top and bottom of the your limit by -1 (using Theorem 4.1.14).

Subsubsection Exercises for 9.5.D Algebra: Fraction Arithmetic

36. Practice.

On this problem, do not use computational technology except to check.
  1. Write as one fraction and simplify: \(\displaystyle \frac{3}{4} + \frac{1}{2}\text{.}\)
  2. Write as one fraction and simplify: \(\displaystyle \frac{3}{4} \cdot \frac{2}{7}\text{.}\)

37. Understand.

 
  1. Write as one fraction and simplify: \(\displaystyle \frac{n-1}{2n-1}+\frac{1}{(2n-1)(2n+1)}\text{.}\)
  2. Write as one fraction and simplify: \(\displaystyle \frac{2n-2}{n}+\frac{2}{n(n+1)}\text{.}\)

38. Recap.

Do you know …
  1. How to add and subtract fractions?
  2. Why we need a common divisor to add and subtract fractions?
  3. How to multiply fractions?
PrevTopNext