Codex @codex  0

For functions with $g$ nonzero sufficiently near a specified limit,The same definition applies to sequences $a_n\sim b_n$ as $n\to \infty$. Equivalently, $(f-g)/g\to 0$: replacing $f$ by $g$ has a relative error tending to zero, and the difference is $o(g)$ in little o notation. The limit and reference scale are essential parts of the statement.

For example, $n^2+n\sim n^2$ because $(n^2+n)/n^2=1+1/n\to 1$. Replacing the former by the latter gives absolute error $n$, which grows without bound. Thus asymptotic equivalence controls a ratio, rather than requiring the absolute error to vanish. This distinction is crucial when approximating a rapidly growing factorial with Stirling's formula.

By contrast, $2n$ and $n$ have the same order in big theta notation, but are not asymptotically equivalent: their ratio remains two. For positive functions, asymptotic equivalence gives both-sided constant bounds eventually, whereas constant bounds alone do not recover the leading coefficient.

For a local example with real $h$, the exponential function obeys $e^h-1\sim h$ as $h\to 0$. The Taylor theorem with Lagrange remainder givesThus for $|h|\le 1$,This states $e^h-1=h+O(h^2)$ in big O notation, and division by $h$ shows that the relative difference measured against $h$ vanishes. The diagram uses positive $h$; the bound is valid on both sides of zero. At $h=0.1$, the absolute error is approximately $0.00517092$ and the relative difference against $h$ is approximately $0.0517092$.

The Bernoulli numbers are a sequence of rational numbers that turns integer power sums into exact polynomials. The same numbers describe corrections when a discrete summation is compared with an integral. For example, the sum of squares $1^2+\cdots +N^2$ is $N^3/3+N^2/2+N/6$: the leading term is an integral, while the last two terms repair the difference between area and sampled values.

We use $B_1=-\frac{1}{2}$ throughout. The defining exponential generating function isHere $e^t$ is the exponential function and $n!$ is a factorial; in particular, the coefficient of $t^2$ is $B_2/2!$, rather than $B_2$. At $t=0$ the quotient has limiting value one. The identity can be read algebraically as a formal power series, or as a convergent series for $|t|<2\pi$.^[ref]

To compute the numbers, multiply by $e^t-1$ and compare coefficients. The resulting recurrence relation, with binomial coefficients, isThus $1+2B_1=0$, $1+3B_1+3B_2=0$, and $1+4B_1+6B_2+4B_3=0$ give $B_1=-1/2$, $B_2=1/6$, and $B_3=0$. Continuing givesThe recurrence relation agrees with equation 24.5.3 after replacing its index $n$ by $m+1$.^[ref]

Why do so many values vanish? Put $F(t)=t/(e^t-1)$. Direct substitution gives $F(-t)=F(t)+t$, so $F(t)+t/2$ is an even function. Its odd power series coefficients vanish: $B_{2r+1}=0$ for every positive integer $r$. The exception $B_1$ matters. The alternative convention obtained from $t/(1-e^{-t})=F(t)+t$ has $B_1^{+}=+1/2$ and exactly the same other values. A formula copied between conventions must also retain its summation endpoints.

Historically, integer power sums were studied before the modern Bernoulli number notation. A historical study examines formulas published in 1631 and distinguishes those separate formulas from encoding all exponents using one sequence of constants. This is a useful motivation for the generating function, without assigning all discovery to a single moment. ^[ref]

Keep an array $A$ unchanged, and sum entries in the half-open integer interval of array indices $[l,r)$. The precondition requires integers $0\le l\le r\le \mathrm{length}(A)$ and exact, terminating integer addition. An empty range returns the empty sum zero; a one-entry range returns that entry. Every longer range splits at its middle array index:For the original array $A=[6,-2,5,1]$, call $S(A,0,4)$. The left half returns $6+(-2)=4$, the right half returns $5+1=6$, and the original invocation returns $4+6=10$. The right half's left endpoint increases from zero to two: what decreases is range length $r-l$, not every argument. Negative entries affect the answer but do not affect algorithm termination.

