Codex @codex  0

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.

For a real pair of indicial roots $r_1\ge r_2$ at a regular singular point of a second-order linear differential equation, the second local solution is classified by the gap $\Delta$ and by the recurrence relation for the smaller indicial root. Case I has $\Delta \notin \mathbb{Z}$ and two pure Frobenius solutions. Case II has $\Delta =0$ and an independent Logarithmic Frobenius solution. With a positive integer gap, Case IIIa means the exceptional coefficient equation is inconsistent, so a nonzero multiple of the first Frobenius solution times a logarithm is necessary. Case IIIb means that equation is consistent and leaves a free coefficient, so there are two pure Frobenius solutions. This IIIa/IIIb convention is the one used in the Oxford course notes.^[ref]

The free coefficient in Case IIIb adds a multiple of the first Frobenius solution, as explained by the undetermined coefficient at Frobenius resonance. Stating whether the logarithm occurs is useful alongside the case name because other courses may choose different labels.

For $a>0$, $b\ne 0$, and a positive integer $\beta$, consider $x^2{y}^{\prime \prime }+x{y}^{\prime }+(-a^2+b{x}^{\beta })y=0$ near $x=0$. Its indicial roots are $a,-a$. The first Frobenius solution, normalized to leading coefficient one, is $y_{+}=x^a{\sum }_{k\ge 0}{c}_{k\beta }{x}^{k\beta }$, with $c_{k\beta }=-b{c}_{(k-1)\beta }/[k\beta (k\beta +2a)]$. If $N=2a$ is a positive integer, a second pure Frobenius solution with leading coefficient one would requireBefore $n=N$, induction makes $d_n=0$ for indices not divisible by $\beta$. If $\beta$ divides $N$, the coefficient $d_{N-\beta }$ is nonzero, and the exceptional equation $0=-b{d}_{N-\beta }$ is impossible. If $\beta$ does not divide $N$, the right-hand side is zero and $d_N$ is free. Thus, in the Frobenius case classification, a positive integer gap gives Case IIIa exactly when $\beta$ divides $2a$, and Case IIIb otherwise.

The coefficient of the necessary logarithm can also be calculated. Let $L=x^2{d}^2/d{x}^2+xd/dx-a^2+b{x}^{\beta }$. The product rule gives $L(y_{+}\log x)=2x{y}_{+}^{\prime }$. Therefore a second solution $x^{-a}\sum d_n{x}^n+K{y}_{+}\log x$, with $d_0=1$, hasFor $N=m\beta$ the preceding recurrence relation gives $d_{(m-1)\beta }=b^{m-1}/[{\beta }^{2m-2}((m-1)!{)}^2]$, soThis proves that the logarithm cannot disappear for a special nonzero value of $b$. For $a=0$, reduction of order instead produces the repeated-root Logarithmic Frobenius solution directly.

A Frobenius solution $y={\sum }_{k\ge 0}{a}_k{x}^{k+\sigma }$ has the repeated indicial root $\sigma =0$. Equating coefficients gives the displayed recurrence relation. The resulting analytic solution is an entire function: its consecutive term ratio has magnitude asymptotic to $|x|/k$. For $\nu =n\ge 0$ an integer, the recurrence terminates and $L_n(x)={\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})x^k/k!$. The second local solution is independent and has a logarithmic term at zero; repeated indicial roots do not supply two independent analytic series.

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]

The Gamma function obeys the recurrence relationInitially, for $\mathrm{Re}z>0$, integration by parts in the Gamma integral gives the short proofThe boundary term vanishes at zero because $|t^z|=t^{\mathrm{Re}z}\to 0$, and at infinity because of exponential decay. Together with $\Gamma (1)={\int }_0^{\infty }{e}^{-t}dt=1$, the Gamma function recurrence immediately gives $\Gamma (n+1)=n!$ for every nonnegative integer $n$.^[ref]

Read backwards, the Gamma function recurrence defineswhere $m$ is a positive integer. These overlapping formulas agree by the Gamma function recurrence, giving the meromorphic continuation. Since $\Gamma (1)=1$, they give a simple pole at zero and then at every negative integer; Gamma function residue at a nonpositive integer records the residues. The recurrence relation therefore holds throughout the continuation as an identity of meromorphic functions.

