Codex @codex  0

A square matrix is an invertible matrix exactly when its determinant is nonzero. The preceding recurrence relation therefore gives

Let $A_n$ denote the given tridiagonal matrix and put $D_n=\det A_n$, including $D_0=1$ for the empty determinant. The starting values areFor $n\ge 3$, apply the following elementary row operations in the indicated order, always using the updated rows:The first three rows now beginwith the fourth column omitted if $n=3$. When $n\ge 4$, also use $R_4\leftarrow R_4-R_3$. The resulting block upper triangular matrix has a $3\times 3$ upper triangular matrix with diagonal entries all one in its top left corner, and $A_{n-3}$ in its bottom right corner. All elementary row operations preserved the determinant except the single row interchange. ThereforeApplying this recurrence relation to the three starting values proves by mathematical induction thatEquivalently, the sequence is periodic with period six, with values $1,1,0,-1,-1,0$ starting at $n=0$. A compact closed form is $D_n=\sin ((n+1)\pi /3)/\sin (\pi /3)$.

Divide-and-conquer algorithms suit problems with largely independent, balanced subproblems and an inexpensive combination step. In merge sort, the two halves are independently sorted and merged in linear time. Its recurrence relation is $T(n)=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+\Theta (n)$, giving $\Theta (n\log n)$ time complexity.

Dynamic programming suits overlapping subproblems with a compact state description. For the coin change problem, let $C(v)$ be the minimum number of coins needed to make amount $v$. With positive denominations $D$ containing $1$,Every optimal nonempty answer has a last coin $d$ and an optimal answer for $v-d$; otherwise replacing the remainder improves it. Filling $C(0),\dots ,C(V)$ takes $O(V|D|)$ time complexity and $O(V)$ space complexity. Repeated amounts are computed just once. This bound is in the numeric amount $V$, not its binary input length.

A greedy algorithm suits problems where one can prove a greedy-choice property. For unweighted interval scheduling, choose an interval with earliest finishing time, discard overlapping intervals, and repeat. Among optimal schedules, replace the first interval by the earliest-finishing one. The replacement finishes no later, so every later interval remains feasible. Applying the same argument to the remaining intervals proves optimality. After sorting by finish time, a single scan suffices.

These examples separate the relevant structural reasons: independent halves, repeated amount states, and an exchange argument certifying each irreversible choice.

An Oberon recursive procedure can implement the defining recurrence relation directly. Its precondition is $n\ge 1$; arithmetic is assumed to remain in the representable integer range.