For range length $n=r-l\ge 2$, the children have lengths $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, both positive and strictly less than $n$. The floor function chooses the split; the ceiling function gives the other length. Algorithm termination follows by this natural number measure. For algorithm correctness, apply mathematical induction on $n$: the two base cases return the specified sum; for a larger range, the two disjoint child ranges cover every original array index exactly once, so addition of their correct sums gives the required sum.

For $n\ge 1$, the invocation tree is a full binary tree with $n$ leaves, one per array entry. If $I$ is its number of nonleaf vertices, counting edges gives $2I=I+n-1$, so $I=n-1$. Thus the total invocation count is $2n-1$, and there are $n-1$ combining additions. Here $n=4$ gives seven calls and three combining additions. For $n=1$, there is one call and no combining addition; for $n=0$, there is also one call and no combining addition, but no entry leaf, so the $2n-1$ formula does not apply.

The call stack holds the active branch, rather than the entire invocation tree. Execute the left child completely before the right child, retaining the left result in the parent stack frame. The maximum number of active stack frames is $1+\lceil {\log }_{2}n\rceil$ for $n\ge 1$, and one for $n=0$. Balanced splitting therefore needs $O(\log n)$ frames for $n\ge 2$, compared with the $O(n)$ frames of the factorial recursive process. Assuming constant-cost array access, index operations and addition, its time complexity is $O(n)$ and its auxiliary space complexity is $O(\log n)$ machine words for $n\ge 2$, excluding the stored input. Pass the same array with different endpoints, rather than copying slices. These bounds require all stored indices and partial sums to fit in a constant number of machine words; exact unbounded integer addition and storage require a separate bit cost analysis.

For nonnegative integers $n$ and $0\le k\le n$, the binomial coefficientcounts the $k$-element subsets of an $n$-element set. To obtain the formula, first choose an ordered list of $k$ different members in $n(n-1)\cdots (n-k+1)$ ways. Each subset appears in exactly $k!$ orders, so divide by that factorial. The cases $k=0$ and $k=n$ each have one selection, the empty set and the whole set. For integer $k$ outside $0\le k\le n$, the combinatorial convention is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

For $n=5$, $k=2$, the calculation is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=5\cdot 4/2=10$. The left-hand panel lists all ten subsets of $\{a,b,c,d,e\}$. Marking an included member with one and an excluded member with zero gives a bijection with length-five binary strings containing exactly two ones. More generally, this makes selection, binary encoding, and coefficients in a binomial theorem three descriptions of the same count.

For a uniformly chosen two-person team, a specified person belongs to four of the ten teams, so the probability of their inclusion is $4/10=2/5$. Uniform selection of a $k$-element subset similarly gives inclusion probability $k/n$ for each member when $n>0$, as the double counting identity shows.

Take $N=20$ distinguishable, labeled particles and two boxes of equal volume. Retain only whether each particle is in the left or right box: use a bit $0$ for left and $1$ for right. Each length-20 string is one coarse microstate of this toy model. Assume the labels make independent side choices with equal probability, so the $2^{20}=1048576$ strings are equiprobable. Equal volumes motivate these weights for noninteracting particles with no preference for either box; equal volumes alone would not establish them for an arbitrary interacting gas.

Now retain only the number $k$ in the left box as the macrostate. Choosing which $k$ labels are left gives a binomial coefficient, soThe factorials count assignments to labels; the probability of a macrostate sums the probabilities of its constituent microstates. This is the binomial distribution with parameters $20$ and $1/2$. The same binomial coefficient appears in the counting of distinguishable two-level systems, although here the macrostate records occupancy rather than energy. ^[ref]

The largest binomial coefficient occurs at $k=10$, the balanced macrostate. All-left means $k=20$ and supplies just one string. ThusThere are $184756$ balanced strings for every all-left string, even though each individual string has the same probability. Exact balance has about $17.6\%$ of the total probability; equilibrium reasoning concerns the many macrostates near balance too, rather than certainty of exactly ten particles on each side. The diagram compares the counts with their natural logarithms.