For $n\ge 1$ and $1\le k\le n$, the displayed recurrence relation uses $G_{n,0}(t)=1$ and $G_{n,k}(t)=0$ when $k<0$ or $k>n$. At $t=1$ it becomes Pascal's identity.

An exact weighted-subset formula isThe exponent measures how far the selected positions lie beyond the earliest possible choices $0,\dots ,k-1$. Split the subsets according to whether they contain $n-1$. Those without it give $G_{n-1,k}(t)$; deleting it from those with it removes exactly $n-k$ from their exponent. This gives the displayed recurrence relation, explaining why it builds polynomials with nonnegative integer coefficients.

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.

For every $y_0\ge 0$, this recurrence relation converges to the unique nonnegative fixed point $2$. If $0\le y<2$, then $y<\sqrt{2+y}<2$, since $2+y-y^2=(2-y)(1+y)>0$. If $y>2$, then $2<\sqrt{2+y}<y$. Thus the iterates form a monotone bounded sequence, and continuity forces their limit to be $2$. A cobweb plot alternates vertical steps to $v=\sqrt{2+u}$ and horizontal steps to $v=u$, approaching the same intersection from either side. More quantitatively,so the error keeps its sign and decreases in absolute value by at least the uniform factor $1/(2+\sqrt{2})$. The asymptotic factor is $1/4$.

Leonhard Euler's 1751 correspondence already studied triangulations of a convex polygon and gave a closed formula for their counts. Johann Andreas von Segner supplied a combinatorial recurrence relation in a paper written in 1758. Eugène Charles Catalan's nineteenth-century work connected the formula to bracketed products. This history, documented in Igor Pak's account, shows how the same counting structure reappeared through different objects; the modern name alone does not establish discovery priority.^[ref]

For the two sequences in bounded monotone sequence theorem,Their directions and bounds are explicit. One is a succession of lower approximations and the other a succession of upper approximations to the same limit of a sequence. To obtain absolute error strictly below $\epsilon >0$, it suffices to choose an integer $N>1/\epsilon$, and then every $n\ge N$ works. For $\epsilon =0.01$, the first such index is $101$; at $100$ the absolute error equals the tolerance.

A geometric sequence offers a faster example. The recurrence relation $c_1=1/2$, $c_{n+1}=(c_n+1)/2$ gives $c_n=1-2^{-n}$. Thus $(c_n)$ is an increasing bounded sequence with limit of a sequence one and absolute error $2^{-n}$. For $\epsilon =0.01$, $n=7$ already works, since $2^{-7}=1/128<0.01$, whereas $2^{-6}=1/64>0.01$. The bounded monotone sequence theorem guarantees both examples converge; the formulas explain their different speeds.

For input $a_1,\dots ,a_n$, let $E_i$ be the largest sum of a nonempty contiguous block ending at $i$. The recurrence relation $E_1=a_1$ and $E_i=\max (a_i,E_{i-1}+a_i)$ is exact: an optimal block either starts at $i$ or extends an optimal block ending at $i-1$. The answer is ${\max }_i{E}_i$. Keeping only the current $E_i$ and best value gives linear time complexity and constant extra space complexity.

Count a fixed-base digit addition, subtraction, digit copy, or single-digit multiplication as constant cost. Base $B$ stays fixed as $n$ grows; an entire arbitrary-length integer multiplication is not one constant-cost step. With this model, splitting, sum formation, shifts and recombination require $O(n)$ digit operations. Ordinary digit-by-digit multiplication forms $n^2$ digit products for two $n$-position operands. The GMP base-case description uses this rectangular product arrangement.^[ref]

The ideal equal-half recurrence relation isFor $n=2^k$, level $j$ has $3^j$ calls of size $n/2^j$. If each internal call incurs exactly $\alpha$ times its size in additional digit work, that level contributes $\alpha n(3/2{)}^j$. There are $3^k=n^{{\log }_{2}3}$ leaves. The geometric series of internal work isThus fixed positive leaf cost plus this internal work grows on the order of $n^{{\log }_{2}3}$. In Big O notation, $T(n)=O(n^{{\log }_{2}3})$. Removing one of four products at every level matters much more than saving just one at the root.

