Arithmetic Progression

You want an article? Fine. Don't expect me to enjoy it.

Arithmetic progression

An arithmetic progression, often referred to as an arithmetic sequence or a linear sequence, is a fundamental concept in mathematics. It's a sequence of numbers where the difference between any two consecutive terms is constant. This consistent difference is known as the common difference, a defining characteristic of the progression. For instance, the sequence 5, 7, 9, 11, 13, 15, and so on, is a perfect example of an arithmetic progression, with a common difference of 2. It's elegant in its simplicity, yet surprisingly versatile.

If we denote the initial term of such a progression as $a_1$ and the common difference as $d$ , then the $n$ -th term of the sequence, denoted by $a_n$ , can be precisely calculated using the formula:

$a_n = a_1 + (n-1)d$ .

This formula is the bedrock upon which many calculations involving arithmetic progressions are built. A finite segment of an arithmetic progression is, naturally, a finite arithmetic progression. When we speak of the sum of the terms within such a finite progression, we are referring to an arithmetic series.

History

The story of the arithmetic progression's discovery is, like many historical mathematical anecdotes, tinged with a bit of apocryphal charm. There's a tale, of dubious veracity, about a young Carl Friedrich Gauss. While still in primary school, he supposedly stumbled upon the formula for summing the integers from 1 to $n$ , which is $\frac{n(n+1)}{2}$ , when faced with the task of summing the numbers from 1 to 100. The story goes that he noticed he could pair the first and last numbers (1 + 100 = 101), the second and second-to-last (2 + 99 = 101), and so on. There were 50 such pairs, each summing to 101, leading to the total of $50 \times 101 = 5050$ . While this specific anecdote might be embellished, Gauss certainly wasn't the first to grasp these principles. Similar methods were known in antiquity to esteemed mathematicians like Archimedes, Hypsicles, and Diophantus. The knowledge wasn't confined to one corner of the world, either. In China, Zhang Qiujian explored these concepts, and in India, mathematicians such as Aryabhata, Brahmagupta, and Bhaskara II made significant contributions. Even in medieval Europe, figures like Alcuin, Dicuil, Fibonacci, and Sacrobosco were familiar with these ideas, with even anonymous commentators of the Talmud, known as Tosafists, demonstrating understanding. Some scholars even suggest the origins might stretch back to the Pythagoreans in the 5th century BC. It’s a testament to how fundamental these patterns are to human thought.

Sum

The sum of the terms in a finite arithmetic progression is termed an arithmetic series. Consider, for instance, the sum:

$2 + 5 + 8 + 11 + 14 = 40$

Calculating such sums manually can be tedious, but there's a remarkably efficient shortcut. One can take the number of terms being added (in this case, 5), multiply it by the sum of the first and last numbers in the progression (here, $2 + 14 = 16$ ), and then divide the result by 2. This yields the formula:

$\frac{n(a_1 + a_n)}{2}$

Applying this to our example:

$2 + 5 + 8 + 11 + 14 = \frac{5(2 + 14)}{2} = \frac{5 \times 16}{2} = 40$ .

This elegant formula holds true for any arithmetic progression of real numbers, from the initial term $a_1$ to the final term $a_n$ . For example, even with fractions and negative numbers:

$\left(-\frac{3}{2}\right) + \left(-\frac{1}{2}\right) + \frac{1}{2} = \frac{3\left(-\frac{3}{2} + \frac{1}{2}\right)}{2} = -\frac{3}{2}$ .

The visual representation of this summation is quite striking. Imagine the sequence $2, 5, 8, 11, 14$ . If you write it out again in reverse: $14, 11, 8, 5, 2$ , and then add the corresponding terms vertically, you get $16, 16, 16, 16, 16$ . This consistent sum, 16, is precisely the sum of the first and last terms ( $2 + 14$ ). Multiplying this constant sum by the number of terms (5) gives $16 \times 5 = 80$ . Since this is the sum of the sequence added to itself, dividing by 2 gives the actual sum of the original sequence: $80 / 2 = 40$ . It's a proof without words of the arithmetic progression formulas, using a rotated copy of the blocks, as it were.

Derivation