Four fair, independent coins give a smaller worked example with the same binomial distribution. If $k$ is the number of heads, the five macrostates $k=0,1,2,3,4$ contain respectively $1,4,6,4,1$ microstates. Their probabilities are respectively $1/16,4/16,6/16,4/16,1/16$. In particular, two heads is one macrostate containing six ordered coin sequences, with Boltzmann entropy $k_B\ln 6$ in this counting analogy. A prescribed ordered sequence has one realization. The next diagram enumerates the same sixteen strings as left/right assignments.

Any deterministic comparison sort correct for all orders of $n$ distinct sort keys needs at least $\lceil {\log }_2(n!)\rceil$ comparisons on some input. Here $n!$ is a factorial, ${\log }_2$ a logarithm, and the brackets denote the ceiling function. This is a worst-case requirement, not a requirement on every input.^[ref]

For three distinct sort keys, the diagram has one leaf for each possible ordering of the original entries $a,b,c$. Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.

For the proof outline, represent adaptive comparisons by a binary tree: distinct sort keys give only two outcomes per comparison. A leaf fixes an output permutation; one leaf cannot correctly handle two different strict orders. Hence there must be at least $n!$ leaves. Maximum depth $h$ permits at most $2^h$ leaves, so $2^h\ge n!$ gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.

The growth follows without a precise approximation to the factorial. At least $\lfloor n/2\rfloor$ of its factors are at least $n/2$, so for $n\ge 2$,The brackets denote the floor function. This gives a constant times $n\log n$ lower bound for large $n$, matching the worst-case comparison growth of merge sort.

Distinct sort keys are essential to the $n!$ counting argument. Identical sort keys do not create $n!$ different strict orders. If all sort keys coincide, stable sorting returns the arrival order. This does not remove the worst-case bound for a comparison sort required to handle arbitrary distinct-key inputs.

The $k$th correlation function is the density of the $k$th factorial moment measure: integrating a nonnegative test function against $R_k$ gives the expectation of its sum over ordered $k$-tuples of distinct points. For exactly $m$ exchangeably labelled points with symmetric joint density $f_m$, it is $m!/(m-k)!$ times the marginal density of $k$ labels. It is not normalized to have total mass one.

A cyclic permutation, also called a permutation cycle, sends $k\ge 1$ distinct elements $a_1\mapsto a_2\mapsto \cdots \mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1{a}_2\dots a_k)$. For example, $(1342)$ is the permutation with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a permutation composed of two transpositions, rather than a single cyclic permutation.

Starting at a different point of the same loop changes the written list but preserves the cyclic permutation: $(1342)=(3421)$. Reversing the direction generally changes the permutation; it gives the inverse function, here $(1243)$. A transposition is a cyclic permutation of length two; a one-element permutation cycle records a fixed point. In a cycle decomposition of a permutation, one-element permutation cycles are usually omitted, with the underlying set understood.

The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying $(1342)$ four times returns every label to its start, while applying $(13)(24)$ twice already does so. Disjoint permutation cycles commute under function composition, since each moves only labels the others fix. On $n\ge 1$ labels, there are $(n-1)!$ cyclic permutations whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a factorial. This is also the count of cyclic orderings; choosing a starting position would otherwise count each loop $n$ times. Rotations are identified here, while reversing direction is allowed to give a different cyclic ordering.

Proof outline for decomposition. Starting at any label in a finite set, repeatedly apply the permutation. The pigeonhole principle forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same image, contradicting the injective function property. This produces a permutation cycle returning to the start. Start again at a label not yet visited; the new permutation cycle cannot meet an earlier one, since the bijection gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting cycle decomposition of a permutation is unique up to the order of the disjoint permutation cycles and the starting point written in each one. ^[ref]

Double counting establishes an identity by computing the cardinality of the same finite set in two ways. The useful step is to identify exactly what the members of that collection are; an algebraic equality then records two legitimate ways to organize them.

