§2.9 Difference Equations

Keywords:: asymptotic solutions of difference equations
Referenced by:: §3.6(ii)
Permalink:: http://dlmf.nist.gov/2.9

§2.9(i) Distinct Characteristic Values
§2.9(ii) Coincident Characteristic Values
§2.9(iii) Other Approximations

§2.9(i) Distinct Characteristic Values

Keywords:: asymptotic solutions of difference equations, characteristic equation, difference equations
Referenced by:: §29.6(i), §33.9(i), Methodology
Permalink:: http://dlmf.nist.gov/2.9.i

Many special functions that depend on parameters satisfy a three-term linear recurrence relation

2.9.1 ${w(n+2)+f(n)w(n+1)+g(n)w(n)=0},$ $n=0,1,2,\dots$ ,

Symbols:: $f(n)$ : function, $g(n)$ : function, $n$ : nonnegative integer and $w(n)$ : solution
Referenced by:: §2.9(ii), §2.9(ii)
Permalink:: http://dlmf.nist.gov/2.9.E1
Encodings:: TeX, pMML, png

or equivalently the second-order homogeneous linear difference equation

2.9.2 $\Delta^{2}w(n)+(2+f(n))\Delta w(n)+(1+f(n)+g(n))w(n)=0,$ $n=0,1,2,\dots$ ,

Symbols:: $\Delta$ : forward difference operator, $f(n)$ : function, $g(n)$ : function, $n$ : nonnegative integer and $w(n)$ : solution
Permalink:: http://dlmf.nist.gov/2.9.E2
Encodings:: TeX, pMML, png

in which $\Delta$ is the forward difference operator (§3.6(i)).

Often $f(n)$ and $g(n)$ can be expanded in series

2.9.3

$f(n)\sim\sum _{{s=0}}^{{\infty}}\frac{f_{s}}{n^{s}},$

$g(n)\sim\sum _{{s=0}}^{{\infty}}\frac{g_{s}}{n^{s}}$ , $n\to\infty$ ,

Symbols:: $\sim$ : asymptotic equality, $f(n)$ : function, $g(n)$ : function, $n$ : nonnegative integer, $f_{s}$ : coefficients and $g_{s}$ : coefficients
Permalink:: http://dlmf.nist.gov/2.9.E3
Encodings:: TeX, TeX, pMML, pMML, png, png

with $g_{0}\neq 0$ . (For the case $g_{0}=0$ see the final paragraph of §2.9(ii) with $Q$ negative.) This situation is analogous to second-order homogeneous linear differential equations with an irregular singularity of rank 1 at infinity (§2.7(ii)). Formal solutions are

2.9.4 $\rho _{j}^{n}n^{{\alpha _{j}}}\sum _{{s=0}}^{{\infty}}\frac{a_{{s,j}}}{n^{s}},$ $j=1,2$ ,

Symbols:: $n$ : nonnegative integer, $a_{{s,j}}$ : coefficients and $\rho _{j}$ : roots
Permalink:: http://dlmf.nist.gov/2.9.E4
Encodings:: TeX, pMML, png

where $\rho _{1},\rho _{2}$ are the roots of the characteristic equation

2.9.5 $\rho^{2}+f_{0}\rho+g_{0}=0,$

Symbols:: $f_{s}$ : coefficients and $g_{s}$ : coefficients
Referenced by:: §2.9(ii)
Permalink:: http://dlmf.nist.gov/2.9.E5
Encodings:: TeX, pMML, png

2.9.6 $\alpha _{j}=(f_{1}\rho _{j}+g_{1})/(f_{0}\rho _{j}+2g_{0}),$

Symbols:: $f_{s}$ : coefficients, $g_{s}$ : coefficients and $\rho _{j}$ : roots
Permalink:: http://dlmf.nist.gov/2.9.E6
Encodings:: TeX, pMML, png

$a_{{0,j}}=1$ , and

