general-term-of-recurrent-series

General Term of a Recurrent Series

Summary: Closed-form expression for the coefficient of $z^n$ in any recurrent series, obtained by decomposing the generating rational function into real partial fractions and summing the general term of each. Two engines: the linear-factor brick $A/(1-pz{)}^k$ gives a polynomial-in-$n$ times $p^n$, and the quadratic-factor brick $(A+Bpz)/(1-2pz\cos \varphi +p^2{z}^2{)}^k$ gives a trigonometric form involving $\sin n\varphi$, $\cos n\varphi$. Chapter 17 inverts the perspective: when only the coefficients of an equation are known, the dominant term in the general term still controls the ratio $Q/P$, which converges to the largest root — see bernoullis-method-for-roots.

Sources: chapter13, chapter17

Last updated: 2026-05-11

---

The strategy (§211–§214)

Let

$\frac{a+bz+c{z}^2+\cdots }{1-\alpha z-\beta z^2-\gamma z^3-\cdots }=A+Bz+C{z}^2+D{z}^3+\cdots$

be a proper rational function expanded as a recurrent series. Decompose the left side by partial fractions (real, using Chapter 12 when the denominator has complex roots), so each piece is one of two types:

• $\frac{A}{(1-pz{)}^k}$ — from a real linear factor $(1-pz{)}^k$ of the denominator,
• $\frac{A+Bpz}{(1-2pz\cos \varphi +p^2{z}^2{)}^k}$ — from a real quadratic (trinomial) factor.

Each piece expands into its own recurrent series, with a known general term. The general term of the original series is the sum of the general terms of the partial-fraction series (source: chapter13, §213).

Equality of two power series in $z$ is justified by setting $z=0$ (giving $A=a+a^{\prime }+a^{\prime \prime }+\cdots$), subtracting, dividing by $z$, and repeating: the coefficient of every power matches (source: chapter13, §214).

Linear-factor brick (§215–§216)

The basic series is

$\frac{A}{1-pz}=A+Apz+A{p}^2{z}^2+A{p}^3{z}^3+\cdots ,\text{general term }A{p}^n{z}^n.$

Differentiating ($k$ times) — or equivalently expanding by Newton’s binomial theorem with negative integer exponent — gives

$\frac{A}{(1-pz{)}^k}=A+kApz+\frac{k(k+1)}{2!}A{p}^2{z}^2+\frac{k(k+1)(k+2)}{3!}A{p}^3{z}^3+\cdots ,$

with general term

$\frac{(n+1)(n+2)\cdots (n+k-1)}{(k-1)!}A{p}^n{z}^n=\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)A{p}^n{z}^n.$

Euler verifies the equivalence of the two factorial expressions $\frac{(n+1)\cdots (n+k-1)}{1\cdot 2\cdots (k-1)}$ and $\frac{k(k+1)\cdots (k+n-1)}{1\cdot 2\cdots n}$ by cross-multiplication: both equal $\frac{(n+k-1)!}{n!(k-1)!}$ (source: chapter13, §215).

Examples I–V (§216, p. 183–186)

Example I — distinct real factors

$\frac{1-z}{1-z-2z^2}=\frac{2/3}{1+z}+\frac{1/3}{1-2z}.$

General term: $\left(\frac{2}{3}(-1{)}^n+\frac{1}{3}{2}^n\right)z^n=\frac{2^n\pm 2}{3}{z}^n$ (positive sign for even $n$). The series begins $1+0z+2z^2+2z^3+6z^4+10z^5+22z^6+\cdots$.

Example II — distinct real factors

$\frac{1-z}{1-5z+6z^2}=\frac{-1}{1-2z}+\frac{2}{1-3z}.$

General term: $(2\cdot 3^n-2^n)z^n$.

Example III — Lucas numbers (Binet form)

$\frac{1+2z}{1-z-z^2}$

has roots $(1\pm \sqrt{5})/2$ and partial fractions $\frac{(\sqrt{5}+1)/2}{1-\frac{1+\sqrt{5}}{2}z}+\frac{(1-\sqrt{5})/2}{1-\frac{1-\sqrt{5}}{2}z}$. General term:

${\left(\frac{1+\sqrt{5}}{2}\right)}^{n+1}{z}^n+{\left(\frac{1-\sqrt{5}}{2}\right)}^{n+1}{z}^n.$

This is the Binet-type formula for the Lucas-like sequence $1,3,4,7,11,18,29,47,\dots$.

Example IV — symbolic two-term recurrence

For the general $\frac{a+bz}{1-\alpha z-\beta z^2}$, partial fractions over the roots $(\alpha \pm \sqrt{{\alpha }^2+4\beta })/2$ give general term