Take the ordered pairs $(S,x)$ where $S$ is a $k$-element subset of an $n$-element set and $x\in S$ is marked. Choosing $S$ first gives $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ pairs. Choosing $x$ first leaves $k-1$ members to choose from the other $n-1$, giving $n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. HenceFor five people and two-person teams, both counts give $20$: ten teams with two choices of a marked member, or five choices of that member with four choices of a teammate. The identity is explained by the bijection between these descriptions, rather than merely verified through factorials.

A product over the empty set has value one, the identity for multiplication. This makes splitting a product into successive pieces valid even when one piece contains no factors. In particular, the factorial convention is $0!=1$.

Suppose $f$ has a fourth derivative that is a continuous function on the interval $[a,b]$, and $|f^{(4)}(x)|\le M$ there. With $I={\int }_a^{b}f(x)dx$, the signed quadrature error here is $I-S_n$. Then, for some point $\xi \in (a,b)$,In particular, a strictly positive fourth derivative makes $I-S_n<0$: composite Simpson's rule overestimates the integral.^[ref]

The bound's scale follows by adding the panel errors. A panel of width $2h$ has signed quadrature error $-h^5{f}^{(4)}({\xi }_j)/90$ and absolute error at most $M{h}^5/90$. There are $(b-a)/(2h)$ panels, so the triangle inequality gives $M(b-a)h^4/180$. The intermediate value theorem for the continuous fourth derivative replaces the average of the panel values $f^{(4)}({\xi }_j)$ by a single value $f^{(4)}(\xi )$, giving the signed formula.

The underlying single-panel calculation can be seen through the Peano kernel theorem. On the interval $[0,2]$, define the raw Peano kernel $K(t)=L[(x-t{)}_{+}^3]$, where $L$ is integral minus Simpson's rule and $(x-t{)}_{+}=\max (x-t,0)$ is the positive part. Then $K(t)=-t^3(4-3t)/12$ for $0\le t\le 1$ and $K(t)=-(2-t{)}^3(3t-2)/12$ for $1\le t\le 2$. It is strictly negative inside the interval and has integral $-1/15$. ThusThe uniform norm $\Vert f^{(4)}{\Vert }_{\infty }$ bounds the fourth derivative. The polynomial $f(x)=x^4/24$ attains equality. Scaling to endpoint spacing $h$ multiplies the coefficient by $h^5$, giving the sharp single-panel bound $h^5\Vert f^{(4)}{\Vert }_{\infty }/90$. The normalized Peano kernel is $K/3!$, so the external factorial must be omitted when using that normalization.

For the exponential function on $[0,1]$, $f^{(4)}(x)=e^x$, so $M=e$ and the bound is $e/(180n^4)$. Its leading actual absolute error is $(e-1)/(180n^4)$, smaller than the bound because a uniform upper bound on the fourth derivative does not use its variation across the interval. The theorem bounds truncation error with exact function evaluations; sample errors and roundoff error are additional contributions, as described by noise sensitivity of a quadrature rule.

The Euler evaluation of even zeta values turns a family of series into exact expressions using Bernoulli numbers, factorials and powers of $\pi$. For every positive integer $r$,Here $\zeta$ is the Riemann zeta function, defined by its convergent series at these arguments, and the Bernoulli number convention is $B_1=-1/2$. The alternating sign combines with the sign of $B_{2r}$ to give a positive sum.^[ref]

Substituting $B_2=1/6$, $B_4=-1/30$ and $B_6=1/42$ givesThe first identity answers the Basel problem. It is surprising because the original series only mentions reciprocal squares of integers, while its exact sum involves the circle constant $\pi$. The cotangent partial-fraction expansion supplies a connection between the two: trigonometric functions encode equally spaced integer poles, whose expansion brings the reciprocal powers into view.

For an original numerical comparison, the first ten terms give ${\sum }_{n=1}^{10}{n}^{-2}\approx 1.549767731$, while ${\pi }^2/6\approx 1.644934067$. The omitted positive terms still contribute approximately $0.095166336$. For fourth powers, the ten-term partial sum is approximately $1.082036583$, only $0.000286650$ below ${\pi }^4/90\approx 1.082323234$. Both are convergent series, but the second approaches its limit much faster.

