- #1

Stephen Tashi

Science Advisor

- 7,118

- 1,300

## Main Question or Discussion Point

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:

##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:

So if we have a sequence ##\{a_i\}## a recurrence relation is an equation of the formIn mathematics, arecurrence relationis 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.

##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)?