$\frac{a(\sqrt{{\alpha }^2+4\beta }+\alpha )+2b}{2\sqrt{{\alpha }^2+4\beta }}{\left(\frac{\alpha +\sqrt{{\alpha }^2+4\beta }}{2}\right)}^n{z}^n+\frac{a(\sqrt{{\alpha }^2+4\beta }-\alpha )-2b}{2\sqrt{{\alpha }^2+4\beta }}{\left(\frac{\alpha -\sqrt{{\alpha }^2+4\beta }}{2}\right)}^n{z}^n.$

Euler comments: “from this result it becomes reasonably easy to express the general term of any recurrent series in which each term is determined by the two preceding terms” (source: chapter13, §216 Example IV). See closed-form-two-term-recurrence.

Example V — repeated linear factor

$\frac{1}{1-z-z^2+z^3}=\frac{1}{(1-z{)}^2(1+z)}=\frac{1/2}{(1-z{)}^2}+\frac{1/4}{1-z}+\frac{1/4}{1+z}.$

General term: $\frac{1}{2}(n+1)z^n+\frac{1}{4}{z}^n+\frac{1}{4}(-1{)}^n{z}^n=\frac{2n+3\pm 1}{4}{z}^n$ (positive sign for even $n$).

Quadratic-factor brick (§217–§222)

For complex roots, Chapter 12 gives a real partial fraction with trinomial denominator. Euler now needs the general term of

$\frac{A+Bpz}{(1-2pz\cos \varphi +p^2{z}^2{)}^k}.$

Base case $k=1$ (§217–§218)

The series for $\frac{A}{1-2pz\cos \varphi +p^2{z}^2}$ is the cos progression:

$A+2Apz\cos \varphi +A{p}^2{z}^2(2(2{\cos }^2\varphi )-1)+\cdots ,$

whose coefficients satisfy $\cos n\varphi =2\cos \varphi \cos (n-1)\varphi -\cos (n-2)\varphi$ (source: chapter13, §217). The general term of the series is

$\frac{\sin (n+1)\varphi }{\sin \varphi }A{p}^n{z}^n.$

For the more general numerator $A+Bpz$, decompose

$\frac{A+Bpz}{1-2pz\cos \varphi +p^2{z}^2}=\frac{Ppz\sin \varphi }{1-2pz\cos \varphi +p^2{z}^2}+\frac{Q-Qpz\cos \varphi }{1-2pz\cos \varphi +p^2{z}^2},$

with $Q=A$ and $P=A\cot \varphi +B\csc \varphi$ (source: chapter13, §218). The first piece has general term $P\sin (n\varphi )p^n{z}^n$; the second has $Q\cos (n\varphi )p^n{z}^n$. Sum and simplify:

$\boxed{\frac{A\sin (n+1)\varphi +B\sin n\varphi }{\sin \varphi }{p}^n{z}^n.}$

Higher $k$ (§219–§222)

For $k\ge 2$, Euler decomposes into a complex pair

$\frac{A+Bpz}{(1-2pz\cos \varphi +p^2{z}^2{)}^k}=\frac{\tilde{a}}{(1-(\cos \varphi +i\sin \varphi )pz{)}^k}+\frac{\tilde{b}}{(1-(\cos \varphi -i\sin \varphi )pz{)}^k},$

applies the §215 linear-factor brick to each piece (giving binomial coefficients), and converts back to real form via $f=\tilde{a}+\tilde{b}$, $g=(\tilde{a}-\tilde{b})/i$. The result for $k=2$ (§220) is

$\frac{(n+3)\sin (n+1)\varphi -(n+1)\sin (n+3)\varphi }{4{\sin }^3\varphi }A{p}^n{z}^n+\frac{(n+2)\sin n\varphi -n\sin (n+2)\varphi }{4{\sin }^3\varphi }B{p}^n{z}^n.$

For $k=3$ (§221) the formula expands with denominator $16{\sin }^5\varphi$ and three sine multiples in the numerator, using the identity $16{\sin }^5\varphi =10\sin \varphi -5\sin 3\varphi +\sin 5\varphi$. For $k=4$ (§222), denominator $64{\sin }^7\varphi$ and four sine multiples, via $64{\sin }^7\varphi =35\sin \varphi -21\sin 3\varphi +7\sin 5\varphi -\sin 7\varphi$. The pattern continues with higher Chebyshev-like identities

$256{\sin }^9\varphi =126\sin \varphi -84\sin 3\varphi +36\sin 5\varphi -9\sin 7\varphi +\sin 9\varphi ,\dots$

(source: chapter13, §222). The same odd-power table is derived systematically — alongside the even-power $\cos kz$ companion — in Chapter 14 §262; see powers-of-sine-and-cosine.

Combining the bricks: §223 examples

Example I — mixed factors with mod-6 cases

$\frac{1}{(1-z)(1-z^2)(1-z^3)}=\frac{1}{(1-z{)}^3(1+z)(1+z+z^2)}$

decomposes as