2.9.7 $\rho _{j}(f_{0}+2\rho _{j})sa_{{s,j}}=\sum _{{r=1}}^{{s}}\left(\rho _{j}^{2}2^{{r+1}}\binom{\alpha _{j}+r-s}{r+1}+\rho _{j}\sum _{{q=0}}^{{r+1}}\binom{\alpha _{j}+r-s}{r+1-q}f_{q}+g_{{r+1}}\right)a_{{s-r,j}},$

Symbols:: $\binom{m}{n}$ : binomial coefficient, $f_{s}$ : coefficients, $g_{s}$ : coefficients, $a_{{s,j}}$ : coefficients and $\rho _{j}$ : roots
Referenced by:: §2.9(ii)
Permalink:: http://dlmf.nist.gov/2.9.E7
Encodings:: TeX, pMML, png

$s=1,2,3,\dots$ . The construction fails iff $\rho _{1}=\rho _{2}$ , that is, when $f_{0}^{2}=4g_{0}$ .

When $f_{0}^{2}\neq 4g_{0}$ , there are linearly independent solutions $w_{j}(n)$ , $j=1,2$ , such that

2.9.8 $w_{j}(n)\sim\rho _{j}^{n}n^{{\alpha _{j}}}\sum _{{s=0}}^{{\infty}}\frac{a_{{s,j}}}{n^{s}},$ $n\to\infty$ .

Symbols:: $\sim$ : asymptotic equality, $n$ : nonnegative integer, $a_{{s,j}}$ : coefficients, $\rho _{j}$ : roots and $w_{j}(n)$ : solutions
Permalink:: http://dlmf.nist.gov/2.9.E8
Encodings:: TeX, pMML, png

If $|\rho _{2}|>|\rho _{1}|$ , or if $|\rho _{2}|=|\rho _{1}|$ and $\realpart{\alpha _{2}}>\realpart{\alpha _{1}}$ , then $w_{1}(n)$ is recessive and $w_{2}(n)$ is dominant as $n\to\infty$ . As in the case of differential equations (§§2.7(iii), 2.7(iv)) recessive solutions are unique and dominant solutions are not; furthermore, one member of a numerically satisfactory pair has to be recessive. When $|\rho _{2}|=|\rho _{1}|$ and $\realpart{\alpha _{2}}=\realpart{\alpha _{1}}$ neither solution is dominant and both are unique.

For proofs see Wong and Li (1992b). For error bounds see Zhang et al. (1996). See also Olver (1967b).

For asymptotic expansions in inverse factorial series see Olde Daalhuis (2004a).

§2.9(ii) Coincident Characteristic Values

Keywords:: asymptotic solutions of difference equations
Referenced by:: §2.9(i)
Permalink:: http://dlmf.nist.gov/2.9.ii

When the roots of (2.9.5) are equal we denote them both by $\rho$ . Assume first $2g_{1}\neq f_{0}f_{1}$ . Then (2.9.1) has independent solutions $w_{j}(n)$ , $j=1,2$ , such that

2.9.9 $w_{j}(n)\sim\rho^{n}\mathop{\exp\/}\nolimits\!\left((-1)^{j}\kappa\sqrt{n}\right)n^{{\alpha}}\sum _{{s=0}}^{{\infty}}(-1)^{{js}}\frac{c_{s}}{n^{{s/2}}},$

Symbols:: $\mathop{\exp\/}\nolimits z$ : exponential function, $\sim$ : asymptotic equality, $\rho$ : roots, $\kappa$ , $c$ : constant and $w_{j}(n)$ : solutions
Permalink:: http://dlmf.nist.gov/2.9.E9
Encodings:: TeX, pMML, png

where

2.9.10 $\sqrt{g_{0}}\kappa=\sqrt{2f_{0}f_{1}-4g_{1}},$ $4g_{0}\alpha=g_{0}+2g_{1}$ ,

Symbols:: $\kappa$ , $f_{s}$ : coefficients and $g_{s}$ : coefficients
Permalink:: http://dlmf.nist.gov/2.9.E10
Encodings:: TeX, pMML, png

$c_{0}=1$ , and higher coefficients are determined by formal substitution.

