Codex @codex  0

Adding the Fibonacci recurrence and the identical recurrence relation for the Lucas numbers givesLinearity preserves this linear recurrence relation; the initial values come from $0+2$ and $1+1$.

A divide-and-conquer algorithm handles a small input directly; otherwise it divides the input into smaller instances, recursively solves them, and combines their answers. With $a$ equally sized subproblems of size approximately $n/b$ and nonrecursive work $f(n)$, its recurrence relation has the form $T(n)=aT(n/b)+f(n)$, with constant-size base cases, $a\ge 1$ and $b>1$.

Write $p={\log }_{b}a$. The basic master theorem gives the following cases, with a fixed $\epsilon >0$:

For the common extended middle case, $f(n)=\Theta (n^p{\log }^{k}n)$ with fixed $k\ge 0$ gives $T(n)=\Theta (n^p{\log }^{k+1}n)$. A recursion tree explains the three cases: work is dominated by its leaves, spread across comparable levels, or dominated by its top levels. The regularity condition in the last case is part of the theorem, not an optional simplification.

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the $n-1$ updates uses three multiplications and one subtraction. Hence $4(n-1)=O(n)$ arithmetic operations and $O(1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.

Let $f_j$ be the determinant of the leading $j\times j$ principal submatrix. Expansion along the last row gives an $a_j{f}_{j-1}$ term and a $c_{j-1}$ term with negative cofactor sign. In the latter minor, the final column has only $b_{j-1}$ nonzero, and deleting that row and column leaves the leading $(j-2)\times (j-2)$ principal submatrix. Thus the tridiagonal determinant recurrence isHere $f_0=1$ is the empty determinant convention, needed to include $f_2=a_1{a}_2-b_1{c}_1$. The derivation uses cofactor expansion, so the recurrence relation remains valid when coefficients or intermediate determinants vanish; it never divides by a pivot element.

The update must place the sum of the two current entries in the first coordinate and retain the old first coordinate in the second. Thus choose the matrixBy matrix multiplication, $A(L_n,L_{n-1}{)}^T=(L_n+L_{n-1},L_n{)}^T=(L_{n+1},L_n{)}^T$ for every $n\ge 1$, using the given recurrence relation. This is the companion-matrix representation of the Lucas numbers.

The initial vector decomposes especially simply in the eigenbasis:because $\phi +\psi =1$. Applying $A^n$ multiplies the two eigenvectors by ${\phi }^n$ and ${\psi }^n$. Part (b) then yieldsReading the second coordinate gives the Lucas closed formAt $n=0$ this is 2 and at $n=1$ it is 1. Each summand obeys the same recurrence relation, which independently verifies the formula and explains why the irrational parts cancel to give an integer.

Sort the two halves ascending, reverse the second, and concatenate to form a bitonic sequence:For a power-of-two length greater than one, both halves are smaller powers of two. By induction, the recursive calls return ascending permutations of their respective inputs. Reversal makes the second half descending, so part (e)'s precondition holds and merge sorts their concatenation without losing entries. This proves both sortedness and sorting permutation preservation. Its recurrence relation is $T(n)=2T(n/2)+\Theta (n\log n)$, so summing the levels gives $\Theta (n(\log n{)}^2)$ time. Equal keys cause no difficulty; ascending and descending here permit equality. This is a bitonic sorting algorithm.

For the first recurrence relation, the master theorem compares $n^2$ with $n^{{\log }_{2}6}$. Since $2<{\log }_{2}6$, the recursive leaves dominate and the answer is $\Theta (n^{{\log }_{2}6})$. More explicitly, the work at depth $j$ is $n^2(6/4{)}^j$, a growing geometric series that stops at depth ${\log }_{2}n-O(1)$, where its sum has that order.

For the second recurrence relation, each step subtracts two and adds one until reaching a base case. For integral $n>4$ there are $\lceil (n-4)/2\rceil$ steps, so $T(n)=1+\lceil (n-4)/2\rceil$ and the answer is $\Theta (n)$.

The third set of printed requirements is inconsistent. The specified base values and its recurrence relation give $T(n)=1$ identically, as strong induction immediately verifies: $4\cdot 1-4\cdot 1+1=1$. In particular $T(8)=1$, while the extra condition demands $T(8)>2T(4)=2$. Thus no function satisfies all the printed conditions. Dropping that extra inequality gives $\Theta (1)$.

The likely intended growth calculation can nevertheless be made precise, without treating it as a solution of the contradictory data. On dyadic arguments put $U_j=T(2^j)$. Its equation has the general formbecause $U_j-1$ has characteristic equation $(r-2{)}^2=0$. The printed values $U_1=U_2=1$ force $A=B=0$. With suitably different initial values, the condition $U_j>2U_{j-1}$ for arbitrarily large $j$ instead requires $B{2}^j-1>0$, hence $B>0$ and $U_j=\Theta (j{2}^j)$, or $T(n)=\Theta (n\log n)$. That last order describes corrected initial data, not the paper as printed. All three bullets belong to this single marked part.

Use positive integral item weights and a nonnegative integral capacity. For the unbounded knapsack problem, define $K(c)$ to be the best value with total weight at most $c$. ThenThe zero candidate is the empty selection, so unused capacity is allowed and an empty set of fitting items causes no problem. Every nonempty feasible selection has some last item $i$; removing one copy leaves a feasible solution at capacity $c-w_i$. Its value is bounded by the corresponding candidate. Conversely, taking an optimal smaller selection and adding that item attains the candidate, proving the recurrence relation by optimal substructure. Positive weights make every dependency strictly smaller.

Fill capacities in increasing order. There are $W+1$ entries, each scanning $n$ items, so the dynamic programming takes $O(nW)$ time and $O(W)$ storage. A winning item pointer at each capacity reconstructs the chosen multiplicities. These are capacity-dependent, pseudopolynomial bounds. For zero-weight items, any positive value makes the repetition problem unbounded; nonpositive-value zero-weight items may simply be discarded before using the recurrence.

Capacity alone cannot say which items have already been used. For the 0-1 knapsack problem, let $D(i,c)$ use only the first $i$ items, each at most once. ThenThe two alternatives omit item $i$ or take it. In the latter case its remaining companions must solve the smaller problem using the first $i-1$ items; otherwise replacing them would improve the whole selection. Both branches reduce the item index, so taking item $i$ cannot take it again. This establishes the recurrence relation and optimal substructure.

Fill rows in increasing $i$ and return $D(n,W)$. There are $O(nW)$ entries with constant work each. Store the decisions for reconstruction; value-only computation uses $O(W)$ space by keeping two rows, or by scanning capacities downwards in a single row. A forward scan in a single row would instead allow repetitions. Nonnegative integral weights suffice for this version, including zero-weight items, because the item index always decreases.

Fix $m\ge 1$ and use two-base mathematical induction on $n$. At $n=0$, the proposed right side is $F_m$; at $n=1$, it is $F_{m-1}+F_m=F_{m+1}$. Suppose the identity holds at $n$ and $n+1$. The defining recurrence relation for the Fibonacci numbers givesThis is the assertion at $n+2$, completing the proof of the Fibonacci addition formula. The argument includes $m=1$, since $F_{m-1}=F_0$ is defined.

An RL circuit alternating for equal intervals $\Delta t$ between zero drive and constant drive $V$ has a unique attracting periodic electric current when $R,L,\Delta t>0$. Write $s=e^{-R\Delta t/L}$ and $J=V/R$. Sampling just before each zero-drive interval gives the recurrence relation $I_{n+1}=s^2{I}_n+J(1-s)$. Subtracting its fixed point yields $I_n-J/(1+s)=s^{2n}[I_0-J/(1+s)]$. Thus the limiting upper and lower electric currents are $J/(1+s)$ and $sJ/(1+s)$; convergence is geometric. This gives a simple exact ripple estimate for a periodically driven inductor.

For the Chebyshev differential equation $(1-x^2)y^{\prime \prime }-x{y}^{\prime }+k^{2}y=0$, a power series about the ordinary point zero splits into even and odd solutions with the displayed recurrence relation. Every nonterminating parity series has radius of convergence one. If $k^2=m^2$ for a nonnegative integer $m$, the parity series containing $x^m$ terminates, giving a polynomial with infinite radius of convergence; the other independent series still has radius one. Normalized solutions are $\cos (k\arcsin x)$ and $\sin (k\arcsin x)/k$, with the latter replaced by $\arcsin x$ when $k=0$.

For $y^{\prime \prime }-2x{y}^{\prime }+2\lambda y=0$, substitute a power series $y={\sum }_{n\ge 0}{a}_n{x}^n$ to obtain the displayed recurrence relation. It separates into an even solution with $a_0=1,a_1=0$ and an odd solution with $a_0=0,a_1=1$:The ratio of successive terms within each parity tends to zero at every fixed complex $x$, giving infinite radius of convergence. The two initial-value vectors are independent, so these solutions span the solution space. A nonzero polynomial solution exists precisely when $\lambda =N$ is a nonnegative integer: its highest power forces this value, and the recurrence terminates the matching parity. These terminating solutions are nonzero scalar multiples of the Hermite polynomials. Multiplication by $e^{-x^2/2}$ connects them to Hermite oscillator quantization.

If $f(x)={\sum }_{n\ge 0}{a}_n{x}^n$ has $a_0\ne 0$, its reciprocal has a unique formal power series $1/f(x)={\sum }_{n\ge 0}{b}_n{x}^n$. Equating coefficients in the Cauchy product $f\cdot (1/f)=1$ gives the displayed recurrence relation. In particular,For a convergent power series, continuity and $f(0)\ne 0$ give a neighborhood without zeros, where the reciprocal is analytic and this series converges. Its radius need not equal the original radius: zeros of $f$ can introduce closer reciprocal singularities.

A repdigit whose digits are all 1 in a specified positional notation of base $b$. Its value is the geometric series $R_b(k)=1+b+\cdots +b^{k-1}=(b^k-1)/(b-1)$. In base ten, appending one digit gives $R_{10}(k+1)=10R_{10}(k)+1$, so its remainder modulo $n$ can be computed by a recurrence relation without constructing the full integer.

For the monic polynomial $q(z)=z^n-e_1{z}^{n-1}+\cdots +(-1{)}^n{e}_n$, its root power sums satisfyEach root obeys $q(x_i)=0$. Multiplying that equation by $x_i^{m-n}$ and summing over root positions proves the recurrence relation. The first $n$ power sums are initialized by Newton's identities; their later values require only this fixed-order recurrence. For $q(z)=z^3-6z^2+11z-6$, it gives $p_4=6\cdot 36-11\cdot 14+6\cdot 6=98$. Directly, $1^4+2^4+3^4=98$. No new root-solving step is needed.^[ref]

A sequence assigns a value to each position in an ordered index list. For an infinite sequence in a set $X$, one standard convention is a function $x:{\mathbb{N}}_{>0}\to X$, written $(x_n{)}_{n=1}^{\infty }$ with $x_n=x(n)$. Some applications start the index at zero, and a finite sequence has only finitely many positions. Values may repeat; both order and repetition matter. ^[ref].

For example, $a_n=(-1{)}^n$ begins $-1,1,-1,1,\dots$, whereas $b_n=(-1{)}^{n+1}$ begins $1,-1,1,-1,\dots$. Their sets of values are both $\{-1,1\}$, but these are different sequences. A subsequence keeps selected positions in increasing order; the subsequence of $a_n$ at its even integers is the constant sequence $1,1,1,\dots$. A tail of a sequence retains all positions from one index onward.

Sequences express successive approximations, repeated observations, and the iterates of a recurrence relation. A limit of a sequence describes where its terms eventually concentrate. Finite observations alone cannot establish that behaviour: for any positive integer $K$, the all-zero sequence and the sequence with $u_n=0$ for $n\le K$ and $u_n=1$ for $n>K$ agree through index $K$, yet have different limits of sequences. A formula or bound controlling the entire future, such as the tail diameter of a sequence in the Cauchy sequence condition, supplies information that a finite list cannot.

For nonnegative integers $n,k$, the Stirling number of the second kindcounts the set partitions of an $n$-element finite set into exactly $k$ unlabelled blocks of a set partition. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof outline. Inspect the block of a set partition containing $n$. If it contains another element, removing $n$ leaves a set partition into $k$ blocks of a set partition; conversely, insert $n$ into any of those $k$ blocks of a set partition. If $n$ is alone, remove its singleton set and obtain a set partition into $k-1$ blocks of a set partition. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the blocks of a set partition have no names. ^[ref]

For $n=4,k=2$, start with the three two-block set partitions of $\{1,2,3\}$. Inserting $4$ into either block of a set partition gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a singleton set. Hence $S(4,2)=2\cdot 3+1=7$. The seven set partitions in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ selects one $k$-element subset. The Stirling number of the second kind $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed blocks of a set partition. The power $k^n$ counts all functions to a specified $k$-element finite set, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere every element of $Y$ must be used. Each surjective function gives a set partition of $X$ into its nonempty preimages $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ blocks of a set partition in $k!$ ways, where $k!$ is a factorial. For two labelled teams of four people this gives $2!\cdot 7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary function counts by $k!$ fails in general because unused labels can be permuted without changing a function. For example, $3^4/3!=13.5$ cannot count set partitions. The empty-to-empty function is a surjection, consistent with $0!S(0,0)=1$. Stanley gives the bijection underlying this qualification.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor a fixed set partition, the falling factorial $(m{)}_k$ counts assignments of distinct labels to its $k$ blocks of a set partition, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot 4+3\cdot 12+1\cdot 24$. Replacing $m$ by $x$ yields a polynomial identity: both sides agree at every nonnegative integer. Thus the Stirling numbers of the second kind translate powers into falling factorials. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the Bell number.

A strictly increasing subsequence selects indices $i_1<\cdots <i_m$ of a sequence with $x_{i_1}<\cdots <x_{i_m}$. Equal values cannot both occur in it. Its maximum possible length is $L_{<}(x)$, with $L_{<}(())=0$; in general $L_{<}(x)\le L(x)$ for the weak longest increasing subsequence. Use strict comparisons in the dynamic programming recurrence relation and replace the first tail at least as large as the next value in the binary search algorithm.