$\frac{1/6}{(1-z{)}^3}+\frac{1/4}{(1-z{)}^2}+\frac{17/72}{1-z}+\frac{1/8}{1+z}+\frac{(2+z)/9}{1+z+z^2}.$

Each piece has a general term; the last (with $\varphi =\pi /3$) gives $\frac{4\sin \frac{(n+1)\pi }{3}-2\sin \frac{n\pi }{3}}{9\sqrt{3}}(-1{)}^n{z}^n$. Summing all five gives a single formula

$\left(\frac{n^2}{12}+\frac{n}{2}+\frac{47}{72}\right)z^n\pm \frac{1}{8}{z}^n\pm \frac{4\sin \frac{(n+1)\pi }{3}-2\sin \frac{n\pi }{3}}{9\sqrt{3}}{z}^n,$

which simplifies into six cases by residue $n\mathrm{mod}6$ — for example, $n=6m$ gives $\left(\frac{n^2}{12}+\frac{n}{2}+1\right)z^n$, $n=6m+1$ gives $\left(\frac{n^2}{12}+\frac{n}{2}+\frac{5}{12}\right)z^n$, and so on (source: chapter13, §223 Example I). At $n=50$: $n=6\cdot 8+2$, so the coefficient is $\frac{2500}{12}+25+\frac{2}{3}=234$, i.e. $234z^{50}$. (This series is the partition-counting generating function $\prod (1-z^k{)}^{-1}$ truncated at $k=3$ — the number of partitions of $n$ into parts $\le 3$.)

Example II — four cases mod 4

$\frac{1+z+z^2}{1-z-z^4+z^5}=\frac{1+z+z^2}{(1-z{)}^2(1+z)(1+z^2)}$

decomposes as

$\frac{3/4}{(1-z{)}^2}+\frac{3/8}{1-z}+\frac{1/8}{1+z}-\frac{(1+z)/4}{1+z^2}.$

The last piece has $\cos \varphi =0$, $\varphi =\pi /2$, giving general term $(-\frac{1}{4}\sin \frac{(n+1)\pi }{2}+\frac{1}{4}\sin \frac{n\pi }{2})z^n$. The full general term is $\left(\frac{3n}{4}+\frac{9}{8}\right)z^n\pm \frac{1}{8}{z}^n-\frac{1}{4}(\sin \frac{(n+1)\pi }{2}-\sin \frac{n\pi }{2})z^n$, splitting into four mod-4 cases. At $n=50$: $n=4\cdot 12+2$, coefficient $\frac{3\cdot 50}{4}+\frac{3}{2}=39$, i.e. $39z^{50}$.

Dominant term and Bernoulli’s method (Chapter 17)

Reading the linear-factor brick $(\ast \ast )$ component by component, $P_n=U{p}^n+V{q}^n+\cdots$ with $|p|>|q|>\cdots$, the largest-magnitude term $U{p}^n$ swamps the rest as $n\to \infty$. Hence the ratio of consecutive terms converges:

$\frac{P_{n+1}}{P_n}=\frac{U{p}^{n+1}+V{q}^{n+1}+\cdots }{U{p}^n+V{q}^n+\cdots }⟶p.$

This is the algebraic content of Daniel Bernoulli’s method for finding the largest root of an algebraic equation: from the equation’s coefficients, read the scale, run the recurrent series, and the quotient $Q/P$ approximates the largest root in absolute value. The quadratic-factor brick complicates this: if a trinomial factor dominates, $P_n$ is sinusoidal in $n$ and $Q/P$ oscillates — §348–§352 then extracts both modulus and argument of the dominant complex conjugate pair from four consecutive coefficients in closed form.

Why this matters

The general-term machinery makes the recurrent series a genuine closed-form object: the $n$-th coefficient is computable directly from $n$, without iterating the recurrence. The trigonometric form for quadratic factors anticipates the modern theory of constant-coefficient linear recurrences with complex roots (oscillatory solutions $r^n\cos n\varphi$, $r^n\sin n\varphi$), and the casework on residues mod the period $k$ is the discrete analogue of the splitting of solutions by characteristic root.

For combinatorial generating functions this technique gives explicit asymptotic and even exact formulas — Euler’s §223 Example I is essentially the formula for the number of partitions of $n$ into parts of size $\le 3$, with the answer split by residue class.

Related pages

• recurrent-series
• scale-of-the-relation
• closed-form-two-term-recurrence
• sum-of-recurrent-series
• partial-fraction-decomposition
• real-partial-fraction-decomposition
• trinomial-factor
• trigonometric-recurrent-progression
• binomial-series
• de-moivre-formula
• powers-of-sine-and-cosine
• chapter-13-on-recurrent-series
• bernoullis-method-for-roots
• trinomial-factor-from-recurrent-series
• chapter-17-using-recurrent-series-to-find-roots-of-equations