Editing Recurrence relation (section)

== Applications ==

=== Mathematical biology ===
Some of the best-known difference equations have their origins in the attempt to model [[population dynamics]]. For example, the [[Fibonacci number]]s were once used as a model for the growth of a rabbit population.

The [[logistic map]] is used either directly to model population growth, or as a starting point for more detailed models of population dynamics. In this context, coupled difference equations are often used to model the interaction of two or more [[population]]s. For example, the [[Nicholson–Bailey model]] for a host-[[parasite]] interaction is given by

:<math>N_{t+1} = \lambda N_t e^{-aP_t} </math>
:<math>P_{t+1} = N_t(1-e^{-aP_t}), </math>

with <math>N_t</math> representing the hosts, and <math>P_t</math> the parasites, at time <math>t</math>.

[[Integrodifference equation]]s are a form of recurrence relation important to spatial [[ecology]]. These and other difference equations are particularly suited to modeling [[voltinism|univoltine]] populations.

===Computer science===
Recurrence relations are also of fundamental importance in [[analysis of algorithms]].<ref>Cormen, T. et al, ''Introduction to Algorithms'', MIT Press, 2009</ref><ref>R. Sedgewick, F. Flajolet, ''An Introduction to the Analysis of Algorithms'', Addison-Wesley, 2013</ref> If an [[algorithm]] is designed so that it will break a problem into smaller subproblems ([[Divide and conquer algorithm|divide and conquer]]), its running time is described by a recurrence relation.

A simple example is the time an algorithm takes to find an element in an ordered vector with <math>n</math> elements,  in the worst case.

A naive algorithm will search from left to right, one element at a time. The worst possible scenario is when the required element is the last, so the number of comparisons is <math>n</math>.

A better algorithm is called [[Binary search algorithm|binary search]]. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by

:<math>c_1=1</math>
:<math>c_n=1+c_{n/2}</math>

the [[time complexity]] of which will be <math>O(\log_2(n))</math>.

=== Digital signal processing ===
In [[digital signal processing]], recurrence relations can model feedback in a system, where outputs at one time become inputs for future time. They thus arise in [[infinite impulse response]] (IIR) [[digital filter]]s.

For example, the equation for a "feedforward" IIR [[comb filter]] of delay <math>T</math> is:

:<math>y_t = (1 - \alpha) x_t + \alpha y_{t - T},</math>

where <math>x_t</math> is the input at time <math>t</math>, <math>y_t</math> is the output at time <math>t</math>, and <math>\alpha</math> controls how much of the delayed signal is fed back into the output.  From this we can see that

:<math>y_t = (1 - \alpha) x_t + \alpha ((1-\alpha) x_{t-T} + \alpha y_{t - 2T})</math>
:<math>y_t = (1 - \alpha) x_t + (\alpha-\alpha^2) x_{t-T}  + \alpha^2 y_{t - 2T}</math>

etc.

===Economics===
{{see also|time series analysis|simultaneous equations model}}
Recurrence relations, especially linear recurrence relations, are used extensively in both theoretical and empirical economics.<ref>{{cite book |first1=Nancy L. |last1=Stokey |author-link=Nancy Stokey | first2=Robert E. Jr. |last2=Lucas |author-link2=Robert Lucas, Jr. |first3=Edward C. |last3=Prescott |author-link3=Edward C. Prescott |title=Recursive Methods in Economic Dynamics |location=Cambridge |publisher=Harvard University Press |year=1989 |isbn=0-674-75096-9 |url=https://books.google.com/books?id=BgQ3AwAAQBAJ }}</ref><ref>{{cite book |last2=Sargent |first2=Thomas J. |author-link2=Thomas J. Sargent |first1=Lars |last1=Ljungqvist |author-link=Lars Ljungqvist |title=Recursive Macroeconomic Theory |location=Cambridge |publisher=MIT Press |edition=Second |year=2004 |isbn=0-262-12274-X |url=https://archive.org/details/recursivemacroec02edljun |url-access=registration }}</ref>  In particular, in macroeconomics one might develop a model of various broad sectors of the economy (the financial sector, the goods sector, the labor market, etc.) in which some agents' actions depend on lagged variables.  The model would then be solved for current values of key variables ([[interest rate]], real [[GDP]], etc.) in terms of past and current values of other variables.