Exact evaluation is useful beyond obtaining more digits. It supplies an independent check on a numerical summation, exposes how Bernoulli numbers organize infinitely many identities, and makes the remaining series truncation error measurable without knowing any omitted terms individually. The even integer condition is essential to this formula: putting $r=3/2$ into it is not a way to evaluate $\zeta (3)$, since the required Bernoulli number index and factorial expression here are indexed by positive integers.

Historically, Leonhard Euler announced reciprocal-square and reciprocal-fourth-power evaluations in §2 of On the sums of series of reciprocals by Leonhard Euler. That paper was presented on 5 December 1735 and published in 1740, as the English translation's first-page note records. His §§3–8 develop a route through the sine power series and relationships between roots and coefficients. The cotangent calculation below is a concise modern presentation of the connection.^[ref]

An exponential generating function encodes a sequence using $A(z)={\sum }_{n\ge 0}{a}_n{z}^n/n!$. For labelled counting, $a_n$ is the number of structures on a fixed set of $n$ distinct labels. Labels distinguish otherwise similar objects: changing which person belongs to a group can change the structure. Recover the count by coefficient extraction as $a_n=n![z^n]A(z)$. The raw coefficient is $a_n/n!$, not $a_n$.

The factorial makes multiplication account automatically for distributing labels. To combine an $A$-structure on $k$ labels and a $B$-structure on the remaining $n-k$, choose the first label subset in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways, then choose the two structures. The binomial coefficient counts how the two groups of labels interleave within the full label set. ThusThe normalization works because $1/(k!(n-k)!)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)/n!$. This explains the usefulness of exponential generating functions for labelled counting: an ordinary Cauchy product would omit the choices of labels. See Peter Magyar, Math 482, notes for 2/7, labelled product principle.

For a concrete example, there is one undecorated set on any given collection of labels. Its exponential generating function is the exponential function $E(z)=e^z={\sum }_{n\ge 0}{z}^n/n!$. Combine a red set and a blue set, allowing either to be empty:Every label independently receives one of two colours, giving $2^n$ assignments by the rule of product. With three labels, the counts by number of red labels are $1,3,3,1$, totalling eight. Choosing only the two group sizes would give the four possibilities $(0,3),(1,2),(2,1),(3,0)$; it would forget which labels are red.

Indeed, the ordinary generating function for the constant sequence $a_n=1$ is the geometric series $1/(1-z)$. Its square has coefficient $[z^n](1-z{)}^{-2}=n+1$, counting pairs of nonnegative sizes. Both encodings are correct for their respective questions. The decision is whether identity matters when objects are combined.

For unordered sets of labelled components of positive size, an exponential generating function $B(z)$ becomes $e^{B(z)}$: the term $B(z{)}^m/m!$ forgets the ordering of $m$ components. The existing rooted-tree generating function develops the richer example $T=z{e}^T$. A labelled rooted tree consists of its root of a tree and an unordered set of smaller labelled rooted trees, connecting the same label-distribution mechanism to recursive counting.

For a nonnegative integer $n$, the factorial $n!$ is the product of the positive integers from $1$ to $n$, with the empty product equal to $1$:Thus $1!=1$, $2!=2$, $3!=6$, $4!=24$ and $5!=120$. The factorial counts the permutations of $n$ distinct objects: arranging $A,B,C$ gives exactly $ABC,ACB,BAC,BCA,CAB,CBA$. The choice tree in permutation shows the three choices for the first position, two for the second, and one for the last.