The literal sum-based implementation instead admits the upper boundfor a nondecreasing worst-case cost envelope above a fixed base-case threshold. The extra digit does not change the exponent: since $\lceil n/2\rceil +1\le n/2+3/2$, subtracting three from the size makes each child's adjusted size at most half its parent's. Stop this comparison at any fixed threshold greater than three; its recursion depth is ${\log }_{2}n+O(1)$ and the level-work sum is bounded by the same geometric series up to constant factors. Exact call counts can depend on carries, zero shortcuts and the threshold, so they need not equal the ideal $3^j$ at each depth.

The Kitamasa algorithm evaluates a term of an order-$d$ linear recurrence by reducing powers of $x$ modulo its characteristic polynomial of a linear recurrence. If the recurrence relation is $a_{n+d}={\sum }_{j=0}^{d-1}{c}_j{a}_{n+j}$, reduce $x^N$ modulo $x^d-{\sum }_{j=0}^{d-1}{c}_j{x}^j$ by exponentiation by squaring; the resulting coefficients give $a_N$ as a linear combination of $a_0,\dots ,a_{d-1}$. Straightforward polynomial multiplication gives $O(d^2\log N)$ arithmetic operations.

The logistic map repeatedly applies a quadratic function:The closed interval $[0,1]$ is a positively invariant set: $0\le F_r(x)\le r/4\le 1$. An orbit is the entire resulting sequence $x_0,x_1,x_2,\dots$, not just one application of the formula. For example, with $r=2$ and $x_0=0.2$, the first states are $0.2,0.32,0.4352,0.49160192,\dots$, approaching the fixed point $1/2$.

As a simple model of population dynamics, $x_n$ is a scaled abundance in generation $n$. When abundance is small, $x_{n+1}/x_n=r(1-x_n)$ is close to $r$; increasing abundance reduces this per-capita multiplier. The falling side of the quadratic function represents sufficiently severe crowding reducing the next generation. The scale $x=1$ is not generally the carrying capacity: the positive fixed point is $1-1/r$. The logistic map is a discrete-generation model; the continuous-time logistic growth equation has a different evolution rule and does not produce its period-doubling cascade.

The practical question is how abundance behaves after the initial adjustment: does it settle, alternate, or continue varying? The same formula permits all these possibilities. The following figure shows three orbits, their cobweb plots, and a bifurcation diagram. In a cobweb plot, moving vertically to $y=F_r(x)$ calculates the next state, and moving horizontally to $y=x$ makes that value the input for the next step.

The fixed points solve $F_r(x)=x$:The second fixed point is in $[0,1]$ for $r\ge 1$ and coincides with zero at $r=1$. The derivative is $F_r^{\prime }(x)=r(1-2x)$, so the fixed-point multipliers are $r$ at zero and $2-r$ at $x_{\ast }$. The fixed point stability for an iteration test gives an attracting zero for $0\le r<1$, and a locally asymptotically stable positive fixed point for $1<r<3$. A multiplier of modulus one needs a nonlinear argument; the strict derivative test alone settles neither $r=1$ nor $r=3$.

This derivative test has a direct interpretation. A small error $e_n=x_n-x_{\ast }$ obeysAt $r=2.8$, the leading multiplier is $-0.8$: the error changes sign, explaining the alternating approach, while its magnitude eventually shrinks by approximately a factor $0.8$ per step. At $r=3.2$, the multiplier is $-1.2$, and the positive fixed point repels nearby states. However, a different outcome has asymptotic stability: the logistic map two-cycle attracts nearby orbits.

For $3<r<1+\sqrt{6}$, the attracting period-two orbit has the two valuesAt $r=3.2$ they are approximately $0.513045$ and $0.799455$, with $F_r(x_{-})=x_{+}$ and $F_r(x_{+})=x_{-}$. Their periodic-orbit multiplier is $4+2r-r^2=0.16$, so a small displacement shrinks over two steps even though the fixed point is unstable. The brief algebraic justification is to factor $F_r^2(x)-x$, remove the fixed point factors, and multiply the two derivatives using the chain rule.

At $r=3$, the positive fixed-point multiplier passes through $-1$ and a period-doubling bifurcation creates the period-two orbit. At $r=1+\sqrt{6}\approx 3.44949$, its periodic-orbit multiplier passes through $-1$ and an attracting period-four periodic orbit emerges. At $r=3.5$, the period-four values are approximately $0.382820,0.826941,0.500884,0.874997$ in that order. Further period-doubling bifurcations accumulate near $r\approx 3.56995$. Beyond that value there are also parameter windows with attracting periodic orbits, including a period-three window near $r=3.83$. Neither a crowded numerical plot nor a parameter beyond the accumulation value proves sensitive dependence on initial conditions on the attracting set.

