A standard 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: ,,, etc. Find a formula for the total number of squares in an 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?
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.
Letβs assume that is even. If it wasnβt, then there would be a single βmiddleβ hook that isnβt added to anything, but this is counteracted by the fact that would count a half hook sum.
SubsectionSumming Arithmetic Sequences: Reverse and Add
Letβs find the sum of the first positive integers carefully. Call that sum , and write it down twice, once in the usual order and once in reverse order.
We then added the two equations together. The left-hand side is . 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 terms in the sum, so we get,
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 . Then,
To find 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 th term in the sum (counting as the 0th term) can be expressed as . If then . So ranges from 0 to 156, giving 157 terms in the sum. This is the number of 472βs in the sum for . Thus
This will work for the sum of any arithmetic sequence. Call the sum . Reverse and add. This produces a single number added to itself many times. Find the number of times. Multiply. Divide by 2. Done.
Again, we have a sum of an arithmetic sequence. How many terms are in the sequence? Clearly each term in the sequence has the form (as evidenced by the last term). For which values of though? To get 6, . To get take . So to find the number of terms, we must count the number of integers in the range . This is . (There are numbers from 1 to , so one less if we start with 2.)
First, if you look at the differences between terms, you get a sequence of differences :, which is an arithmetic sequence. Indeed, we notice that , which agrees with the recurrence relation. Written another way:
and so on. We can write the general term of in terms of the arithmetic sequence as follows:
Since we know how to compute the sum of the first 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 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 squares, but we also want to consider squares of longer side length. Even though we are only considering an 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 board, the second term will be the number of squares on a board, and so on. After a little thought, we arrive at the sequence
Not a huge surprise: One way to count the number of squares in a chessboard is to notice that there are 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
,
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 -constant. The sequence has second differences constant, so it will be a -constant sequence. In general, we will say a sequence is a -constant sequence if the th differences are constant.
This is the sequence from Example 4.3.3, in which we found a closed formula by recognizing the sequence as the sequence of partial sums of an arithmetic sequence. Indeed, the sequence of first differences is , which itself has differences . Thus is a -constant sequence.
These are the perfect cubes. The sequence of first differences is ; the sequence of second differences is ; the sequence of third differences is constant: . Thus the perfect cubes are a -constant sequence.
If we take first differences, we get . Wait, what? Thatβs the sequence we started with. So taking second differences will give us the same sequence again. No matter how many times we repeat this we will always have the same sequence, which in particular means no finite number of differences will be constant. Thus this sequence is not -constant for any .
The -constant sequences are themselves constant, so a closed formula for them is easy to compute (itβs just the constant). The -constant sequences are arithmetic, and we have a method for finding closed formulas for them as well. Every -constant sequence is the sum of an arithmetic sequence, so we can find formulas for these as well. But notice that the format of the closed formula for a -constant sequence is always quadratic. For example, the square numbers are -constant with closed formula . The triangular numbers (also -constant) have closed formula , which when multiplied out gives you an term as well. It appears that every time we increase the complexity of the sequence, that is, increase the number of differences before we get constants, we also increase the degree of the polynomial used for the closed formula. We go from constant to linear to quadratic. The sequence of differences between terms tells us something about the rate of growth of the sequence. If a sequence is growing at a constant rate, then the formula for the sequence will be linear. If the sequence is growing at a rate which itself is growing at a constant rate, then the formula is quadratic. You might have seen this elsewhere: If a function has a constant second derivative (rate of change), then the function must be quadratic.
The closed formula for a sequence will be a degree polynomial if and only if the sequence is -constant (i.e., the th sequence of differences is constant).
This tells us that the sequence of numbers of squares on a chessboard, , which we saw to be -constant, will have a cubic (degree 3 polynomial) for its closed formula.
Now once we know what format the closed formula for a sequence will take, it is much easier to actually find the closed formula. In the case that the closed formula is a degree polynomial, we just need data points to βfitβ the polynomial to the data.
First, check to see if the formula has constant differences at some level. The sequence of first differences is which is arithmetic, so the sequence of second differences is constant. The sequence is -constant, so the formula for will be a degree 2 polynomial. That is, we know that for some constants ,, and ,
Now to find ,, and . First, it would be nice to know what is, since plugging in simplifies the above formula greatly. In this case, (work backward from the sequence of constant differences). Thus
At this point, we have two (linear) equations and two unknowns, so we can solve the system for and (using substitution or elimination or even matrices). We find and , so .
We can find if we know what is. Working backward from the third differences, we find (unsurprisingly, since there are no squares on a chessboard). Thus . Now plug in ,, and :
The sequence of (first) differences is (which agrees with what is given in the recurrence relation). The sequence of second differences is constant! So we expect that the closed formula for will be a degree 2 polynomial. That is, we guess,
As we saw in Example 4.3.4, this sequence is not -constant for any . Therefore the closed formula for the sequence is not a polynomial. In fact, we know the closed formula is , which grows faster than any polynomial (so is not a polynomial).
The sequence of first differences is . The second differences are: . Third differences: . Fourth differences: . As far as we can tell, this sequence of differences is constant so the sequence is -constant, and as such the closed formula is a degree 4 polynomial.
This is the Fibonacci sequence. The sequence of first differences is , the second differences are . We notice that after the first few terms, we get the original sequence back. So there will never be constant differences, so the closed formula for the Fibonacci sequence is not a polynomial.
A degree polynomial is completely determined by its coefficients (the is because of the constant term). Therefore we can always find a degree polynomial when given terms of a sequence.
If we take the terms, we can take differences of differences of differences of... until (after steps) we are left with just a single number. As far as we can tell, this th difference is constant. This doesnβt mean we have found the closed formula for the right sequence. This is why it is so important to work with sequences in a particular context.
SubsectionSolving 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 , and the coefficient of ). A system of three linear equations will be enough to find these three unknowns. In fact, since 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.
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:
import numpy as np
A = np.array([[1,1,1],[8,4,2],[27,9,3]])
b = np.array([1,5,14])
x = np.linalg.solve(A,b)print(x)
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),
and a vector b for the constants,
.
What numpy does is solve the matrix equation
.
The vector that satisfies this matrix equation will be the values of the unknowns in the system (so the vector ).
Of course, once you find the coefficients of the polynomial, you should still write out the closed formula using those coefficients. It is always a good idea to check that the formula appears to work by using an that you did not use to get your system of equations.
Suppose 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 ? Explain.
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.
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 quarters?
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 quarters?
Consider the sequence . 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 (do not use polynomial fitting).
Consider the sequence (with ). 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 th partial sum.
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.
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.
If you were to shade in an 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 square now has area 13. Our goal is to find a formula for the area of an (diagonal) square.
Write out the first few terms of the sequence of areas (assume ,, 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.
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.
Generalize Practice Problem 5: Find a closed formula for the sequence of differences of . That is, prove that every quadratic sequence has arithmetic differences.
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?
Let denote the number of cannonballs needed to create a pyramid layers high. So ,, and so on. Calculate ,, and .