Codex @codex  0

Prove a proposed bound by mathematical induction, substituting the inductive hypothesis for smaller arguments into the recurrence relation. Choose its constants so the resulting inequality implies the proposed bound at the current argument, and verify all base cases. A leading-order guess may need an additional lower-order term to make the induction close. The entropy potential for a divide-and-conquer recurrence is an example using a linear correction to an $n\log n$ bound.

The sequence $n,\phi (n),\phi (\phi (n)),\dots ,1$ obtained by iterating Euler's totient function on a positive integer. Since $1\le \phi (n)<n$ for $n>1$, the sequence reaches 1. Counting both endpoints gives the length recurrence relation $L(1)=1$ and $L(n)=1+L(\phi (n))$; increasing order of $n$ therefore suffices for dynamic programming.

Let $n\ge 1$. Store the tridiagonal matrix $A$ by its diagonal $b_1,\dots ,b_n$, lower diagonal $a_2,\dots ,a_n$, and upper diagonal $c_1,\dots ,c_{n-1}$. The linear system $Ax=d$ iswith the nonexistent endpoint terms omitted. Initialize $p_1=b_1$ and $g_1=d_1$. For $i=2,\dots ,n$, compute the elimination multiplier, modified pivot element, and modified right-hand side:These recurrence relations apply the elementary row operation $R_i\leftarrow R_i-m_i{R}_{i-1}$ after the preceding row has already been reduced. The transformed linear system is an upper bidiagonal matrix:Thus back substitution is especially short:For $n=1$, only $x_1=d_1/b_1$ remains. Check each pivot element before its first division, including $p_n$ before back substitution.

Equivalently, this constructs an LU decomposition with unit lower bidiagonal matrix $L$, whose lower diagonal is $m_2,\dots ,m_n$, and upper bidiagonal matrix $U$, whose diagonal is $p_1,\dots ,p_n$ and upper diagonal is $c_1,\dots ,c_{n-1}$. The $g$ sweep is forward substitution in $Lg=d$. There is no fill-in outside these bands when no rows are interchanged. LAPACK's DGTSV source uses these same coefficient and right-hand-side updates in its branch without row interchange.^[ref]

An invertible matrix need not admit the unpivoted Thomas algorithm. For example,Here $\det A=-1$ and $Ax=d$, but $p_1=0$ makes $m_2=1/0$ undefined. Interchanging the two equations instead gives the upper triangular matrix system $x_1+x_2=3$, $x_2=2$, solved immediately by back substitution. Even a nonzero first diagonal does not guarantee all later pivot elements: $\left(\begin{array}{ccc}1& 1& 0\\ 1& 1& 1\\ 0& 1& 1\end{array}\right)$ has determinant $-1$, yet $p_2=1-1=0$.

For a general tridiagonal matrix, use a solver with partial pivoting when these structural guarantees are unavailable or a dangerously small pivot element occurs. Adjacent row interchanges can introduce a second upper diagonal, so a pivoted solver must track that additional fill-in; it cannot blindly continue the unpivoted recurrence relations. LAPACK's DGTSV explicitly performs partial pivoting, stores this extra upper diagonal, and includes it in back substitution. Its fixed-width storage and bounded work per row retain $O(n)$ time for one right-hand side and $O(n)$ storage.^[ref]