Editing Recurrence relation (section)

== Solving ==

=== Solving linear recurrence relations with constant coefficients ===
{{main|Linear recurrence with constant coefficients}}

===Solving first-order non-homogeneous recurrence relations with variable coefficients===
Moreover, for the general first-order non-homogeneous linear recurrence relation with variable coefficients:

:<math>a_{n+1} = f_n a_n + g_n, \qquad f_n \neq 0,</math>
there is also a nice method to solve it:<ref>{{cite web |url=http://faculty.pccu.edu.tw/%7Emeng/Math15.pdf |title=Archived copy |access-date=2010-10-19 |url-status=live |archive-url=https://web.archive.org/web/20100705023731/http://faculty.pccu.edu.tw/~meng/Math15.pdf |archive-date=2010-07-05 }}</ref>
:<math>a_{n+1} - f_n a_n = g_n</math>
:<math>\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{f_n a_n}{\prod_{k=0}^n f_k} = \frac{g_n}{\prod_{k=0}^n f_k}</math>

:<math>\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{a_n}{\prod_{k=0}^{n-1} f_k} = \frac{g_n}{\prod_{k=0}^n f_k}</math>

Let 
:<math>A_n = \frac{a_n}{\prod_{k=0}^{n-1} f_k},</math>
Then 
:<math>A_{n+1} - A_n = \frac{g_n}{\prod_{k=0}^n f_k}</math>
:<math>\sum_{m=0}^{n-1}(A_{m+1} - A_m) = A_n - A_0 = \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}</math>
:<math>\frac{a_n}{\prod_{k=0}^{n-1} f_k} = A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}</math>
:<math>a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right)</math>

If we apply the formula to <math>a_{n+1} = (1 + h f_{nh}) a_n + hg_{nh}</math> and take the limit <math>h \to 0</math>, we get the formula for first order [[linear differential equation]]s with variable coefficients; the sum becomes an integral, and the product becomes the exponential function of an integral.

===Solving general homogeneous linear recurrence relations===
Many homogeneous linear recurrence relations may be solved by means of the [[generalized hypergeometric series]]. Special cases of these lead to recurrence relations for the [[orthogonal polynomials]], and many [[special function]]s. For example, the solution to

:<math>J_{n+1}=\frac{2n}{z}J_n-J_{n-1}</math>

is given by

:<math>J_n=J_n(z), </math>

the [[Bessel function]], while

:<math>(b-n)M_{n-1} +(2n-b+z)M_n - nM_{n+1}=0 </math>

is solved by

:<math>M_n=M(n,b;z) </math>

the [[confluent hypergeometric series]]. Sequences which are the solutions of [[P-recursive equation|linear difference equations with polynomial coefficients]] are called [[Holonomic function|P-recursive]]. For these specific recurrence equations algorithms are known which find [[Polynomial solutions of P-recursive equations|polynomial]], [[Abramov's algorithm|rational]] or [[Petkovšek's algorithm|hypergeometric]] solutions.

===Solving general non-homogeneous linear recurrence relations with constant coefficients===
Furthermore, for the general non-homogeneous linear recurrence relation with constant coefficients, one can solve it based on variation of parameter.<ref>[https://www.techrxiv.org/doi/full/10.36227/techrxiv.174439127.75795694/v1 Solution of Nonhomogeneous Linear Recurrence Relations with Constant Coefficient based on Variation of Parameter], Haoran Han, 2025</ref>


===Solving first-order rational difference equations===
{{Main|Rational difference equation}}

A first order rational difference equation has the form <math>w_{t+1} = \tfrac{aw_t+b}{cw_t+d}</math>. Such an equation can be solved by writing <math>w_t</math> as a nonlinear transformation of another variable <math>x_t</math> which itself evolves linearly.  Then standard methods can be used to solve the linear difference equation in <math>x_t</math>.