Editing Recurrence relation (section)

===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).