Polynomial Sequences

Section Preview

Investigation

A standard \(8 \times 8\) chessboard contains 64 squares. Actually, this is just the number of unit squares. How many squares of all sizes are there on a chessboard? Start with smaller boards: \(1\times 1\), \(2 \times 2\), \(3\times 3\), etc. Find a formula for the total number of squares in an \(n\times n\) board.

We have seen that arithmetic sequences grow at a constant rate, and so their closed formulas are linear functions. What about sequences that grow faster? What if their rate of change (really the differences between terms) is itself growing at a constant rate?

In we claimed that the triangular numbers, the sum of the first \(n\) positive integers, have closed formula \[T_n = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}\]. So this sequence, whose sequence of differences is arithmetic, is a degree 2 polynomial (a quadratic function).

Our goal in this section is to explore this phenomenon. We will verify that this really is the closed formula for the triangular numbers, extend it to other sequences with arithmetic differences, and then explore sequences that grow at even faster rates.

Summing Arithmetic Sequences: Reverse and Add

Let's find the sum of the first \(n\) positive integers carefully. Call that sum \(T_n\), and write it down twice, once in the usual order and once in reverse order. \[\begin{array}{lccccccccc} & T_n & = & 1 & + & 2 &+ & 3 & + \cdots + & n \\ + & T_n & =& n & + &(n-1)& + & (n-2)& + \cdots + &1 \\\hline & 2T_n & =& n+1 & + & n+1 & + & n+1 &+ \cdots + & n+1 \end{array}\]

We then added the two equations together. The left-hand side is \(2T_n\). On the right-hand side, something great happens: All the terms of the sum are the same! So instead of adding up a bunch of different numbers, we now just add a bunch of the same number. That's a task that multiplication lives for! There are \(n\) terms in the sum, so we get, \[2T_n = n(n+1)\]. Solving for \(T_n\) gives us, \[T_n = \frac{n(n+1)}{2}\], as expected.

This technique will work for any arithmetic sum.

Example

Find the sum: \(2 + 5 + 8 + 11 + 14 + \cdots + 470\).

Solution

The idea is to mimic how we found the formula for triangular numbers. If we add the first and last terms, we get 472. The second term and second-to-last term also add up to 472. To keep track of everything, we might express this as follows. Call the sum \(S\). Then,

\(S =\)	\(2\)	\(+\)	\(5\)	\(+\)	\(8\)	\(+ \cdots +\)	\(467\)	\(+\)	470
\(+ \quad S =\)	\(470\)	\(+\)	\(467\)	\(+\)	\(464\)	\(+ \cdots +\)	\(5\)	\(+\)	2
\(2S =\)	\(472\)	\(+\)	\(472\)	\(+\)	\(472\)	\(+ \cdots +\)	\(472\)	\(+\)	\(472\)

To find \(2S\) then, we add 472 to itself a number of times. What number? We need to decide how many terms (summands) are in the sum. Since the terms form an arithmetic sequence, the \(n\)th term in the sum (counting \(2\) as the 0th term) can be expressed as \(2 + 3n\). If \(2 + 3n = 470\) then \(n = 156\). So \(n\) ranges from 0 to 156, giving 157 terms in the sum. This is the number of 472's in the sum for \(2S\). Thus \[2S = 157\cdot 472 = 74104\].

It is now easy to find \(S\): \[S = 74104/2 = 37052\].

This will work for the sum of any arithmetic sequence. Call the sum \(S\). Reverse and add. This produces a single number added to itself many times. Find the number of times. Multiply. Divide by 2. Done.

Besides finding sums, we can use this technique to find closed formulas for sequences we recognize as sequences of partial sums.

Notice that the closed formula for a sequence that has an arithmetic (i.e., linear) rate of change is a quadratic function. Interesting....

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Higher Degree Polynomials

Since we know how to compute the sum of the first \(n\) terms of arithmetic sequences, we can compute the closed formulas for sequences that have an arithmetic sequence of differences between terms. But what if we consider a sequence that is the sum of the first \(n\) terms of a sequence that is itself the sum of an arithmetic sequence?

