Skip to main content

Section 9.1 Modeling with Sums and Products

We start this section with two activities that involve modeling with sums. Next, we look at modeling with sums and products and introduce a notation for writing general sums and products without using ellipses (\(\ldots\)).

Subsection 9.1.A Counting Squares

We begin with an activity that involves a sum.

Activity 9.1.A Counting Squares.

 
  1. How many squares appear on the standard chessboard as drawn in Figure 9.1.2? Hint: There are 64 \(1 \times 1\) squares, one \(8 \times 8\) squares, and many more squares of other sizes. Show the steps of your calculation in an organized manner and clearly indicate your final answer.
    Figure 9.1.2. The standard chessboard.
  2. Conjecture the number of squares on an \(n \times n\) chessboard.
Let’s take a closer look at Activity 9.1.A.

Example 9.1.3 Counting \(\times 5\) squares.

How many \(5 \times 5\) squares are there on the \(8 \times 8\) chessboard?
Solution.
Think of taking a \(5 \times 5\) square and moving it around on top of the \(8 \times 8\) square. If we start with a the \(5 \times 5\) square in the upper left hand corner, we can move it one, two, or three units to the right. That is, there are four \(5 \times 5\) squares that fit along the top row. If we move it down one unit, there are also four \(5 \times 5\) squares that fit one row down. Similarly, there are four \(5 \times 5\) squares that fit two rows down and four \(5 \times 5\) squares that fit three rows down. That is the furthest we can go, so there are \(4+4+4+4=16\) different \(5 \times 5\) squares.
There is a more sophisticated way to count. We can create a pairing between each possible \(5 \times 5\) squares and its upper left-hand corner, which is a \(1 \times 1\) square. Which \(1 \times 1\) squares can be the upper left-hand corner of a \(5 \times 5\) square? The answer is any \(1 \times 1\) squares in the \(4 \times 4\) square that sits in the upper left-hand corner of the \(8 \times 8\) chessboard. (If we try to put the upper left-hand corner of the \(5 \times 5\) square anywhere else on the chessboard, then the \(5 \times 5\) square will not fit.) Because we have a pairing, the number of \(5 \times 5\) squares equals the number of \(1 \times 1\) squares in the \(4 \times 4\) square that sits in the upper left-hand corner of the \(8 \times 8\) chessboard. Since any \(4 \times 4\) square has exactly \(4^2=16\) of the \(1 \times 1\) squares, the answer again is \(4^2=16\text{.}\)

Subsection 9.1.B Factorial Representations

In this puzzle, we represent an integer by writing it as the sum of factorials.

Activity 9.1.B Factorial Representations Puzzle.

As a reminder, the first few factorial are listed in Table 9.1.5.
Table 9.1.5. The values of \(n!\) for \(n=1,2, \ldots 8\)
\(1! = 1\) \(2! = 2\) \(3! = 6\) \(4! = 24\)
\(5! = 120\) \(6! = 720\) \(7! =\) 5,040 \(8! =\)40,320
Every positive integer can be written as the sum of factorials. For example, we can write 10 using \(3!=6\text{,}\) \(2!=2\text{,}\) and \(1!=1\) in several ways, including
\begin{align*} 10 \amp = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1\\ \amp = 2 + 2 + 1 + 1 + 1 + 1\\ \amp = 6 + 2 + 1 + 1\\ \amp = 6 + 2 + 2 \end{align*}
The last line uses the fewest factorials. When we write the positive integer \(n\) using the fewest factorials, that is the factorial representation of \(n\text{.}\)
There is a handy shorthand for this notation. For example, the factorial representation of 10 is
\begin{equation*} 10 = 6 + 2 + 2 = \underline{1} \cdot 3! + \underline{2} \cdot 2! + \underline{0} \cdot 1! =(120)_! \end{equation*}
For example,
\begin{equation*} (10320)_! = \underline{1} \cdot 5! + \underline{0} \cdot 4! + \underline{3} \cdot 3! + \underline{2} \cdot 2! + \underline{0} \cdot 1! = 120 + 3(6) + 2(2) = 142\text{.} \end{equation*}
  1. Evaluate \((1201)_!\)
  2. Evaluate \((1000)_!\) and \((10000)_!\text{.}\) What do you notice?
  3. Find the factorial representation of 5, 20, and 132.
  4. A classmate is writing the factorial representation of 27 and her answer is
    \begin{equation*} 27 = 6 + 6 + 6 + 6 + 2 + 1 = \underline{4} \cdot 3! + \underline{1} \cdot 2! + \underline{1}\cdot 1! = (411)_! \end{equation*}
    Explain why this answer is incorrect and calculate the correct answer.
  5. What is the largest multiple of 3! you could have in the factorial representation of an integer? Explain.
  6. Let’s generalize. What is the largest number of \(k!\) you could have in the factorial representation of an integer?
  7. Here is a different question. What is the largest integer whose factorial representation uses up to 4!? Evaluate your answer.
  8. What is the largest integer whose factorial representation uses up to 5!? Evaluate your answer.
  9. What is the largest integer whose factorial representation uses up to \(k!\text{?}\) Write your answer as a sum.
  10. Find an explicit formula for the largest integer whose factorial representation uses up to \(k!\) (Hint: It involves a factorial. Look back at your answers to (g) and (h).)
