- #1
- 7,861
- 1,600
On the one hand, the intuitive notion of a recurrence relation is clear from examples. On the other hand, what is the precise way to define it?
The first interesting technicality is why should we call it a "relation" ? Is it, in general, a "relation" and not the more specific case of a "function"?
As a strawman, we can consider the current Wikipedia article https://en.wikipedia.org/wiki/Recurrence_relation:
So if we have a sequence ##\{a_i\}## a recurrence relation is an equation of the form
##a_{n+1} = f(a_1,a_2,...a_n)## where ##f## is some function.
A technical question: Does this notation imply that ##f## a function of ##n##? (After all, how would you know which arguments to put in ##f## if you didn't specify ##n##?)
If someone offers the example ##a_{n+1} = 3 a_n + a_{n-2} + n##, my first reaction is that this is a recurrence relation. However, should we allow ##f## to be an explicit function of ##n##?
Suppose we do allow ##f## to be a function of ##n##. Each term ##a_n## of a (well defined) sequence is a function of ##n##. so ##a_n = g(n)## and, trivially, that would define a recurrence relation using the function ##a_{n+1} = f(n,a_1,a_2...a_n) = g(n+1)## which is constant with respect to ##a_1,a_2,...a_n##. Do we want every sequence to be recursive (in this trivial sense)?
The first interesting technicality is why should we call it a "relation" ? Is it, in general, a "relation" and not the more specific case of a "function"?
As a strawman, we can consider the current Wikipedia article https://en.wikipedia.org/wiki/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.
So if we have a sequence ##\{a_i\}## a recurrence relation is an equation of the form
##a_{n+1} = f(a_1,a_2,...a_n)## where ##f## is some function.
A technical question: Does this notation imply that ##f## a function of ##n##? (After all, how would you know which arguments to put in ##f## if you didn't specify ##n##?)
If someone offers the example ##a_{n+1} = 3 a_n + a_{n-2} + n##, my first reaction is that this is a recurrence relation. However, should we allow ##f## to be an explicit function of ##n##?
Suppose we do allow ##f## to be a function of ##n##. Each term ##a_n## of a (well defined) sequence is a function of ##n##. so ##a_n = g(n)## and, trivially, that would define a recurrence relation using the function ##a_{n+1} = f(n,a_1,a_2...a_n) = g(n+1)## which is constant with respect to ##a_1,a_2,...a_n##. Do we want every sequence to be recursive (in this trivial sense)?