The derivation of the sum formula, $S_n = \frac{n}{2}[2a + (n-1)d]$ , is straightforward. We begin by writing the sum $S_n$ in its natural order:

$S_n = a + a_2 + a_3 + \dots + a_{(n-1)} + a_n$

Substituting the general form of the terms ( $a_k = a + (k-1)d$ ):

$S_n = a + (a+d) + (a+2d) + \dots + (a+(n-2)d) + (a+(n-1)d)$ .

Next, we write the same sum in reverse order:

$S_n = (a+(n-1)d) + (a+(n-2)d) + \dots + (a+2d) + (a+d) + a$ .

Now, if we add these two equations term by term, something remarkable happens. Each pair of corresponding terms sums to the same value:

$(a) + (a+(n-1)d) = 2a + (n-1)d$ $(a+d) + (a+(n-2)d) = 2a + (n-1)d$ ... and so on.

There are $n$ such pairs, each summing to $2a + (n-1)d$ . So, the sum of the two equations is $2S_n$ . Therefore:

$2S_n = n[2a + (n-1)d]$

Dividing by 2 gives the formula:

$S_n = \frac{n}{2}[2a + (n-1)d]$ .

This formula can be elegantly rearranged. Notice that $2a$ can be written as $a + a$ . So,

$S_n = \frac{n}{2}[a + a + (n-1)d]$ .

Since $a + (n-1)d$ is simply the last term, $a_n$ , we arrive at the more common form:

$S_n = \frac{n}{2}(a + a_n)$ ,

which is the sum of the initial and last terms multiplied by half the number of terms.

Furthermore, the average value of the terms in an arithmetic progression can be easily found by dividing the sum $S_n$ by the number of terms $n$ :

$\overline{a} = \frac{S_n}{n} = \frac{a_1 + a_n}{2}$ .

This is precisely the average of the first and last terms, which makes intuitive sense given the uniform spacing of the terms. This formula is strikingly similar to the mean of a discrete uniform distribution, which is no coincidence if you consider the arithmetic progression as a set of equally probable outcomes.

Product

Calculating the product of the terms in a finite arithmetic progression requires a bit more mathematical machinery. If we have an arithmetic progression starting with $a_1$ , a common difference $d$ , and $n$ terms in total, the product $P_n$ is given by:

$P_n = a_1 a_2 a_3 \cdots a_n = \prod_{k=0}^{n-1}(a_1 + kd)$ .

This can be expressed using the Gamma function as:

$P_n = d^n \frac{\Gamma(\frac{a_1}{d} + n)}{\Gamma(\frac{a_1}{d})}$

This formula, however, has a caveat: it's not valid when $a_1/d$ is negative or zero.

This is a generalization of simpler, well-known products. For instance, the product of the first $n$ positive integers, $1 \times 2 \times \cdots \times n$ , is simply the factorial $n!$ . Similarly, the product of a sequence of consecutive integers from $m$ to $n$ , i.e., $m \times (m+1) \times \cdots \times n$ , can be expressed using factorials as $\frac{n!}{(m-1)!}$ .

Derivation

The derivation of the product formula involving the Gamma function starts by factoring out the common difference $d$ from each term in the product:

$a_1 a_2 a_3 \cdots a_n = \prod_{k=0}^{n-1}(a_1 + kd)$

$= \prod_{k=0}^{n-1} d\left(\frac{a_1}{d} + k\right)$

$= d\left(\frac{a_1}{d}\right) \cdot d\left(\frac{a_1}{d}+1\right) \cdot d\left(\frac{a_1}{d}+2\right) \cdots d\left(\frac{a_1}{d}+(n-1)\right)$

$= d^n \prod_{k=0}^{n-1}\left(\frac{a_1}{d} + k\right)$

The product term $\prod_{k=0}^{n-1}\left(\frac{a_1}{d} + k\right)$ is known as the rising factorial, often denoted as $(\frac{a_1}{d})^{\overline{n}}$ . The rising factorial has a relationship with the Gamma function:

$x^{\overline{n}} = \frac{\Gamma(x+n)}{\Gamma(x)}$ .

Therefore, substituting this back into the equation, we get:

$a_1 a_2 a_3 \cdots a_n = d^n \frac{\Gamma(\frac{a_1}{d} + n)}{\Gamma(\frac{a_1}{d})}$ .

This derivation relies on the recurrence relation of the Gamma function, $\Gamma(z+1) = z\Gamma(z)$ , which allows us to express products of consecutive numbers in terms of Gamma functions. For example, $\Gamma(z+m) = (z+m-1)(z+m-2)\cdots z \Gamma(z)$ . This holds true for positive complex numbers $z$ .

Examples

Example 1

Consider the arithmetic progression $3, 8, 13, 18, 23, 28, \ldots$ . The general term is $a_n = 3 + 5(n-1)$ . To find the product of the first 50 terms, we use the formula with $a_1 = 3$ , $d = 5$ , and $n = 50$ :

$P_{50} = 5^{50} \cdot \frac{\Gamma(\frac{3}{5} + 50)}{\Gamma(\frac{3}{5})} \approx 3.78438 \times 10^{98}$ .

Example 2

The product of the first 10 odd numbers $(1, 3, 5, \ldots, 19)$ can be calculated using the same formula. Here, $a_1 = 1$ , $d = 2$ , and $n = 10$ .

$1 \cdot 3 \cdot 5 \cdots 19 = \prod_{k=0}^{9}(1 + 2k) = 2^{10} \cdot \frac{\Gamma(\frac{1}{2} + 10)}{\Gamma(\frac{1}{2})}$ .

This evaluates to $654,729,075$ .

Standard deviation

The standard deviation ( $\sigma$ ) of an arithmetic progression provides a measure of its dispersion. It's given by the formula:

$\sigma = |d| \sqrt{\frac{(n-1)(n+1)}{12}}$

where $n$ is the number of terms in the progression and $d$ is the common difference. This formula is remarkably similar to the standard deviation of a discrete uniform distribution, reinforcing the idea of the arithmetic progression as a set of equally spaced, equally probable values.

Intersections

When you consider the intersection of two doubly infinite arithmetic progressions, the result is either an empty set or another arithmetic progression. This can be determined using the principles of the Chinese remainder theorem. If you have a family of doubly infinite arithmetic progressions where every pair has a non-empty intersection, then there exists at least one number common to all of them. This property means that infinite arithmetic progressions form a Helly family. However, it's important to note that the intersection of infinitely many infinite arithmetic progressions might result in a single number, rather than another infinite progression.

Amount of arithmetic subsets of length k of the set {1,...,n}

Let $a(n,k)$ represent the number of arithmetic subsets of length $k$ that can be formed from the set $\{1, \ldots, n\}$ . The function $\phi(\eta, \kappa)$ is defined as:

$\phi(\eta, \kappa) = \begin{cases} 0 & \text{if } \kappa \mid \eta \\ \left(\left[\eta \;(\text{mod }\kappa )\right]-2\right)\left(\kappa -\left[\eta \;(\text{mod }\kappa )\right]\right) & \text{if } \kappa \not\mid \eta \end{cases}$

where $[\cdot]$ denotes the floor function or, in this context, the remainder. Then, the number of arithmetic subsets $a(n,k)$ is given by:

$a(n,k) = \frac{1}{2(k-1)}\left(n^{2}-(k-1)n+(k-2)+\phi(n+1,k-1)\right)$

An alternative form is:

$a(n,k) = \frac{1}{2(k-1)}\left((n-1)(n-(k-2))+\phi(n+1,k-1)\right)$

For instance, if we consider $n=7$ and $k=3$ , we'd expect $a(7,3) = 9$ arithmetic subsets of length 3 from the set $\{1, 2, 3, 4, 5, 6, 7\}$ . Let's list them: $\{1, 2, 3\}$ , $\{2, 3, 4\}$ , $\{3, 4, 5\}$ , $\{4, 5, 6\}$ , $\{5, 6, 7\}$ , $\{1, 3, 5\}$ , $\{3, 5, 7\}$ , $\{2, 4, 6\}$ , and $\{1, 4, 7\}$ . It's a neat little combinatorial puzzle.

Arithmetic Progression