Let’s take a closer look at some of our findings in Activity 9.1.B.

Example 9.1.6 Factorial representation.

Consider the factorial representation of an integer introduced in Activity 9.1.B.
  1. Calculate the factorial representations of 17 and of 100.
    Solution.
    First,
    \begin{equation*} 17 = 6 + 6 + 2 + 2 +1 = \underline{2} \cdot 3! + \underline{2} \cdot 2! + \underline{1} \cdot 1! = (221)_! \end{equation*}
    Next,
    \begin{equation*} 100 = 24 + 24 + 24 + 24 + 2 + 2 = \underline{4} \cdot 4! + \underline{0} \cdot 3! + \underline{2} \cdot 2! + \underline{0} \cdot 1! = (4020)_! \end{equation*}
  2. What happens if we calculate the factorial representation of \(5!\text{?}\)
    Solution.
    We get
    \begin{equation*} 5! = \underline{1} \cdot 5! = \underline{1} \cdot 5! + \underline{0} \cdot 4! + \underline{0} \cdot 3! + \underline{0} \cdot 2! + \underline{0} \cdot 1! =(10000)_! \end{equation*}
    which is a 1 followed by four 0s.
  3. What is the largest multiple of \(4!\) you could have in the factorial representation? Explain. Generalize
    Solution.
    We could have \(\underline{4} \cdot 4!\) but we would not have \(\underline{5} \cdot 4!\) because \(5\cdot 4! = (5)(4)(3)(2)(1) = 5!\) The largest multiple of \(4!\) in the factorial representation is four. In general, the largest multiple of \(k!\) in the factorial representation is \(k\) because \((k+1)k!=(k+1)!\)
  4. What is the largest integer whose factorial representation uses up to 5!?
    Solution.
    The largest integer would be
    \begin{equation*} \underline{5} \cdot 5! + \underline{4} \cdot 4! + \underline{3} \cdot 3! + \underline{2} \cdot 2! + \underline{1} \cdot 1! = 5(120)+4(24)+3(6)+2(2)+1(1) =119\text{.} \end{equation*}
    By the way, \(119 = 120-1 = 5!-1\text{.}\)
  5. What is the largest integer whose factorial representation uses up to \(k!\text{?}\)
    Solution.
    We can write the largest integer as the sum
    \begin{equation*} k\cdot k! + (k-1) \cdot (k-1)! + \ldots + 2 \cdot 2! + 1 \cdot 1! \end{equation*}
    which seems more natural to write in reverse order as
    \begin{equation*} 1 \cdot 1! + 2 \cdot 2! + \ldots + (k-1) \cdot (k-1)! +k \cdot k! \end{equation*}
We can now state the definition of the factorial representation.

Definition 9.1.7 Factorial representation.

For a positive integer \(n\text{,}\) the factorial representation of \(n\) is
\begin{equation*} n= (a_ka_{k-1}\dots a_3a_2a_1)_! \end{equation*}
if
\begin{equation*} n = a_kk!+a_{k-1}(k-1)! + \ldots a_33! + a_22! + a_11! \end{equation*}
for some integer \(k\) where each integer \(a_i=1, 2, \ldots, i\text{.}\)