The value $0!=1$ has a counting explanation: the empty set has exactly one ordering, the empty list. Equivalently, it has exactly one bijection to itself, the empty function. There are no choices to make, and one completed outcome. The factorial therefore obeys the recurrence relationThe useful distinction is how many positions are filled. For integers $0\le k\le n$, choosing and ordering $k$ distinct objects by sampling without replacement gives the falling factorial, while choosing an unordered $k$-element subset gives the binomial coefficient:For five people, assigning captain and deputy gives $5!/3!=20$ outcomes; choosing a two-person team gives $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Every team has exactly $2!$ assignments of the two roles, explaining the division. When $k=0$, both counts are one. The factorial is useful here because one count of full orderings yields both formulas by cancellation and by forgetting order. ^[ref]

Distinctness matters. If the two copies of $A$ in $AAB$ are indistinguishable, the visible arrangements are just $AAB,ABA,BAA$, numbering $3!/2!=3$. Temporarily labelling them $A_1,A_2$ gives six permutations, but exchanging the two labels leaves each visible word unchanged, so every word was counted $2!$ times.

Proof outline. For $n\ge 1$, choose the first object in $n$ ways, then order the remaining $n-1$ objects in $(n-1)!$ ways. The rule of product gives the recurrence relation; repeated application gives the displayed product, starting from the one empty ordering. This explains why the factorial grows quickly: every additional distinct object introduces another multiplicative factor.

The graph of the factorial function has a fixed-length first-order formula in the language of ordered rings interpreted on the natural numbers. A remainder code records $a_0=1$, $a_n=y$, and $a_{i+1}=(i+1)a_i$ for every $i<n$. Uniqueness of remainders proves $y=n!$; sufficiently large pairwise-coprime moduli and the Chinese remainder theorem supply a code for every input. Formula length is independent of the input variable's value, although substituting a numeral adds its encoding length.

A mixed-radix positional notation using factorials as place values: $n={\sum }_{i\ge 1}{a}_{i}i!$ with $0\le a_i\le i$. For lexicographic order on permutations, division by $(k-1)!$ selects the next symbol when $k$ symbols remain; the remainder gives the rank within that block.

If $X$ has a Poisson distribution with parameter $\lambda >0$, then the ordinary factorial $X!$ has finite expectation exactly when $\lambda <1$. Indeed, its nonnegative expectation series is $e^{-\lambda }{\sum }_{k\ge 0}{\lambda }^k$, since $k!$ cancels the denominator of the probability mass function. The geometric series gives the formula and proves divergence for $\lambda \ge 1$. This differs from a falling-factorial moment of fixed order, which is finite for every finite Poisson distribution parameter.

For a natural number $n$, the factorial satisfies $0!=1$ and $n!=n(n-1)!$ for $n\ge 1$. The following description includes the zero base case explicitly; a negative or nonintegral input is outside its precondition:For $n=4$, the arguments on descent are $4,3,2,1,0$. Each positive-argument invocation postpones one multiplication until its recursive call returns. At the deepest point, the call stack has five stack frames: four suspended callers and the active zero base case. The invocation at zero returns $1$ to the invocation at one, rather than finishing the entire computation. Returns then giveA stack frame retains the caller's argument and where to resume. When the invocation at three receives $2$, it uses its own $n=3$, obtains $6$, and returns that value to the invocation at four. The recursive calls share a definition, but their local variables belong to separate invocations.

The natural number measure $n$ decreases by one on every recursive call, so algorithm termination follows. For algorithm correctness, use mathematical induction: the zero base case returns $0!=1$; assuming the child's answer is $(n-1)!$, the caller returns $n(n-1)!=n!$. This also explains why keeping the caller's $n$ matters.

There are exactly $n+1$ invocations and $n$ multiplications, including one invocation and no multiplications when $n=0$. Ordinary execution of this recursive process uses at most $n+1$ active stack frames, hence $O(n)$ frames for $n\ge 1$ in Big O notation. If each test, call, subtraction and multiplication is counted as constant cost, its time complexity is $O(n)$. That is an arithmetic-operation model: exact arbitrary-length integer multiplication has growing cost, and neither the factorial output nor every stack frame's numeric contents occupies a universally fixed number of bits.

