Editing Recurrence relation (section)

==Examples==
===Factorial===
The [[factorial]] is defined by the recurrence relation
:<math>n!=n\cdot (n-1)!\quad\text{for}\quad n>0,</math>
and the initial condition
:<math>0!=1.</math>
This is an example of a ''linear recurrence with polynomial coefficients'' of order 1, with the simple polynomial (in {{mvar|n}})
:<math>n</math>
as its only coefficient.

===Logistic map===
An example of a recurrence relation is the [[logistic map]] defined by

:<math>x_{n+1} = r x_n (1 - x_n),</math>

for a given constant <math>r.</math> The behavior of the sequence depends dramatically on <math>r,</math> but is stable when the initial condition <math>x_0</math> varies.

===Fibonacci numbers===
The recurrence of order two satisfied by the [[Fibonacci number]]s is the canonical example of a homogeneous [[linear recurrence]] relation with constant coefficients (see below).  The Fibonacci sequence is defined using the recurrence

:<math>F_n = F_{n-1}+F_{n-2}</math>

with [[initial condition]]s

:<math>F_0 = 0</math>
:<math>F_1 = 1.</math>

Explicitly, the recurrence yields the equations
:<math>F_2 = F_1 + F_0</math>
:<math>F_3 = F_2 + F_1</math>
:<math>F_4 = F_3 + F_2</math>
etc.

We obtain the sequence of Fibonacci numbers, which begins
:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

The recurrence can be solved by methods described below yielding [[Binet's formula]], which involves powers of the two roots of the characteristic polynomial <math>t^2 = t + 1</math>; the [[generating function]] of the sequence is the [[rational function]]
:  <math>\frac{t}{1-t-t^2}.</math>

===Binomial coefficients===
A simple example of a multidimensional recurrence relation is given by the [[binomial coefficient]]s <math>\tbinom{n}{k}</math>, which count the ways of selecting <math>k</math> elements out of a set of <math>n</math> elements.
They can be computed by the recurrence relation
:<math>\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},</math>
with the base cases <math>\tbinom{n}{0}=\tbinom{n}{n}=1</math>. Using this formula to compute the values of all binomial coefficients generates an infinite array called [[Pascal's triangle]]. The same values can also be computed directly by a different formula that is not a recurrence, but uses [[factorial]]s, multiplication and division, not just additions:
:<math>\binom{n}{k}=\frac{n!}{k!(n-k)!}.</math>

The binomial coefficients can also be computed with a uni-dimensional recurrence:
:<math>\binom n k = \binom n{k-1}(n-k+1)/k,</math>
with the initial value <math display = inline>\binom n 0 =1</math> (The division is not displayed as a fraction for emphasizing that it must be computed after the multiplication, for not introducing fractional numbers).
This recurrence is widely used in computers because it does not require to build a table as does the bi-dimensional recurrence, and does involve very large integers as does the formula with factorials (if one uses <math display = inline>\binom nk= \binom n{n-k}, </math> all involved integers are smaller than the final result).