Chapter 1: Analyzing sequences
Imagine you're undertaking an IQ test and you've been given the following question:
What number should be placed instead of the question mark?
0 1 5 14 30 55 91 ?
Huh. That seems harsh. It's certainly not an arithmetic sequence, nor the primes, nor anything well known. After a few unsuccessful tries to tackle the problem you might look at the difference of the consecutive numbers. 1 minus 0 is 1, 5 minus 1 is 4, 14 minus 5 is 9, 30 minus 14 is 16... Oh! These are the squares of integers! The next square is 72 = 49 and the answer is therefore 91 + 49 which is 140. The problem solved.
If you're a mathematician, you cannot just stop here. What exactly was that sequence? Could you compute the i-th element of the sequence without knowing the previous ones?
Problem 1.1
Let the sequence 0 1 5 14 ... be denoted a. Find the explicit formula for ai.
The solution displays when you hover above it.
You can derive the solution by looking at the first few elements.
The first term is 0 which is 02, the second is 1 = 02 + 12, the third is 5 = 1 + 22 = 02 + 12 + 22. And so on. This could be written compactly using the sum notation as: Σk=0i k2.
Do not forget that such intuitive analysis is not a proof and unless it's proven you cannot be sure it's true. However proving this statement is not difficult and can be done via mathematical induction.
You can now state that the initial sequence is the series of the squares of natural integers.
But the proven formula seems to be working generally. It appears as if taking the differences of consecutive elements had exactly the opposite effect than the partial summing. Mathematically spoken these two operations seem to be inverses of each other. However before formulating this hypothesis it's always handy to clean up the notation a bit.
The operation described above is usually called forward difference and is denoted as Δ as that's a common symbol for subtraction. With this notation in hand, the hypothesis can be formulated as: ai = Σk=0i-1(Δa)k for any sequence a.
Problem 1.2
Prove or disprove this hypothesis.
The solution displays when you hover above it.
This statement might seem intuitive. It should be quite the same as the previous case. However if you do the proof by induction correctly, you realize that the statement is actually false. The induction step holds, but the base case does not. The reason why it holds for the sequence 0 1 5 ... is that it begins with 0 - an empty sum is by definition 0 and therefore the base case holds.
This hypothesis turns out to be generally false. There are sequences for which the statement is true though - those which start by 0. If you realize this, it's not that hard to fix the statement - just add the first term to all terms as a constant. The final version of equation is this: ai = a0 Σk=0i-1(Δa)k for any sequence a.
If you are familiar with the standard calculus, this might remind you of the classic Don't forget the C term! This is not a coincidence. In fact the calculus of sequences and the calculus of functions are intertwined - the partial sums play the role of Newton integral, forward differences the role of derivatives and the theorem you've just derived is 'the Newton-Leibniz formula of sequences.' We will see why this is the case in later chapters.
This formula enables us to compute the original sequence if we know the differences of consecutive terms or if we know the sequence of partial sums. It's enough to solve the IQ test, but otherwise it's very impractical - we still have to compute the sum or calculate the difference. We will see in the next chapter how to overcome this problem.
Problem 1.3
A boy built cubes from wooden blocks. He built a 1×1×1 cube the first day and each other day he extended the side of the cube by one (i.e. the second day he had a cube 2×2×2). How many blocks did he have to buy each day?
The solution displays when you hover above it.
The sequence is ai = i3, the difference is then (Δa)i = 3i2+3i+1. He therefore bought (Δa)i = 3i2+3i+1 blocks on i-th day.