Subsection 9.1.C Sum and Product Notation

In Activity 9.1.A and Activity 9.1.B, we saw the sums \(1^2+3^2+3^2+ \ldots + 8^2\) and
\begin{equation*} 1 \cdot 1! + 2 \cdot 2! + \ldots + (k-1) \cdot (k-1)! +k \cdot k! \end{equation*}
In our work with exponentials and factorials, we saw the products
\begin{equation*} 2^n = \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n \text{ times } }\text{.} \end{equation*}
and
\begin{equation*} n! = (n)(n-1)\cdots(3)(2)(1) \end{equation*}
There is a standard notation for sums and products.

Definition 9.1.8 Sum and product notation.

Consider a (finite) list of numbers
\begin{equation*} a_s, a_{s+1}, a_{s+2}, \ldots, a_n \end{equation*}
for some integers \(s\) and \(n\text{.}\)
  1. We can abbreviate their sum using summation (Sigma) notation:
    \begin{equation*} \sum_{k=s}^n a_k =a_s + a_{s+1}+a_{s+2}+\ldots+a_n \end{equation*}
    which is pronounced “the sum from \(s\) to \(n\) of \(a\) sub \(k\)”. For example, our answer to Activity 9.1.A is
    \begin{equation*} \sum_{k=1}^8 k^2 =1^2+2^2+3^2+ \ldots + 8^2 = 204\text{.} \end{equation*}
  2. We can abbreviate their product using product (Pi) notation:
    \begin{equation*} \prod_{k=s}^n a_k =a_s \cdot a_{s+1} \cdot a_{s+2} \cdot \cdots \cdot a_n \end{equation*}
    which is pronounced “the product from \(s\) to \(n\) of \(a\) sub \(k\)”. For example,
    \begin{equation*} \prod_{k=1}^5 k =1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 5! = 120\text{.} \end{equation*}
  3. The numbers we add in a sum are the terms and the numbers we multiply in a product are the factors.
  4. We say the sum or product starts at \(s\text{.}\) Often \(s=0\) or \(s=1\text{.}\)
By the way, the Greek letters \(\Sigma\) (sigma) and \(\Pi\) (pi) are the analogs of the letters S and P, which are the first letters of sum and product, respectively.
Let’s practice evaluating a sum and product.

Example 9.1.9 Summation and product notation.

 
  1. Evaluate \(\displaystyle \sum_{k=1}^4 (-1)^kk\text{.}\)
    Solution.
    This sum starts at \(k=1\) and ends when \(k=4\text{.}\) When \(k=1\text{,}\) we have \((-1)^kk=(-1)^11=-1\text{,}\) when \(k=2\text{,}\) we have \((-1)^kk=(-1)^22=2\text{,}\) when \(k=3\text{,}\) we have \((-1)^kk=(-1)^33=-3\text{,}\) and when \(k=4\text{,}\) we have \((-1)^kk=(-1)^44=4\text{.}\) We add these terms to get the sum
    \begin{equation*} \sum_{k=1}^4 (-1)^kk =\underbrace{(-1)^1\cdot 1}_{k=1}+ \underbrace{(-1)^2\cdot 2}_{k=2}+ \underbrace{(-1)^3\cdot 3}_{k=3}+ \underbrace{(-1)^4\cdot 4}_{k=4} =-1 + 2 - 3 + 4 = 2 \end{equation*}
  2. Evaluate \(\displaystyle \prod_{k=0}^2(5k+1)\text{.}\)
    Solution.
    This product starts at \(k=0\) and ends when \(k=4\text{.}\) When \(k=0\text{,}\) we have \(5k+1=5(0)+1= 1\text{,}\) when \(k=1\text{,}\) we have \(5k+1=5(1)+1 = 6\text{,}\) and when \(k=2\text{,}\) we have \(5k+1=5(2)+1 = 11\text{.}\) We multiply these factors to get the product
    \begin{equation*} \prod_{k=0}^2(5k+1) = \underbrace{1}_{k=0} \cdot \underbrace{6}_{k=1} \cdot \underbrace{11}_{k=2} = 66\text{.} \end{equation*}
  3. Write \(1 + 2 + 3 + \ldots + (n-1)\) using summation notation in a natural way starting at \(k=1\text{.}\)
    Solution.
    Our sum starts at 1 and ends at \(n-1\text{.}\) The terms equal the index so we get
    \begin{equation*} 1 + 2 + 3 + \ldots + (n-1) = \sum_{k=1}^{n-1}k \end{equation*}