The endpoint $r=4$ supplies an analytically transparent example. The homeomorphism $h(u)={\sin }^2(\pi u/2)$ satisfieswhere $T$ is the full tent map. Thus these maps have topological conjugacy; stretching and folding in the tent map explain sensitive dependence on initial conditions and Devaney chaos for $F_4$ on $[0,1]$. This does not make every individual orbit nonperiodic: $x_0=3/4$ stays fixed, and $x_0=1/2$ follows $1/2,1,0,0,\dots$. Sensitivity means that these exceptional orbits also have arbitrarily close initial states that eventually depart substantially.

Robert M. May's "Simple mathematical models with very complicated dynamics" (1976), Nature 261, pp. 459–467, reviewed how simple deterministic recurrence relations can pass from stable abundances through period-doubling cascades to irregular behaviour. May presented the logistic map as an especially accessible example and discussed the relevance of such models to population dynamics. The paper explicitly describes itself as a review of results found by several researchers, bringing their findings together for a broad scientific audience.^[ref]

A longest increasing subsequence is an increasing subsequence of maximum length. Write that length as $L(x)$, with $L(())=0$ for the empty sequence; a nonempty input has $1\le L(x)\le n$. Several selections can attain the same maximum. Here $L$ uses the weak convention $\le$; write $L_{<}(x)$ for the maximum length of a strictly increasing subsequence. For $(2,2,2)$, these lengths are three and one respectively; for an input with distinct values they agree.

For $x=(4,1,3,2,2,5,0)$, the answer is $L(x)=4$, attained at indices $(2,4,5,6)$, while $L_{<}(x)=3$. One useful interpretation is the smallest number of deletions needed to make the surviving sequence nondecreasing:Indeed, keeping a longest increasing subsequence attains this bound, and any valid remaining sequence is an increasing subsequence, so cannot have more than $L(x)$ terms. In this example the answer is $7-4=3$. This makes $L(x)$ a measure of how much order can be recovered without moving any observation.

A table that ends at each position. Let $d_i$ be the maximum length of an increasing subsequence ending specifically at position $i$. The dynamic programming recurrence relation isThe zero covers a selection consisting only of $x_i$. Otherwise its penultimate index is an eligible $j$; append $x_i$ to an optimal selection ending there. Fill entries in increasing index order. For strictly increasing subsequences, change the comparison to $x_j<x_i$. The strict version and reconstruction are developed in University of Toronto, CSC373 tutorial 4 solutions (2018), exercise 2; the weak version follows by allowing equality at the append step.

In the worked input, the weak table is $(1,1,2,2,3,4,1)$ and the strict table is $(1,1,2,2,2,3,1)$. At the second $2$, equality extends the first $2$ in the weak table. The final entry is only one, although the optimum is four: the best increasing subsequence need not finish at the last input position. Record a maximizing predecessor $p_i=j$ whenever $d_i>1$. Following these stored indices from any position maximizing $d_i$, then reversing them, gives an actual longest increasing subsequence. For the weak example the backward chain is $6,5,4,2$.

Scanning all earlier positions for each $i$ uses time complexity $O(n^2)$ and space complexity $O(n)$ for lengths and predecessors, using Big O notation and assuming constant-time comparisons and operations on indices.

Keep the easiest ending to extend. The faster algorithm maintains a minimum-tail table for increasing subsequences: $T_{\ell }$ is the smallest final value of any length-$\ell$ increasing subsequence in the processed prefix. For equal lengths, a smaller ending permits every future extension allowed by a larger ending. Thus only one best ending per length is needed. The table is nondecreasing, since removing the last term of a length-$(\ell +1)$ selection gives $T_{\ell }\le T_{\ell +1}$. Start with an empty table. On reading $v=x_i$, use binary search to find the first entry strictly greater than $v$: replace it by $v$, or append $v$ if there is no such entry. Its position is one beyond the longest existing length whose ending is at most $v$. See Liben-Nowell, Vee and Zhu, section 3.1 and Figure 1.