How many squares (of all sizes) are there on a chessboard? A chessboard consists of \(64\) squares, but we also want to consider squares of longer side length. Even though we are only considering an \(8 \times 8\) board, there is already a lot to count. So instead, let us build a sequence: the first term will be the number of squares on a \(1 \times 1\) board, the second term will be the number of squares on a \(2 \times 2\) board, and so on. After a little thought, we arrive at the sequence \[1,5,14,30, 55,\ldots\].

This sequence is not arithmetic (or geometric for that matter), but perhaps its sequence of differences is. For differences we get \[4, 9, 16, 25, \ldots\].

Not a huge surprise: One way to count the number of squares in a \(4 \times 4\) chessboard is to notice that there are \(16\) squares with side length 1, 9 with side length 2, 4 with side length 3 and 1 with side length 4. So the original sequence is just the sum of squares. Now this sequence of differences is not arithmetic since its sequence of differences (the differences of the differences of the original sequence) is not constant. In fact, this sequence of second differences is \[5, 7, 9, \ldots\], which is an arithmetic sequence (with constant difference 2). Notice that our original sequence had third differences (that is, differences of differences of differences of the original) constant. We will call such a sequence \(\Delta^3\)-constant. The sequence \(1, 4, 9, 16, \ldots\) has second differences constant, so it will be a \(\Delta^2\)-constant sequence. In general, we will say a sequence is a \(\Delta^k\)-constant \(\Delta^k\) the \(k\)th differences of a sequence sequence if the \(k\)th differences are constant.

Example

Which of the following sequences are \(\Delta^k\)-constant for some value of \(k\)?

1. \(2, 3, 7, 14, 24, 37,\ldots\)
2. \(1, 8, 27, 64, 125, 216, \ldots\)
3. \(1,2,4,8,16,32,64,\ldots\)

Solution

1. \(1,4,7, 10, 13,\ldots\)\(3,3,3,3,\ldots\)\(2, 3, 7, 14, 24, 37,\ldots\)\(\Delta^2\)
2. \(7, 19, 37, 61, 91, \ldots\)\(12, 18, 24, 30,\ldots\)\(6,6,6,\ldots\)\(\Delta^3\)
3. \(1,2,4,8,16,\ldots\)\(\Delta^k\)\(k\)

This works in general:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Solving Systems of Equations with Technology

The point of polynomial fitting is that if we can be sure that a sequence has a polynomial as its closed formula, then we can find that formula. Since we know the degree of the polynomial, all we need is to find its coefficients, and with enough terms of the sequence, we can find a system of enough linear equations whose solution will be those coefficients. However, this requires solving a system of linear equations.

For a degree 2 polynomial, we need to find three coefficients (the constant term, the coefficient of \(n\), and the coefficient of \(n^2\)). A system of three linear equations will be enough to find these three unknowns. In fact, since \(a_0\) will be the constant term, we can really get away with just two equations and two unknowns, and this is not difficult to solve by hand.

For higher degree polynomials, the number of equations is larger, and solving by hand can be tedious. Luckily, it is easy for computers to solve these equations. Below we demonstrate how to use the free computer algebra system SageMath, as well as python, to solve these systems of equations. Besides these two choices, pretty much any computer algebra system (including Wolfram Alpha) can solve these systems of equations.

Suppose we have the following system of three equations and three unknowns, as in the chess board example above: \[\begin{aligned}1 = \amp a + b + c \\ 5 = \amp 8a + 4b + 2c \\ 14 = \amp 27a + 9b + 3c\end{aligned}\]

In SageMath, we can use the solve method to solve the system of equations. Here is the code:

This is easier than in python, but python might be more readily available. One way you can solve the system in python is to use the numpy library. In this case, you would create a matrix of coefficients and a vector of constants, and then use the solve method. Here is the code:

An explanation of what is going on here: We create a matrix A of coefficients of the system of equations (not the coefficients of the closed formula we are looking for), \[A = \begin{bmatrix} 1 \amp 1 \amp 1 \\ 8 \amp 4 \amp 2 \\ 27 \amp 9 \amp 3 \end{bmatrix}\] and a vector b for the constants, \[b = \begin{bmatrix} 1 \\ 5 \\ 14 \end{bmatrix}\]. What numpy does is solve the matrix equation \[Ax = b\]. The vector \(x\) that satisfies this matrix equation will be the values of the unknowns in the system (so the vector \([a,b,c]\)).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (17)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Match each sequence on the left with the type of closed formula it might have, on the right.