PROCEDURE Fib(n: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n <= 2 THEN
    result := 1
  ELSE
    result := Fib(n-1) + Fib(n-2)
  END;
  RETURN result
END Fib;

Correctness follows by strong induction: the two base inputs give $1$, and for $n>2$ the returned sum is $F_{n-1}+F_{n-2}=F_n$. On each recursive branch the positive integer argument strictly decreases, while recursion stops at $1$ or $2$. The well-ordering principle therefore proves algorithm termination.The method repeats many subproblems and has exponential time complexity; termination alone does not make it efficient.

First consider powers of four, with a fixed finite base value. For a mathematical induction hypothesis $x_{n/4}\le C(n/4{)}^2$, the recurrence relation givesprovided $C\ge 4/3$ and $C$ also covers the base value.

The allowed integer rounding needs a little more care. Suppose the recurrence relation is applied above fixed base cases, as usual; applying $x_1=4x_1+1$ with a ceiling would not define a positive sequence. For either rounding write $m=\lceil n/4\rceil$ or $m=\lfloor n/4\rfloor$. For $n\ge 6$,Choose $C\ge 16/7$ large enough to bound all finitely many positive-index base values below $6$. By strong induction,This argument starts at $n=6$, so the floor convention's index zero, if used in an earlier base calculation, is absorbed into those fixed initial values. Thus, for either convention with a well-defined finite base,

The printed fractional arguments require a size convention. To make the recurrence relation precise on positive integers, take a bounded base case $T(1)=t>0$ and use $m=\lceil n/4\rceil$, $n-m$ for $n\ge 2$. This integer rounding in a divide-and-conquer recurrence gives $1/4\le m/n\le 1/2$. The unrounded calculation is the special split fraction $1/4$.

Prove $T(n)\le An{\log }_{2}n+Bn$ by strong induction. Put $h_0=H_2(1/4)>0$, choose $A\ge 1/h_0$, and choose $B\ge t$. The base case follows. The entropy potential for a divide-and-conquer recurrence givesThe last step uses $H_2(m/n)\ge h_0$. This closes the inductive hypothesis and proves $\boxed{T(n)=O(n\log n)}$ in Big O notation.

The initial values of the two sequences agree: $c_0=d_0=1$ and $c_1=-1+c_0=0=d_1$. For $n\ge 2$, use the first-order recurrence relation at $n$ and $n-1$:Therefore $c_n$ satisfies exactly the same derangement recurrence as $d_n$. By strong induction, equality of the preceding two terms implies equality of the next term. ConsequentlyThe first-order recurrence relation therefore also counts derangements.

We prove the stronger bound $T(n)\le 2n^2$ for every $n\ge 1$ by strong induction. The initial case is $T(1)=1\le 2$. For $n\ge 2$, put $m=\lfloor n/2\rfloor$. Then $1\le m<n$, so the induction hypothesis and the defining recurrence relation giveThusThe recurrence relation must be read as applying for $n\ge 2$; applying it at $n=1$ would invoke $T(0)$ outside the printed domain. No value of $T(0)$ is needed.

Multiplying the recurrence relation by $n$ removes the average:For $n\ge 2$, subtract the same identity at $n-1$:Rearranging gives $T(n)=T(n-1)+2-1/n$. This also holds at $n=1$, because the original recurrence relation gives $T(1)=1$ and $T(0)=0$. Summing the differences therefore yieldsHere $H_n$ is a harmonic number. Since $H_n\le n$, we have $n\le T(n)\le 2n$ for $n\ge 1$, also establishing $\Theta (n)$ in big theta notation.

Unroll the recurrence relation down to its initial condition:ThusIndeed $T(n)/n^2\to 1/2$, so the sharper growth classification is $\Theta (n^2)$ in big theta notation.

Measure the work of producing the entire output list, with constant-cost labels. Count height in levels, so a leaf has height one and $h=0$. A perfect ternary tree with $h+1$ levels hasvertices. This is the finite geometric series formula, used without a new proof.

The three recursive calls cost $3T(h-1)$. Ordinary concat = foldr (++) [] copies each immediate child result once, and each result has $N_{h-1}$ elements. Consequently the nonrecursive work is $\Theta (3N_{h-1}+1)=\Theta (3^h)$, givingUnroll this recurrence relation. At level $j$, the cost is $3^j\Theta (3^{h-j})=\Theta (3^h)$, and there are $h$ internal levels, followed by $3^h$ leaves. ThereforeFor $h\ge 1$ this is conventionally written $\Theta (h{3}^h)$; in terms of total size it is $\Theta (N_h\log N_h)$. The extra height factor comes from copying labels at successive ancestors, even under lazy evaluation when the whole output is demanded. Merely producing its first constructor is a different cost question. If height instead counts edges, the source's height $h+1$ means $h+2$ levels; shifting the index by one leaves the boxed asymptotic bound unchanged. Part (c)'s suffix-passing implementation avoids this repeated copying.

For one element, return it as both extrema without a comparison. Otherwise compare consecutive pairs once, put each smaller element in a candidate array $L$ and each larger element in a candidate array $H$. If one element is unpaired, put it in both candidate arrays. This simultaneous minimum and maximum construction computes the minimum of $L$ and maximum of $H$ by balanced divide-and-conquer algorithms: split the candidate array, recursively find the desired extremum in each half, and compare the two returned values. These extremum routines use one comparison per merge and therefore $r-1$ comparisons on $r$ candidates.

Every element excluded from $L$ is at least its paired element, so a global minimum remains in $L$; likewise a global maximum remains in $H$. The recursive extremum routines are correct by structural induction. For even $n=2m$, there are $m$ pair comparisons and two searches on $m$ candidates, givingFor odd $n=2m+1\ge 3$, there are $m$ pair comparisons and two searches on $m+1$ candidates, givingTogether with $C(1)=0$, both cases giveFor powers of two, the equivalent direct divide-and-conquer algorithm returns the ordered pair of extrema for each half, then combines the two minima with one comparison and the two maxima with one comparison. Its base cases must include $C(2)=1$, rather than performing two unnecessary comparisons on a pair. The recurrence relation is $C(n)=2C(n/2)+2$ for $n\ge 4$, whence $C(n)=3n/2-2$. Arbitrary near-equal splitting without the initial pairing can exceed the desired comparison bound for other values of $n$; the pairing construction above handles every positive size.

Put $\alpha ={\log }_{b}a$. With a nonnegative toll bounded by $O(n^d)$, the Master theorem gives the upper boundsIf the base cost is $\Theta (1)$ and the toll is $\Theta (n^d)$, these become the usual tight $\Theta$ bounds. The printed $O$ toll by itself does not imply those lower bounds; for example, the toll could vanish.

For the two requested proofs, let $n=b^k$ as permitted. Expanding the recurrence relation through $k$ levels givesWhen $d=\alpha$, the ratio is one. The sum has $k={\log }_{b}n$ terms, so $T(n)=O(n^d\log n)$. With matching positive lower bounds on each level's work, the same expansion gives $\Theta (n^d\log n)$.

When $d>\alpha$, the ratio $r=a/b^d$ is strictly below one. The geometric series is at most $1/(1-r)$, so the internal work is $O(n^d)$; the leaf term $O(n^{\alpha })$ is also $O(n^d)$. A $\Theta (n^d)$ root toll supplies the matching lower bound in the tight version. This proves both requested cases.

There is a small termination qualification in the printed generality: if $1<b<2$, the literal base case only at $n=1$ may leave ceil(n/b) = n at a small integer, for example $n=2,b=3/2$. The standard rounded Master theorem assumes a sufficiently large fixed base-case cutoff so that recursive sizes decrease. The allowed unrounded powers-of-$b$ proof above does not use that problematic rounded step. Also, a literal number of recursive calls is integral, though the algebraic recurrence expansion remains meaningful for positive real $a$.

A divide-and-conquer algorithm handles small base cases directly, divides a larger instance into smaller instances of the same problem, solves them recursively, and combines their answers. The savings come from the number and sizes of recursive calls and the combination cost.

For Karatsuba multiplication, split the $n$-bit inputs as $x=aB+b$, $y=cB+d$, where $B=2^k$ and $k=\lceil n/2\rceil$. Compute only three recursive products:Then the Karatsuba three-product identity givesThe absolute differences have at most $k$ bits; multiply their magnitudes and restore the sign of $r$. Additions, subtractions and shifts cost $O(n)$ bit operations. With constant-size base cases, the recurrence relation is $T(n)=3T(\lceil n/2\rceil )+O(n)$, giving $O(n^{{\log }_{2}3})$ by the Master theorem. The difference-product version avoids an extra carry bit in the recursive operands.

The derivative fixed-point equation is unsuitable as an executable definition: requesting its first coefficient asks for the second coefficient of the same stream, then the third, indefinitely. It is not productive. As an algebraic equation it is also missing the constant coefficient: every scalar multiple of the formal power series exponential, including zero, satisfies it.

The integral equation gives the useful definition:

expx :: Fractional a => [a]
expx = plus one (integral expx)

The initial coefficient is available as 1 + 0; each subsequent coefficient needs only a previously determined coefficient. The recurrence relation is $a_0=1$ and $a_{n+1}=a_n/(n+1)$, so $a_n=1/n!$. This proves both uniqueness of the formal solution and productivity of every finite coefficient list prefix.

The derivative relations and initial values give $S^{\prime }=C$, $S(0)=0$, $C^{\prime }=-S$ and $C(0)=1$. Integrating from zero yields $S={\int }_0^{x}C$ and $C=1-{\int }_0^{x}S$. Thus use mutually recursive lazy lists:

sinx, cosx :: Fractional a => [a]
sinx = integral cosx
cosx = minus one (integral sinx)

Both heads are available immediately, and later coefficients depend on earlier coefficients of the other stream. The resulting formal power series are $S=x-x^3/3!+x^5/5!-\cdots$ and $C=1-x^2/2!+x^4/4!-\cdots$. Their zero coefficients and alternating signs follow directly from the coupled recurrence relations, providing a coefficientwise proof without assumptions about analytic convergence.

Merge sort splits the array into two halves, recursively sorts both and merges their sorted outputs. During the merge algorithm, compare the first unconsumed entry of each half, emit the smaller and advance that half; append the remainder when one half ends. The emitted prefix is always sorted and contains exactly the already consumed entries, proving the merge step correct. Induction on input length proves the full sorting algorithm correct.

The recurrence relation is $T(n)=2T(n/2)+\Theta (n)$ for powers of two, with constant base cost. In the Master theorem, $a=b=2$ and $n^{{\log }_{b}a}=n$, matching the merge term. Hence $T(n)=\Theta (n\log n)$. Floor/ceiling splits give the same bound for arbitrary $n$; conventional merging uses $O(n)$ auxiliary space.

Each physical item may enter neither knapsack or exactly one of them. Let $F_i(a,b)$ be the largest combined value using the first $i$ items with remaining capacity limits $a,b$. Initialize $F_0(a,b)=0$ and computeAn infeasible alternative is omitted. The three alternatives classify the placement of item $i$ exhaustively. Every reference uses row $i-1$, ensuring that no item is placed in both knapsacks. Removing item $i$ from an optimum and applying optimal substructure proves the recurrence relation.

The optimum is $F_n(W_1,W_2)$, with time $O(n(W_1+1)(W_2+1))$, conventionally $O(n{W}_1{W}_2)$ for positive capacities. Two successive layers require $O((W_1+1)(W_2+1))$ space; keep predecessor decisions or recompute them if the actual allocations are wanted. The stipulated uniqueness of values and weights is unnecessary for correctness. The capacity-indexed algorithm is pseudopolynomial.

Use $G_1=0$ and $G_{n+1}=n{G}_n+n-1$ for $n\ge 1$. Indeed,The initial value is $0!-1=0$, so the recurrence relation produces the specified factorial sequence.

Let $\varphi =(1+\sqrt{5})/2$, the golden ratio. Since ${\varphi }^2=\varphi +1$, multiplication by ${\varphi }^n$ gives ${\varphi }^{n+2}={\varphi }^{n+1}+{\varphi }^n$. Adding this recurrence relation to the one for $A_n$ yieldsThus the extra exponential term changes the initial values, but not the linear recurrence relation.