Higher-Order Arithmetic Progressions

Summary: Sequences whose $k$-th differences are eventually constant, identified by Euler (§64–§67) as precisely the recurrent series generated by rational functions with denominator $(1-z{)}^{k+1}$. The case $k=1$ is the ordinary arithmetic progression; the case $k=2$ has constant second differences; etc. The figurate numbers (natural, triangular, tetrahedral, …) appear again in Chapter 16 as the leading-column entries of the partition table.

Sources: chapter4, chapter16

Last updated: 2026-05-11

---

Definition

A sequence $A,B,C,D,E,\dots$ is a progression of order $k$ if its $k$-th differences are constant (and its $(k-1)$-st differences are not). For $k=1$ this is an arithmetic progression in the usual sense.

Euler’s framing (§64–§67): such a progression, regarded as the sequence of coefficients of an infinite series $A+Bz+C{z}^2+\cdots$, is a recurrent-series whose recurrence kernel is given by the expansion of $(1-z{)}^{k+1}$.

First order: arithmetic progressions (§64)

The rational function $\frac{a+bz}{(1-\alpha z{)}^2}$ expands as

$a+2\alpha az+3{\alpha }^{2}a{z}^2+4{\alpha }^{3}a{z}^3+\cdots +bz+2\alpha b{z}^2+3{\alpha }^{2}b{z}^3+\cdots$

so that the coefficient of $z^n$ is $(n+1){\alpha }^{n}a+n{\alpha }^{n-1}b$ (source: chapter4, §64). Setting $\alpha =z=1$ produces the arithmetic progression $a,2a+b,3a+2b,4a+3b,\dots$, whose first differences are the constant $a+b$.

Because $(1-\alpha z{)}^2=1-2\alpha z+{\alpha }^2{z}^2$, the recurrence is $C=2\alpha B-{\alpha }^{2}A$ (source: chapter4, §64). Specialized to $\alpha =1$: $C=2B-A$, i.e. every arithmetic progression satisfies $C-B=B-A$.

Second order (§65)

$\frac{a+bz+c{z}^2}{(1-\alpha z{)}^3}$ has coefficient of $z^n$ equal to

$\frac{(n+1)(n+2)}{1\cdot 2}{\alpha }^{n}a+\frac{n(n+1)}{1\cdot 2}{\alpha }^{n-1}b+\frac{(n-1)n}{1\cdot 2}{\alpha }^{n-2}c.$

With $\alpha =z=1$ this is a second-order progression — second differences are constant, equal to $a+b+c$. The recurrence, read off $(1-z{)}^3=1-3z+3z^2-z^3$, is $D=3C-3B+A$ (source: chapter4, §65).

Third order (§66)

$\frac{a+bz+c{z}^2+d{z}^3}{(1-\alpha z{)}^4}$ gives a third-order progression with recurrence kernel $(1-z{)}^4=1-4z+6z^2-4z^3+z^4$:

$E=4D-6C+4B-A.$

The explicit coefficient of $z^n$ is

$\left(\genfrac{}{}{0ex}{}{n+3}{3}\right){\alpha }^{n}a+\left(\genfrac{}{}{0ex}{}{n+2}{3}\right){\alpha }^{n-1}b+\left(\genfrac{}{}{0ex}{}{n+1}{3}\right){\alpha }^{n-2}c+\left(\genfrac{}{}{0ex}{}{n}{3}\right){\alpha }^{n-3}d$

(Euler writes this as $(n+1)(n+2)(n+3)/(1\cdot 2\cdot 3)\cdot {\alpha }^{n}a+\cdots$) (source: chapter4, §66).

General order (§67)

Every progression of order $m$ — every sequence whose $m$-th differences are constant — is a recurrent series. The generating denominator is $(1-z{)}^{m+1}$, and the recurrence kernel is the expansion of this denominator. The key combinatorial identity is

$0=a^m-\left(\genfrac{}{}{0ex}{}{n}{1}\right)(a+b{)}^m+(\genfrac{}{}{0ex}{}{n}{2})(a+2b{)}^m-\left(\genfrac{}{}{0ex}{}{n}{3}\right)(a+3b{)}^m+\cdots \pm (a+nb{)}^m,$

valid whenever $n=m+1$, i.e. the $(m+1)$-st difference of $(a+kb{)}^m$ vanishes (source: chapter4, §67). Equivalently: $a^m+(a+b{)}^m+(a+2b{)}^m+\cdots$ is a recurrent series of order $m+1$.

Use in Chapter 16 — columns of the partition table

The column-$m$ generating function for the partition table (number of partitions of $n$ into parts $\le m$) is

$\frac{1}{(1-z)(1-z^2)\cdots (1-z^m)},$

which Euler relates to the figurate numbers in §319–§322:

• Column II ($m=2$): $1/[(1-z)(1-z^2)]=(1+z)/(1-z{)}^2(1+z)$ — after correction by an averaging step, the entries reduce to the natural numbers $1,2,3,4,\dots$.
• Column III ($m=3$): $1/[(1-z)(1-z^2)(1-z^3)]=(1+z)(1+z+z^2)/(1-z{)}^3$ — the leading behaviour is the triangular numbers $\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)$.
• Column IV ($m=4$): the leading entries are the tetrahedral numbers $\left(\genfrac{}{}{0ex}{}{n+3}{3}\right)$ (third-order progression).
• Column $m$ in general: leading entries are $\left(\genfrac{}{}{0ex}{}{n+m-1}{m-1}\right)$ (a progression of order $m-1$).

Euler’s §322 schemes display the explicit additive ladders that recover each column’s entries from those of the simpler (geometric-number) leading progression.

Remarks

• The recurrence kernel $(1-z{)}^{m+1}={\sum }_k(\genfrac{}{}{0ex}{}{m+1}{k})(-z{)}^k$ is exactly the finite-difference operator ${\Delta }^{m+1}$ applied to the sequence; constant $m$-th differences means ${\Delta }^{m+1}$ annihilates the sequence. Euler observes the algebraic fact without yet naming the difference operator.
• These higher-order progressions are the coefficient sequences of $(1-z{)}^{-k}$ — i.e. polynomial functions of $n$ with leading term $n^{k-1}/(k-1)!$.
• Because every progression of order $\le k$ is killed by $(1-z{)}^{k+1}$, the properties derived for a given order automatically hold for all lower orders (source: chapter4, §65 remark).

Related pages

• recurrent-series
• geometric-series
• binomial-series
• chapter-4-on-the-development-of-functions-in-infinite-series
• partition-recurrence
• partition-generating-functions
• chapter-16-on-the-partition-of-numbers