2. Suppose \((a_n)\) is a sequence whose sequence of differences has a degree 2 polynomial as its closed formula. What can you say about the sequence of partial sums of \((a_n)\)? Explain.

3. What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about after reading this section.

4. Consider the sequence \(10, 13, 16, 19, 22\ldots\) where \(a_1 = 10\).

   1. What is the recursive definition for the sequence?

   2. Give a closed formula for the \(n\)th term of the sequence.

   3. Is 1555 a term in the sequence?

   4. How many terms does the finite sequence \(10, 13, 16, \ldots, 433\) have?

   5. Find the sum: \(10+13+16+\ldots+433\).

   6. Use what you found above to find \(b_n\), the \(n\)th term of \(3, 13, 26, 42, 61, \ldots\)

   Ҷавоби ҷавобро нишон диҳед

   1. \(a_n = a_{n-1}+3\); \(a_1 = 10\).

   2. \(a_n = 7+3n\).

   3. Yes, \(1555 = a_{516}\).

   4. The sequence has 142 terms.

   5. The sum is 31453.

   6. \(b_n = 3 + \frac{(10+7+3n)n}{2}\).

5. Suppose \(a_n = {2n^{2}+3n+2}\text{.}\) Find a closed formula for the sequence of differences by computing \(a_n - a_{n-1}\text{.}\) Simplify your answer as much as possible.

   Ҷавоби ҷавобро нишон диҳед

   \(a_{n-1} = 2(n-1)^2 + 3(n-1) + 2 = {2n^{2}-n+1}\) Thus \(a_n - a_{n-1} = {4n+1}\text{.}\) Note that this is linear (arithmetic).

6. Your friendly neighborhood bodega has a candy machine that gives 7 Skittles to the first customer who puts in a quarter, 10 to the second, 13 to the third, 16 to the fourth, etc. How many candies has the machine given out in total after 20 quarters are put into the machine? After \(n\) quarters?

7. Not to be outdone, the mega-mart across the street has installed a candy machine that gives 4 Skittles to the first customer, 7 to the second, 12 to the third, 19 to the fourth, etc. How many Skittles has the machine given out in total after 20 quarters are put into the machine? After \(n\) quarters?

8. Make up sequences that have

   1. 3, 3, 3, 3, as its second differences.
   2. 1, 2, 3, 4, 5, as its third differences.
   3. 1, 2, 4, 8, 16, as its 100th differences.

9. Consider the sequence \(1, 3, 7, 13, 21, \ldots\). Explain how you know the closed formula for the sequence will be quadratic. Then guess the correct formula by comparing this sequence to the squares \(1, 4, 9, 16, \ldots\) (do not use polynomial fitting).

   Ҷавоби ҷавобро нишон диҳед

   \(a_n = n^2 - n + 1\).

10. Use a similar technique as in the previous exercise to find a closed formula for the sequence \(2, 11, 34, 77, 146, 247,\ldots\).

    Ҷавоби ҷавобро нишон диҳед

    \(a_n = n^3 + n^2 - n + 1\)

11. Consider the sequence \(2, 7, 15, 26, 40, 57, \ldots\) (with \(a_0 = 2\)). By looking at the differences between terms, express the sequence as a sequence of partial sums. Then find a closed formula for the sequence by computing the \(n\)th partial sum.

    Ҷавоби ҷавобро нишон диҳед

    We have \(2 = 2\), \(7 = 2+5\), \(15 = 2 + 5 + 8\), \(26 = 2+5+8+11\), and so on. The terms in the sums are given by the arithmetic sequence \(b_n = 2+3n\). In other words, \(a_n = \sum_{k=0}^n (2+3k)\). To find the closed formula, we reverse and add. We get \(a_n = \frac{(4+3n)(n+1)}{2}\) (we have \(n+1\) there because there are \(n+1\) terms in the sum for \(a_n\)).

12. If you have enough toothpicks, you can make a large triangular grid. Below, are the triangular grids of size 1 and of size 2. The size 1 grid requires 3 toothpicks, the size 2 grid requires 9 toothpicks.

    1. Let \(t_n\) be the number of toothpicks required to make a size \(n\) triangular grid. Write out the first 5 terms of the sequence \(t_1, t_2, \ldots\).

    2. Find a recursive definition for the sequence. Explain why you are correct.

    3. Is the sequence arithmetic or geometric? If not, is it the sequence of partial sums of an arithmetic or geometric sequence? Explain why your answer is correct.

    4. Use your results from part (c) to find a closed formula for the sequence. Show your work.