Try working with summation and product notation.

Activity 9.1.C Summation and product notation.

 
  1. Evaluate \(\displaystyle \sum_{m=0}^4 (2m+1)\)
  2. Evaluate \(\displaystyle \prod_{m=0}^4 (2m+1)\)
  3. Write the sum
    \begin{equation*} \frac{1}{2} + \frac{4}{3} + \frac{9}{4} + \frac{16}{5}+ \frac{25}{6} \end{equation*}
    using summation notation in a natural way starting at \(k=1\text{.}\)
  4. Write the product
    \begin{equation*} \frac{1}{2} \cdot \frac{3}{4}\cdot \frac{5}{6}\cdot \frac{7}{8} \end{equation*}
    using product notation in a natural way starting at \(k=1\text{.}\)
We can add or multiply numbers from any sequence.

Example 9.1.11 Sums of Fibonacci numbers and binomial coefficients.

 
  1. Recall that the Fibonacci sequence is defined by \(F_0=0\text{,}\) \(F_1=1\text{,}\) and \(F_n=F_{n-1}+F_{n-2}\text{.}\) For example, \(F_2=2, F_3=3, F_5=5, F_6=8, F_7=13\text{,}\) and \(F_8=21\text{.}\) Evaluate \(\displaystyle \sum _{j=1}^8F_{j}^2\text{.}\)
    Solution.
    We have
    \begin{align*} \sum _{j=1}^8F_j^2 \amp = F_j^2 + F_j^2 + F_j^2 + F_j^2 + F_j^2 + F_j^2 + F_j^2 + F_j^2\\ \amp = 1^2 + 1^2 + 2^2 + 3^2 + 5^2 + 8^2 + 13^2 + 21^2\\ \amp = 1 + 1 + 4 + 9 + 25 + 64 + 169 + 441 = 714 \end{align*}
  2. Recall that the binomial coefficients \(\binom{n}{k}\) is the number of \(k\)-element subsets of a set of \(n\) elements. For example,
    \begin{equation*} \binom{4}{0} = 1 \binom{4}{1} = 4 \binom{4}{2} = 6 \binom{4}{3} = 4 \binom{4}{4} = 1 \end{equation*}
    Evaluate \(\displaystyle \sum_{k=0}^4 \binom{4}{k}\) and \(\displaystyle \sum_{k=0}^4 (-1)^4\binom{4}{k}\text{.}\)
    Solution.
    First,
    \begin{align*} \sum_{k=0}^4 \binom{4}{k} \amp = \binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4}\\ \amp = 1+4+6+4+1=16\text{.} \end{align*}
    Next,
    \begin{align*} \sum_{k=0}^4 (-1)^4\binom{4}{k} \amp = (-1)^0\binom{4}{0} + (-1)^1\binom{4}{1} + (-1)^2\binom{4}{2} + (-1)^3\binom{4}{3} + (-1)^4\binom{4}{4}\\ \amp = 1-4+6-4+1=0\text{.} \end{align*}

Subsection 9.1.D Exercises for 9.1.A Counting Squares

1. Practice.

Explain carefully how to calculate the number of \(3\times3\) squares on the standard chessboard in Activity 9.1.A, as an example of your reasoning. Hint: See Example 9.1.3.

2. Understand.

How many squares appear on a \(8\times 16\) board? Show your calculations and explain your reasoning.
Check.
Hint: There are 128 \(1 \times 1\) squares, 105 \(2 \times 2\) squares, …, and 9 \(8 \times 8\) squares for a total of just under 500 squares.

3. Recap.

Do you know …
  1. How to count the number of each size square on a chessboard?
  2. How to create a pairing between the squares of a given size and a set of \(1 \times 1\) squares?

4. Explore.