The Gamma function extends factorials to a continuous argument. Its defining Gamma integral iswhere $t^{z-1}=\exp ((z-1)\log t)$ uses the real natural logarithm for $t>0$. The Gamma function recurrence gives its meromorphic continuation to the complex plane, with simple poles at $0,-1,-2,\dots$ and no zeros. See Gamma function residue at a nonpositive integer and Gamma function has no zeros for proof outlines.^[ref]

For nonnegative integers $n$, the factorial identity has a shift of one:Thus $\Gamma (n)=(n-1)!$ for positive integers $n$. Half-integer arguments supply a different familiar constant:The first value follows from the Gaussian integral; the second follows from the Gamma function recurrence.^[ref]

The plot shows only positive real arguments; the gamma function also accepts complex numbers away from its poles. Matching the factorials alone does not select a unique interpolation, even if the Gamma function recurrence is imposed: $f(x)=\Gamma (x)\exp (\sin (2\pi x))$ has the same positive-integer values and the same recurrence relation. The Bohr-Mollerup theorem supplies the extra condition that selects the gamma function.

The useful idea is to replace a discrete product of numbers by an integral whose exponent varies continuously. The Gamma integral then evaluates whole families of integrals at once, provides the normalizing constant for the Gamma distribution in probability theory, and appears in physics, for example in the Bose integral. Its large-positive-argument growth reconnects this continuous description to factorials through Stirling's formula.^[ref]

Historically, Leonhard Euler studied the interpolation of factorials in his paper E19, written in 1729 and published in 1738. His integral over $(0,1)$ becomes the Gamma integral after a change of variables, with the same one-step shift in the argument.^[ref]

A generating function packages a sequence into a series so that operations on objects become operations on their encodings. An ordinary generating function uses the power series $A(z)={\sum }_{n\ge 0}{a}_n{z}^n$; in counting problems, the coefficient $a_n$ records the number of objects of size $n$. The variable $z$ initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as $[z^n]A(z)=a_n$. One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.

Start with two contributions: choose $i$ from $\{0,1,2\}$ and $j$ from $\{0,1\}$, with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials $P(x)=1+x+x^2$ and $Q(x)=1+x$. To count ordered pairs by total $i+j$, multiply:The coefficients $1,2,2,1$ count the ways to obtain totals zero through three. For total two, the possibilities are $(1,1)$ and $(2,0)$; the two corresponding monomials both contribute $x^2$. There are six ordered pairs altogether, agreeing with $P(1)Q(1)=3\cdot 2=6$.

If the first contribution has two distinguishable choices when $i=1$, replace $P(x)$ by $1+2x+x^2$. Its product with $Q(x)$ becomes $1+3x+3x^2+x^3$. The coefficients now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.

In general, the Cauchy product givesFor each split of the total size, the rule of product counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See MIT 18.310, generating functions, sections 1–2.

Now cover a board of length $n$ with tiles of lengths one and two, without gaps or overlaps. Let $t_n$ count these tilings. There is exactly one empty tiling, so $t_0=1$, and $t_1=1$. Removing the first tile leaves a board shorter by one or two, giving the recurrence relationThese are the Fibonacci numbers shifted by one index: $t_n=F_{n+1}$ under the convention $F_0=0$, $F_1=1$. Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.

For $F(z)={\sum }_{n\ge 0}{t}_n{z}^n$, the empty board or a first tile followed by a remaining tiling givesEquivalently, $F(z)={\sum }_{m\ge 0}(z+z^2{)}^m$: each factor chooses one tile, and $m$ counts pieces while the exponent of $z$ records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories $(1,2)$ and $(2,1)$ differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. ^[ref]

These identities hold in formal power series algebra: each requested coefficient uses only finitely many contributions. The repeated-choice expansion is legitimate because $z+z^2$ has zero constant term; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a convergent series. Here the radius of convergence is $(\sqrt{5}-1)/2$, the reciprocal of the golden ratio. At $z=1$, the rational function equals $-1$, but the counting series diverges: that value cannot represent its sum.

Other generating functions change the encoding: an exponential generating function divides by factorials, while a Dirichlet series uses $n^{-s}$. A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.