Recurrence relation

A recurrence relation specifies members of a sequence in terms of previous members, together with enough initial values to determine the sequence. A three-term recurrence for orthogonal polynomials relates consecutive orders. For example, the physicists' Hermite polynomials satisfy $H_{n+1}(x)=2x{H}_n(x)-2n{H}_{n-1}(x)$, starting from $H_0=1$ and $H_1=2x$.

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.

If $S_0=a$ and $S_n=S_{\lfloor n/2\rfloor }+m$ for positive integers $n$, each halving removes one binary digit until zero is reached. There are $1+\lfloor {\log }_{2}n\rfloor$ such steps. The formula follows by strong induction, using $\lfloor {\log }_2\lfloor n/2\rfloor \rfloor =\lfloor {\log }_{2}n\rfloor -1$ for $n\ge 2$ and checking $n=1$ separately. With fixed positive $m$, this is $\Theta (\log n)$ as $n\to \infty$; the zero case retains its separately defined value.

For $T(n)=1$ at $n\le 3$ and $T(n)=2T(\lfloor n/2\rfloor {)}^2$ otherwise, put $d=\max (0,\lfloor {\log }_{2}n\rfloor -1)$ for positive integer $n$. Taking logarithms gives $S(n)=1+2S(\lfloor n/2\rfloor )$, hence $S(n)=2^d-1$ and $T(n)=2^{2^d-1}$. These constant-value plateaux have exponential envelopes $2^{\Theta (n)}$, but do not justify $\Theta (2^{n/2})$ for all integer inputs.

For divide-and-conquer recurrences $T(n)=aT(n/b)+f(n)$ with $a\ge 1$, $b>1$, compare $f(n)$ with $n^{{\log }_{b}a}$. If $f(n)=O(n^{{\log }_{b}a-\epsilon })$ for some $\epsilon >0$, then $T(n)=\Theta (n^{{\log }_{b}a})$. If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$. If $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$ and $af(n/b)\le cf(n)$ for a constant $c<1$ eventually, then $T(n)=\Theta (f(n))$. Constant-size base cases and ordinary bounded rounding of subproblem sizes are understood. A recursion tree proves these cases by summing per-level costs.

For $0<\alpha <1$, the successive differences satisfy $d_{n+1}=-(1-\alpha )d_n$. Summing the resulting geometric series givesEquivalently, the two-dimensional update matrix has eigenvalues $1$ and $\alpha -1$, with only the second mode decaying. At $\alpha =0$, generic initial values instead alternate and do not converge.

A linear recurrence ${\sum }_{j=0}^r{p}_j(n)a_{n+j}=0$ whose coefficients $p_j(n)$ are polynomials in the index. A sequence satisfying such a relation is P-recursive.

A difference equation relates values of a sequence at different indices, or its finite differences. A first-order autonomous system has the displayed form, with a scalar or vector state. Writing $z_{n+1}-z_n=F(z_n)-z_n$ gives its equivalent finite-difference form. Its fixed point stability is determined by the Jacobian matrix of the update and the unit circle, whereas a continuous-time differential equation uses the real parts of its linearized eigenvalues.