For the sake of this problem, a double-square is a rectangle made of two squares; that is, one side of the rectangle is twice as long as the other side. How many double-squares appear on the standard \(8 \times 8\) chessboard? Show your calculations and explain your reasoning.
Check.
228 Hint: Squares can appear vertically or horizontally.

Subsection 9.1.E Exercises for 9.1.B Factorial Representations

6. Practice.

 
  1. What is the largest integer whose factorial representation uses up to 6!? Explain your reasoning and calculate an actual number.
  2. Write your answer in terms of a single factorial.
Check.
  1. Hint: The number begins \(\underline{6} \cdot 6! +\ldots\)
  2. Hint: It is one less than a factorial.

8. Understand.

 
  1. How can you tell just by looking at the factorial representation of an integer whether that integer is even or odd? State your answer as a conjecture.
  2. How can you tell just by looking at the factorial representation of an integer whether or not that integer is a multiple of three? State your answer as a conjecture.
Check.
Not sure where to start? Write the factorial representation of 1, 2, 3, …, 12.
  1. Hint: A number is even if and only if the last digit in its factorial representation is \(\underline{\hspace{.25in}}\text{.}\)
  2. Hint: There are two different possibilities that involve the last two digits.

9. Recap.

Do you know …
  1. How to evaluate an integer given in factorial representation?
  2. How to find the factorial representation of an integer?
  3. Why the largest multiple of \(k!\) is \(k\text{?}\)
  4. What the largest integer is that uses only 1!, 2!, 3!, …, \(k!\text{?}\)

10. Explore.

Here is an alternative way to find the factorial representation of the integer 100.
  • 100 \(\fn{div}\) 2 = 50 and 100 \(\fn{mod}\) 2 = 0.
  • 50 \(\fn{div}\) 3 = 16 and 50 \(\fn{mod}\) 3 = 2.
  • 16 \(\fn{div}\) 4 = 4 and 16 \(\fn{mod}\) 4 = 0.
  • 4 \(\fn{div}\) 5 = 0 [STOP] and 4 \(\fn{mod}\) 5 = 4.
  • The factorial representation of 100 = \((4020)_!\text{.}\) Note that we are reading the remainders (\(\fn{mod}\)) from bottom to top.
Use this new process to find the factorial representation of each integer. Show work.
  1. 1,000
  2. 20,000
Check.
Hint: You should get the same answers as in Exercise 8. Make sure your work on that problem follows the process from the puzzle and your work on this problem follows the algorithm.

11. Explore.

Explain why the algorithm introduced in Exercise 10 works in general. Hint: How is the last number in the factorial representation of an integer \(n\) related to \(n\) \(\fn{mod}\) 2? How is the next to last number in the factorial representation of an integer \(n\) related to \(n\) \(\fn{mod}\) 3?

Subsection 9.1.F Exercises for 9.1.C Sum and Product Notation

13. Practice.

Evaluate the sum or product and simplify your answer. Show work.
  1. \(\displaystyle \displaystyle \sum_{m=1}^3(3m-1)\)
  2. \(\displaystyle \displaystyle \prod_{m=1}^3(3m-1)\)
  3. \(\displaystyle \displaystyle \sum_{k=1}^3 k^2\)
  4. \(\displaystyle \displaystyle \prod_{k=1}^3 k^2\)
  5. \(\displaystyle \displaystyle \sum_{i=1}^3i2^i\)
  6. \(\displaystyle \displaystyle \prod_{i=1}^3i2^i\)
Check.
The answers, in some order, are 14, 15, 34, 36, 80, and 384.

14. Understand.

Evaluate the sum or product and simplify your answer.
  1. \(\displaystyle \displaystyle \sum_{i=1}^42\)
  2. \(\displaystyle \displaystyle \prod_{i=1}^42\)
  3. \(\displaystyle \displaystyle \sum_{i=1}^n2\)
  4. \(\displaystyle \displaystyle \prod_{i=1}^n2\)
Check.
  1. Hint: Each term is 2.
  2. Hint: Each factor is 2.
  3. Hint: The sum equals \(\underbrace{2+2+\ldots+2}_{n \text{ times } }\)
  4. Hint: The product equals \(\underbrace{2 \times 2 \times \ldots \times 2}_{n \text{ times } }\)

