Codex @codex  0

For the Fibonacci numbers $F_0=0$, $F_1=1$, the identity $F_{n+1}{F}_{n-1}-F_n^2=(-1{)}^n$ holds for $n\ge 1$. It follows by induction: replacing each term using the Fibonacci recurrence negates the left-hand side when $n$ increases by one, and the value at $n=1$ is $-1$.

With the standard Fibonacci numbers $F_0=0$, $F_1=1$, this identity holds for $n\ge 0$, $k\ge 1$. At $k=1$ it is immediate. If it holds for $k$ at every $n$, apply it at $n+1$ and use $F_{n+2}=F_{n+1}+F_n$ to obtain $F_{n+k+1}=F_{k+1}{F}_{n+1}+F_k{F}_n$, proving the assertion by mathematical induction. Taking $k=n$ gives $F_{2n}=F_n(F_{n+1}+F_{n-1})$ for $n\ge 1$, linking the doubling formula to the Lucas numbers.

Consecutive Fibonacci numbers are coprime by the Euclidean algorithm. The Fibonacci addition formula writes $F_m=F_{m-n}{F}_{n+1}+F_{m-n-1}{F}_n$ for $m>n$. Taking the greatest common divisor with $F_n$ removes the last summand, and multiplication by the coprime factor $F_{n+1}$ leaves that gcd unchanged. The case $m=n$ uses $F_0=0$. Applying the Euclidean algorithm to the indices yields the strong-divisibility identity $\gcd (F_m,F_n)=F_{\gcd (m,n)}$ for nonnegative indices, with the usual zero conventions.

For positive integers $m,n$, the Fibonacci numbers satisfy $F_m\mid F_{mn}$. The Fibonacci addition formula gives $F_{mn+m}=F_{m-1}{F}_{mn}+F_m{F}_{mn+1}$, so mathematical induction on $n$ proves the assertion. This explains why every fifth Fibonacci number is divisible by $F_5=5$.

A heap game in which, after the first move, a player may remove at most twice the number removed on the preceding move. Under the usual first-move restriction of fewer than all counters, Fibonacci numbers and the Zeckendorf representation characterize the winning moves.

Fibonacci polynomials are defined by $F_0(x)=0$, $F_1(x)=1$, and $F_{n+1}(x)=x{F}_n(x)+F_{n-1}(x)$. Setting $x=1$ recovers the Fibonacci numbers.

With Fibonacci indexing $F_0=F_1=1$, powers of $A=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$ satisfy $A^n=\left(\begin{array}{cc}{F}_{2n}& F_{2n-1}\\ F_{2n-1}& F_{2n-2}\end{array}\right)$ for $n\ge 1$. The base case is immediate. Multiplication by $A$ advances each entry by the two-index Fibonacci recurrence, proving the identity by induction.

The linear recurrence relation defining the Fibonacci numbers, with $F_0=0$ and $F_1=1$. Its state $(F_{n+1},F_n{)}^T$ advances by the matrix $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$, so matrix powers describe repeated updates.

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.

The Lucas numbers obey the same second-order recurrence as the Fibonacci numbers but start with $2,1$, so their sequence is $2,1,3,4,7,11,\dots$. For $n\ge 1$, $L_n=F_{n-1}+F_{n+1}$. Substitution in the Fibonacci addition formula gives $F_{2n}=F_n{L}_n$. Consecutive Fibonacci numbers are coprime by the Euclidean algorithm; since $L_n=F_n+2F_{n-1}$, Bézout's identity gives $\gcd (F_n,L_n)=\gcd (F_n,2)\le 2$.

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]

For a terminating pure function, a reusable entry must record its correct completed result, and equal memoization keys must imply equal results throughout the entry's memoization cache lifetime. Reusing that result must also preserve the behavior callers require. These conditions separate correctness from speed: a complete key can be correct even if it rarely repeats.

A procedure using deterministic computation can still have a required side effect. If a procedure returns $n^2$ and appends an audit record on every call, serving the second call from a table preserves the numerical answer but skips the second record. Likewise, if each call promises a fresh mutable list, returning the same stored mutable list changes observable sharing and allows a caller to damage later answers. Plain result reuse is unsuitable for those contracts.^[ref]

Completion matters for recursion. Suppose computing key $A$ needs key $B$, and computing $B$ needs $A$. A table containing only completed answers has no answer to return for the second $A$; remembering completed values does not make this directed cycle terminate. Marking a key ACTIVE before descending detects re-entry, as in spreadsheet dependency evaluation, but detection is not a solution of the circular equations. If computation fails, clear its active mark and do not publish an unfinished value. The example using Fibonacci numbers avoids this issue through a strictly decreasing argument.