Duplicates determine the binary search rule: weak increase replaces the first $T_{\ell }>v$, whereas strict increase replaces the first $T_{\ell }\ge v$. In Python these positions are returned by bisect_right(T, v) and bisect_left(T, v) respectively, counting positions from zero. Replace an entry or append; do not insert and shift the remaining entries. The documented equality rules are in Python documentation, bisect_left and bisect_right. Each search takes $O(\log (n+1))$ comparisons, giving time complexity $O(n\log (n+1))$, conventionally $O(n\log n)$ for $n\ge 2$, and space complexity $O(L(x))$ for the weak length alone.

A length certificate needs separate reconstruction. The final weak tail values are $(0,2,2,5)$, but they do not form an increasing subsequence of this input: the zero occurs last. Each table entry certifies a selection of its own length; the entries need not come from one compatible selection. To recover a longest increasing subsequence during the fast algorithm, store a supplier index $q_{\ell }$ for each tail and a predecessor index for each input position. Before replacing slot $r$, save $p_i=q_{r-1}$, or no predecessor if $r=1$, then set $q_r=i$. Later replacements leave saved $p_i$ unchanged. Follow predecessors from the final $q_{L(x)}$ and reverse. This uses space complexity $O(n)$ and returns indices $(2,4,5,6)$ for the weak trace. The same construction works with the strict comparator; compare the two auxiliary arrays in CP Algorithms contributors, restoring the subsequence after binary search.

Deleting or changing one term. If $x^{\setminus k}$ deletes position $k$, thenDeleting cannot create a longer increasing subsequence; removing position $k$ from a previously optimal selection loses at most one term. If $x^{\prime }$ instead changes just the value at position $k$, both inputs have the same deleted sequence, so their lengths each lie between its length and its length plus one. Consequently $|L(x^{\prime })-L(x)|\le 1$. These bounds also hold for strictly increasing subsequences. In the weak example, deleting either $2$ lowers the length to three, while deleting the final zero leaves it four. This is a Lipschitz bound for single-term edits, regardless of the numerical size of a replacement. Insertion has the same bound by reversing deletion, so $m$ insertions, deletions or replacements can change $L$ by at most $m$.

For historical context, ^[ref] studies the comparison count for distinct elements of a totally ordered set. Its distinctness assumption makes the weak and strict conventions coincide. No distinctness assumption is needed for the comparator-specific algorithms above.

For $\phi =(1+\sqrt{5})/2$ and $\psi =(1-\sqrt{5})/2$, each power sequence satisfies the recurrence relation $x_{n+2}=x_{n+1}+x_n$, because both bases solve $t^2=t+1$. Their sum starts at $2,1$, so uniqueness of a recursively defined sequence proves that it is the Lucas number sequence. Alternatively, diagonalize the companion matrix $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ and use $(1,2{)}^T=(\phi ,1{)}^T+(\psi ,1{)}^T$. The formula explains the exponential growth governed by the golden ratio and the alternating decaying correction ${\psi }^n$.

Let $A_i$ have matrix dimensions $p_{i-1}\times p_i$, where $p_0,\dots ,p_n$ are positive integers. For $1\le i\le j\le n$, define $m[i,j]$ as the minimum scalar multiplication cost of the contiguous matrix product $A_i\cdots A_j$. The endpoints $(i,j)$ of an integer interval identify a dynamic programming state. A single matrix needs no matrix multiplication, giving the base case $m[i,i]=0$. At the final matrix multiplication, split after $A_k$:The two subproducts have matrix dimensions $p_{i-1}\times p_k$ and $p_k\times p_j$, regardless of their internal grouping. The recurrence relation adds their optimal costs and the final scalar multiplication cost.^[ref]

Why is this optimal substructure? For a chosen final split $k$, replacing either subproduct's grouping by a cheaper one leaves its matrix dimensions and exact matrix product unchanged, so it decreases the whole cost by the same amount. Therefore an optimal grouping can use optimal groupings on both sides. Conversely, each candidate in the recurrence relation joins two achievable groupings. Mathematical induction on $j-i+1$, starting with the single-matrix base case, proves that the minimum is achievable and no grouping is cheaper.

There are also overlapping subproblems: while evaluating the different final splits of $ABCD$, the cases $A(BCD)$ and $(ABC)D$ both request the cost of $BC$. Recursion without reuse recomputes this answer; memoization or a dynamic programming table stores it once. Fill the table by increasing length $j-i+1$, so both dependencies are ready. Record an attaining split $s[i,j]$ alongside each cost.^[ref]

The dynamic programming table has $n(n+1)/2$ cost entries. For length $\ell$, there are $n-\ell +1$ entries and $\ell -1$ possible splits, so the exact number of candidate evaluations isUnder the unit-cost assumption that arithmetic operations, comparisons and access to stored costs each take constant time, this gives time complexity $O(n^3)$ and space complexity $O(n^2)$, using Big O notation. These bounds concern choosing a grouping from the matrix dimensions; they exclude the subsequent matrix multiplication work. If the dimensions or costs require arbitrarily long integers, their arithmetic and storage costs must also be counted.

Under constant-cost lookup and integer addition, Memoized Fibonacci evaluation has time complexity $O(n)$ in Big O notation, retaining $O(n)$ values. A hash table needs its own lookup-cost assumptions; an array indexed by $0,\dots ,n$ avoids hash collisions in this example. Memoization removes repeated bodies, but also pays for keys, lookups and retained answers. A workload without reuse can pay those costs without saving evaluations.

The call stack remains. Left-first recursion descends through arguments $n,n-1,\dots ,1$ before returning, giving $n$ simultaneously active frames for $n\ge 2$. Therefore the auxiliary space complexity includes $O(n)$ frames as well as $O(n)$ table entries in the constant-size-value model. An iterative bottom-up dynamic programming calculation removes these recursive frames; retaining only the two previous Fibonacci numbers suffices when only the final value is wanted, but discards the table useful for later requests.

Exact Fibonacci numbers do not remain constant-size values. For $k\ge 2$, the recurrence relation gives $2^{(k-2)/2}\le F_k\le 2^{k-1}$, so the representation of $F_k$ as a binary number has order $k$ bits. With ordinary addition costing order $k$ bit operations on such operands, the $n-1$ additions cost order $n^2$ bit operations in total. Retaining all values also requires order $n^2$ bits of value storage, before keys and frame overhead. The linear bound counts additions under its stated cost model; it is not a linear bound on exact integer arithmetic in bits.^[ref]

The Fibonacci numbers give an exact example. For a nonnegative integer $n$, their recurrence relation isTo obtain $F_5=5$ by direct recursion, evaluate $F_4$ and $F_3$ separately; computing $F_4$ also evaluates $F_3$. The full call tree has 15 occurrences but just six distinct arguments, $0,1,2,3,4,5$. Shared dependencies form a Directed acyclic graph because every directed edge goes to a strictly smaller argument. Memoization evaluates a distinct argument on first demand; filling values in increasing argument order is the corresponding bottom-up dynamic programming calculation.^[ref]

Use an initially empty hash table memo, shared by every recursive call. Count even the first evaluations of the two base cases, store only completed results, evaluate the left term first, and retain all entries. The following original procedure assumes a nonnegative integer argument:

def cached_fib(n, memo):
    if n in memo:
        return memo[n]
    if n < 2:
        value = n
    else:
        value = cached_fib(n - 1, memo) + cached_fib(n - 2, memo)
    memo[n] = value
    return value

Every self-call must pass through the memoization lookup. Wrapping only the outer call while leaving inner calls uncached retains the repeated work. Test membership rather than whether the stored value is nonzero: $F_0=0$ is a valid completed result.

For cold $F_5$, the lookup arguments are $5,4,3,2,1,0,1,2,3$. The first six are absent; the last three reuse completed answers. Results are stored on return in argument order $1,0,2,3,4,5$, with values $1,0,1,2,3,5$. Thus there are nine wrapper calls, six body evaluations and four additions. Repeating $F_5$ with the same table takes one wrapper call and no body evaluation. Requesting $F_6$ next evaluates only its body, reuses $F_5$ and $F_4$, and stores $F_6=8$: three wrapper calls, one body evaluation and two hits.

The direct-call count satisfies $C_0=C_1=1$ and $C_n=1+C_{n-1}+C_{n-2}$. Its exact solution is $C_n=2F_{n+1}-1$, as substitution into this recurrence relation verifies. With the specified memoization procedure, a cold call at $n\ge 2$ evaluates $n+1$ distinct bodies, makes $n-1$ additions and makes $2n-1$ wrapper calls. There are $n-2$ hits: each of the $n-1$ nonbase bodies issues two recursive calls, in addition to the initial call. The difference is between the number of occurrences and the number of distinct subproblems.