15. Understand.

Write each sum or product in summation (sigma) or product (pi) notation in a natural way, starting at \(k=1\text{.}\)
  1. \(\displaystyle 4 +7 + 10 + 13 + 16 + 19\)
  2. \(\displaystyle 4 \cdot 7 \cdot 10 \cdot 13 \cdot 16 \cdot 19\)
Check.
Hint: The terms/factors come from a sequence where each term is the previous term plus three, so the explicit formula for the terms/factors involves \(3k\text{.}\)

16. Understand.

Write each sum or product in summation (sigma) or product (pi) notation in a natural way, starting at \(k=1\text{.}\)
  1. \(\displaystyle 1 + 4 + 9 + \ldots + n^2\)
  2. \(\displaystyle 1 \cdot 4 \cdot 9 \cdots n^2\)
  3. \(\displaystyle 1 + r + r^2 + r^3 + \ldots + r^n\)
  4. \(\displaystyle 1 \cdot r \cdot r^2 \cdots r^n\)
Check.
  1. \(\displaystyle \displaystyle \sum_{k=1}^nk^2\)
  2. Hint: Use product notation.
  3. Hint: \(1 = r^0\) and \(r = r^1\text{.}\)
  4. Hint: Use product notation.

17. Understand.

Recall that the Fibonacci sequence is defined by \(F_0=0\text{,}\) \(F_1=1\text{,}\) and \(F_n=F_{n-1}+F_{n-2}\text{.}\) For example, \(F_2=2, F_3=3, F_5=5, F_6=8, F_7=13\text{,}\) and \(F_8=21\text{.}\) Evaluate each sum. Show work.
  1. \(\displaystyle \displaystyle \sum_{k=1}^8F_k\)
  2. \(\displaystyle \displaystyle \sum _{i=1}^8(-1)^iF_{i}\)
Check.
Hint: Each answer is one less than a Fibonacci number.

18. Understand.

Recall that the binomial coefficients \(\binom{n}{k}\) is the number of \(k\)-element subsets of a set of \(n\) elements. For example,
\begin{equation*} \binom{5}{0} = 1 \binom{5}{1} = 5 \binom{5}{2} = 10 \binom{5}{3} = 10 \binom{5}{4} = 5 \binom{5}{5} = 1\text{.} \end{equation*}
Evaluate each sum. Show work.
  1. \(\displaystyle \displaystyle \sum_{k=0}^5 \binom{5}{k}\)
  2. \(\displaystyle \displaystyle \sum_{m=0}^5 \binom{5}{m}^2\)
  3. \(\displaystyle \displaystyle \sum_{k=0}^5 (-1)^i\binom{5}{i}\)
Check.
The answers, in some order, are 0, 32, and 252.

19. Understand.

Evaluate each sum. Show work. Hint: Simplify before you evaluate terms.
  1. \(\displaystyle \displaystyle \sum_{m=1}^9 \left((m+1)!-m!\right)\)
  2. \(\displaystyle \displaystyle \prod_{k=1}^9 \frac{k}{k+1}\)
  3. \(\displaystyle \displaystyle \sum_{j=2}^9 \left(\frac{1}{j-1}-\frac{1}{j}\right)\)
Check.
Hint: Most terms should cancel.
  1. Hint: You can simplify your answer to involve only one factorial.
  2. Hint: The answer is a fraction with denominator 10.
  3. Hint: The answer is a fraction with denominator 9.

20. Recap.

Do you know …
  1. How to evaluate a sum written in summation (Sigma) notation?
  2. How to evaluate a product written in product (Pi) notation?
  3. How to write a sum or product in summation or product notation?

21. Explore.

In Section 3.2 Exercise 20, we saw the family of trees \(B_n\text{.}\) The trees \(B_1\text{,}\) \(B_2\text{,}\) and \(B_3\) are drawn in Figure 3.3.45. Write each quantity as sum using sigma notation.
  1. The number of vertices in \(B_n\text{.}\) Hint: Add up the vertices in each generation.
  2. The number of edges in \(B_n\text{.}\) Hint: Add up the edges to each generation.
Check.
Check that your answers give the correct answers for \(B_3\) which has 15 vertices and 14 edges.
PrevTopNext