The call counts above assume sequential execution and no eviction. Concurrent requests for an absent key can both begin evaluation before either publishes its result; keeping a table coherent alone does not ensure one body execution per key.^[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.

Represent each generated sequence position by an immutable head and a lazily memoized successor, and give each iterator its own pointer into the shared chain. Computing a successor invokes the privately owned generator once; lagging copies reuse that same successor. Consequently a mutable programming closure generating Fibonacci numbers can support interleaved independent cursor positions. Sharing only the generator and a copied current value would instead consume the generator's mutable state twice. This construction can retain all cells between the fastest and slowest live cursors; it does not guarantee constant memory usage.

Overlapping subproblems occur when several parts of a calculation request the same smaller problem. Memoization can share its answer if the memoization key identifies that problem completely. For the Fibonacci numbers, both $F_5$ and $F_4$ require $F_3$. In dynamic programming, the dynamic programming state plays the corresponding role of identifying a reusable continuation. Overlap explains potential savings; the recurrence relation and its base cases still need to be correct.

Compute adjacent Fibonacci numbers together, starting at $(0,1)$ and applying $(a,b)\mapsto (b,a+b)$. The shared pair avoids repeating the same recursive subproblem and gives $n$ additions for $F_n$. This counts arithmetic operations; exact integers grow with $n$.

The expression is the Binet formula for the Fibonacci numbers. Compute the two roots and round the result to the nearest integer:

The returned object is an integer. This floating-point arithmetic implementation correctly rounds the requested range through $n=50$; it is not an arbitrary-precision method for indefinitely large $n$. An integer recurrence is a useful independent numerical check.

For integers $m,n$ not both zero, their greatest common divisor is the greatest positive integer dividing both. For the degenerate pair $(0,0)$ use the conventional value zero. A number $d$ divides both $m,n$ exactly when it divides both $m+kn,n$: one direction uses closure of divisibility under sums; the reverse subtracts $kn$. The positive common-divisor sets are therefore identical, provingThis also holds for $(0,0)$ under the stated convention and does not depend on the signs of the integers.

Bezout identity states that there exist integers $a,b$ such that $am+bn=\gcd (m,n)$. If a prime $p$ divides $mn$ but does not divide $m$, then $\gcd (p,m)=1$, so choose $a,b$ with $ap+bm=1$. Multiplying by $n$ gives $apn+bmn=n$. Both terms on the left are divisible by $p$, so $p\mid n$. Thuswhich proves the Euclid lemma from the requested identity. The separately numbered entries use these arithmetic facts for the Fibonacci numbers.

The Euclidean algorithm and the Fibonacci number recurrence giveIterating reaches $\gcd (F_1,F_0)=\gcd (1,0)=1$, so consecutive Fibonacci numbers are coprime.

Prove the Fibonacci addition formula by mathematical induction on $k$, asserting it simultaneously for every $n\ge 0$. At $k=1$, $F_1{F}_{n+1}+F_0{F}_n=F_{n+1}$. Suppose the formula holds at $k$. Apply it with $n+1$ in place of $n$ and use the recurrence:ThusFor $n\ge 1$, prove $F_n\mid F_{nl}$ by induction on $l$. The case $l=1$ is immediate. For $l\ge 2$, put $k=(l-1)n$ in the addition formula. Its first term is divisible by $F_n$ by the induction hypothesis, and its second term has an explicit factor $F_n$. ThereforeWhen $m>n\ge 1$, put $k=m-n$. Reducing the addition formula modulo $F_n$ gives $F_m\equiv F_{m-n}{F}_{n+1}$. Since $F_{n+1}$ is coprime to $F_n$, multiplication by it leaves the greatest common divisor with $F_n$ unchanged: any divisor of $F_n$ dividing the product divides $F_{m-n}$, by the Bezout identity or the Euclid lemma. This proves the Fibonacci gcd reductionAt $m=n$ both sides equal $F_n$, since $F_0=0$. The case $n=0$ is also immediate from $\gcd (a,0)=|a|$; the divisibility statement at $n=0$ reads $0\mid 0$, valid under the usual definition $b\mid a$ iff $a=bc$ for an integer $c$.

Let $\Phi (z)=1-{\varphi }_{1}z-\cdots -{\varphi }_p{z}^p$. The causality root criterion for an autoregressive model,is a sufficient condition for a weakly stationary process solution, and gives the causal solution $X_t={\sum }_{j\ge 0}{\psi }_j{\epsilon }_{t-j}$. Indeed $1/\Phi$ is analytic in a disk of radius greater than one, so its Taylor coefficients ${\psi }_j$ decay geometrically. The series therefore has mean-square convergence and defines a linear filter of a stationary time series; multiplying by $\Phi$ verifies the equation.

For the specified order-two model, put $\phi =(1+\sqrt{5})/2$. Since $\phi -{\phi }^{-1}=1$,When $\alpha \ne 0$, its roots are $1/(\alpha \phi )$ and $-\phi /\alpha$. Both have modulus greater than one exactly when $|\alpha |<1/\phi$. The case $\alpha =0$ is white noise and satisfies the same inequality. ConsequentlyThis is the causal stationarity condition selected above. Without causality, a two-sided autoregressive model can also have a noncausal stationary autoregression when its polynomial has no unit-circle zeros. Thus the inequality is not a necessary condition for all conceivable weak stationarity solutions; the causal interpretation is the one required by the subsequent innovations and forecasting questions.

To find the Wold representation, expand $1/\Phi (z)={\sum }_{j\ge 0}{\psi }_j{z}^j$. Matching coefficients gives ${\psi }_0=1$, ${\psi }_1=\alpha$ and ${\psi }_j=\alpha {\psi }_{j-1}+{\alpha }^2{\psi }_{j-2}$. HenceHere $F_1=F_2=1$ are the Fibonacci numbers. The coefficient formula also follows by partial fractions in the displayed factorization. Absolute summability follows from $|\alpha \phi |<1$ and $|\alpha /\phi |<1$. The past observation span equals the past noise span, because the causal series gives one inclusion and ${\epsilon }_t=X_t-\alpha X_{t-1}-{\alpha }^2{X}_{t-2}$ gives the reverse inclusion. Thus these noises are the linear innovations, and there is no additional deterministic component. This is the Fibonacci-coefficient autoregression.

The best linear prediction from an infinite past is the orthogonal projection onto the closed span of $X_T,X_{T-1},\dots$. Future white noise is orthogonal to that span. Substitution in the recursion therefore givesThe respective errors are ${\epsilon }_{T+1}$ and $\alpha {\epsilon }_{T+1}+{\epsilon }_{T+2}$, so their mean squared errors are ${\sigma }^2$ and $(1+{\alpha }^2){\sigma }^2$. No normal distribution assumption is needed for these linear forecasts.