Recurrence relation

1、“recurrence relation”即“递归关系”，“递归方程”，它是一个数学概念。在Discrete Mathematics and Its Applications的chapter 4 advanced counting techniques中对它进行了介绍。

2、“recurrence relation”所描述的relation是离散的。

wikipedia Recurrence relation

In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given; each further term of the sequence or array is defined as a function of the preceding terms.

NOTE: 显然，recurrence relation是一个的recursive definition。

The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation. However, "difference equation" is frequently used to refer to any recurrence relation.

Definition

NOTE: 原文的这一段非常难懂

Examples

Factorial

The factorial is defined by the recurrence relation

$ n!=n(n-1)!\quad {\text{for}}\quad n>0, $

and the initial condition

$ 0!=1. $

Logistic map

Fibonacci numbers

Solving

NOTE: 给定一个recurrence relation，如何求解出它的通用表达式，这是本节所讨论的问题。

Applications

Computer science

Recurrence relations are also of fundamental importance in analysis of algorithms.

TODO: 添加链接到工程algorithm的analysis of algorithm章节。