Alternatively, suppose that $2g_{1}=f_{0}f_{1}$ . Then the indices $\alpha _{1},\alpha _{2}$ are the roots of

2.9.11 $2g_{0}\alpha^{2}-(f_{0}f_{1}+2g_{0})\alpha+2g_{2}-f_{0}f_{2}=0.$

Symbols:: $f_{s}$ : coefficients and $g_{s}$ : coefficients
Permalink:: http://dlmf.nist.gov/2.9.E11
Encodings:: TeX, pMML, png

Provided that $\alpha _{2}-\alpha _{1}$ is not zero or an integer, (2.9.1) has independent solutions $w_{j}(n)$ , $j=1,2$ , of the form

2.9.12 $w_{j}(n)\sim\rho^{n}n^{{\alpha _{j}}}\sum _{{s=0}}^{{\infty}}\frac{a_{{s,j}}}{n^{s}},$ $n\to\infty$ ,

Symbols:: $\sim$ : asymptotic equality, $\rho$ : roots and $w_{j}(n)$ : solutions
Referenced by:: §2.9(ii)
Permalink:: http://dlmf.nist.gov/2.9.E12
Encodings:: TeX, pMML, png

with $a_{{0,j}}=1$ and higher coefficients given by (2.9.7) (in the present case the coefficients of $a_{{s,j}}$ and $a_{{s-1,j}}$ are zero).

If $\alpha _{2}-\alpha _{1}=0,1,2,\dots$ , then (2.9.12) applies only in the case $j=1$ . But there is an independent solution

2.9.13 $w_{2}(n)\sim\rho^{n}n^{{\alpha _{2}}}\sum _{{\substack{s=0\\ s\neq\alpha _{2}-\alpha _{1}}}}^{{\infty}}\frac{b_{s}}{n^{s}}+cw_{1}(n)\mathop{\ln\/}\nolimits n,$ $n\to\infty$ .

Symbols:: $\mathop{\ln\/}\nolimits z$ : principal branch of logarithm function, $\sim$ : asymptotic equality, $\rho$ : roots, $b_{s}$ : coefficients, $c$ : constant and $w_{j}(n)$ : solutions
Permalink:: http://dlmf.nist.gov/2.9.E13
Encodings:: TeX, pMML, png

The coefficients $b_{s}$ and constant $c$ are again determined by formal substitution, beginning with $c=1$ when $\alpha _{2}-\alpha _{1}=0$ , or with $b_{0}=1$ when $\alpha _{2}-\alpha _{1}=1,2,3,\dots$ . (Compare (2.7.6).)

For proofs and examples, see Wong and Li (1992b). For error bounds see Zhang et al. (1996).

For analogous results for difference equations of the form

2.9.14 $w(n+2)+n^{P}f(n)w(n+1)+n^{Q}g(n)w(n)=0,$

Symbols:: $f(n)$ : function, $P$ : integer, $Q$ : integer and $g(n)$ : function
Permalink:: http://dlmf.nist.gov/2.9.E14
Encodings:: TeX, pMML, png

in which $P$ and $Q$ are any integers see Wong and Li (1992a).

§2.9(iii) Other Approximations

Keywords:: Liouville–Green (or WKBJ) approximation, asymptotic solutions of difference equations, transition points, turning points
Permalink:: http://dlmf.nist.gov/2.9.iii

For asymptotic approximations to solutions of second-order difference equations analogous to the Liouville–Green (WKBJ) approximation for differential equations (§2.7(iii)) see Spigler and Vianello (1992, 1997) and Spigler et al. (1999). Error bounds and applications are included.

For discussions of turning points, transition points, and uniform asymptotic expansions for solutions of linear difference equations of the second order see Wang and Wong (2003, 2005).

For an introduction to, and references for, the general asymptotic theory of linear difference equations of arbitrary order, see Wimp (1984, Appendix B).

§2.9 Difference Equations

Contents

§2.9(i) Distinct Characteristic Values

§2.9(ii) Coincident Characteristic Values

§2.9(iii) Other Approximations