13. If you were to shade in an \(n\times n\) square on graph paper, you could do it the boring way (with sides parallel to the edge of the paper) or the interesting way, as illustrated below:

    The interesting thing here is that a \(3\times 3\) square now has area 13. Our goal is to find a formula for the area of an \(n \times n\) (diagonal) square.

    1. Write out the first few terms of the sequence of areas (assume \(a_1 = 1\), \(a_2 = 5\), etc). Is the sequence arithmetic or geometric? If not, is it the sequence of partial sums of an arithmetic or geometric sequence? Explain why your answer is correct, referring to the diagonal squares.

    2. Use your results from part (a) to find a closed formula for the sequence. Show your work. Note that while there are lots of ways to find a closed formula here, you should use partial sums specifically.

    3. Find the closed formula in as many other interesting ways as you can.

14. Generalize Practice Problem 5: Find a closed formula for the sequence of differences of \(a_n = an^2 + bn + c\). That is, prove that every quadratic sequence has arithmetic differences.

    Ҷавоби ҷавобро нишон диҳед

    \(a_{n-1} = a(n-1)^2 + b(n-1) + c = an^2 - 2an + a + bn - b + c\). Therefore \(a_n - a_{n-1} = 2an - a + b\), which is arithmetic. Notice that this is not quite the derivative of \(a_n\), which would be \(2an + b\), but it is close.

15. Can you use polynomial fitting to find the formula for the \(n\)th term of the sequence 4, 7, 11, 18, 29, 47, ? Explain why or why not.

    Ҷавоби ҷавобро нишон диҳед

    No. The sequence of differences is the same as the original sequence, so no differences will be constant.

16. Will the \(n\)th sequence of differences of \(2, 6, 18, 54, 162, \ldots\) ever be constant? Explain.

    Ҷавоби ҷавобро нишон диҳед

    No. The sequence is geometric, and in fact has closed formula \(2\cdot 3^n\). This is an exponential function, which is not equal to any polynomial of any degree. If the \(n\)th sequence of differences was constant, then the closed formula for the original sequence would be a degree \(n\) polynomial.

17. In their down time, ghost pirates enjoy stacking cannonballs in triangular based pyramids (aka, tetrahedrons), like those pictured here:

    Note: These are solid tetrahedrons, so there will be some cannonballs obscured from view (the picture on the right has one cannonball in the back not shown in the picture, for example).

    The pirates wonder how many cannonballs would be required to build a pyramid 15 layers high (thus breaking the world cannonball stacking record). Can you help?

    1. Let \(P(n)\) denote the number of cannonballs needed to create a pyramid \(n\) layers high. So \(P(1) = 1\), \(P(2) = 4\), and so on. Calculate \(P(3)\), \(P(4)\), and \(P(5)\).

    2. Use polynomial fitting to find a closed formula for \(P(n)\). Show your work.

    3. Answer the pirate's question: How many cannonballs do they need to make a pyramid 15 layers high?

    4. Bonus: Locate this sequence in Pascal's triangle. Why does that make sense?

Symbols used here

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

matrix
A rectangular array of numbers; a linear map.

P(A),\ P(A \mid B)

probability, conditional probability
Chance of A; chance of A given that B happened.

i

imaginary unit
i² = −1.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

\forall,\ \exists

for all, there exists
Quantifiers: every x; at least one x.

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow

not, and, or, implies, iff
Logical connectives.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

O(n^2),\ \Theta,\ \Omega

big-O notation
Grows no faster than n² (up to a constant), for large n.

a \bmod n

remainder
What is left after dividing a by n.

How to: Polynomial Sequences

1. Identify a sequence as having a polynomial closed formula based on its sequence of differences, and determine the polynomial's degree.
2. Fit an appropriate degree polynomial to a sequence of initial terms.
3. Explain how recurrence relations for polynomial sequences relate to their closed formulas.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Санҷиши худ

⌨ Type ✎ Draw

Масъалаи математикии шумо

& Ҷудо кардан

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

& Иловаи забон Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions