Definition of "recurrence relation"

[Stephen Tashi]

The definition from the current Wikipedia article is a good start:

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.

My technical question is whether "each further term" is a function of only the values of the preceeding terms, or is it also a function of the index of the "further term"?

For example, if we are given that the values of two consecutive terms are (in order) $x$ and $y$ and given the equation $z = x + 2y$ where $z$ is the next consecutive term, then we don't have to know that $z$ is the 5th term or the 24th term etc. in order to find $z$ from $x$ and $y$.

However, if we are given an equation like $z_n = 2 z_{n-1} - 3 n z_{n-2}$ then I can find the "further term" $z_n$ if am given the value of the the previous two terms and the index $n$, but it isn't obvious that I can find an an arbitrary term $z$ from previous terms $x$ and $y$ without knowing $n$.

On the one hand, it seems natural to allow the definition of "reccurence relation" to assume that $n$ is known, because the familiar examples of recurrence relation say things like $z_n = ...$ , explicitly using $n$ like the argument of a function.

On the other hand, given any sequence of positive numbers $a_0, a_1, a_2, ...$ we would have the recurrence relation $a_{n} = f(n) a_{n-1}$ where $f(n) = \frac{a_n}{a_{n-1}}$. So sequences of numbers satisfying recurrence relations would not be particularly special.

It might be possible to leave dependence on $n$ out of the definition of recurrence relation and still have equations like $z_n = 2z_{n-1} -3 nz_{n-2}$ be equivalent to recurrence relations if we can deduce the value of $n$ involved from the values of the two consecutive terms. The recurrence relation would be an equation employing a function that was implemented as a complicated algorithm - to the effect of "given x and y and the first two terms $z_0, z_1$ of the sequence, perform the following steps to deduce the index $n$ ...and then set $z =2x + 3ny$".

 

[micromass]

The distinction is like the one where you have a differential equation like $y^{\prime\prime} + 2y^\prime + 4y = 0$ where all the coefficients are constant, or more complicated ones like $xy^{\prime\prime} + xy = x^2$, where the coefficients are allowed to depend on the independent variable $x$. Clearly, with constant coefficients, it is easier to handle.

In the same way, you have recurrence relations where the coefficients are constant, like $a_{n+1}= 2a_n$, or allowed to depend on an independent variable $n$, like with $a_{n+1} = na_n$. Clearly, the first type is easier to handle.

The correspondence between differential equations and recurrence relation is more than just cosmetic, they are two sides of the same coin.

 

[fresh_42]

I tried to understand what it is about. I'm not quite sure, though. As soon as you use the term function instead of sequence, the enumerator of the sequence becomes a variable, namely the evaluation point of the function. Of course we can always resolve the recursion. I don't know whether this always results in a nice closed form, as e.g. the Fibonacci sequence, which can be written
$F(n) = \frac{1}{\sqrt{5}} \cdot (φ^{n} - (1-φ)^{n})$ with $φ = \frac{1+\sqrt{5}}{2}$

 

[Stephen Tashi]

In the same way, you have recurrence relations where the coefficients are constant, like $a_{n+1}= 2a_n$, or allowed to depend on an independent variable $n$, like with $a_{n+1} = na_n$. Clearly, the first type is easier to handle.

I'll interpret that to mean that the definition of "recurrence relation" applies to equations where a term z in a sequence is equal to a function that depends on the values of some previous terms and also may depend explicitly on the index n of z in the sequence.

However, I don't think of an equation like $z_n = f(n,z_{n-1}) = n^2 - 3 n$ as being a recurrence relation even though it gives $z_n$ as a function of $n$ and $z_{n-1}$. (Of course, the fact that $f$ is constant with respect to $z_{n-1}$ doesn't disqualify it from being a function of $z_{n-1}$.)

Looking for the definition of "recursive function" on the web, I find that people avoid giving any simple definition for it. There are various ways to precisely define the concept of a "recursively defined function" but they are specialized into various types of recursively defined functions. I have to wonder why people tread carefully when defining "recursively defined function" and are casual in defining a "recurrence relation".

 

[micromass]

I'll interpret that to mean that the definition of "recurrence relation" applies to equations where a term z in a sequence is equal to a function that depends on the values of some previous terms and also may depend explicitly on the index n of z in the sequence.

However, I don't think of an equation like $z_n = f(n,z_{n-1}) = n^2 - 3 n$ as being a recurrence relation even though it gives $z_n$ as a function of $n$ and $z_{n-1}$. (Of course, the fact that $f$ is constant with respect to $z_{n-1}$ doesn't disqualify it from being a function of $z_{n-1}$.)

Then you shouldn't look at an equation like $y=f(x,y') =x^2-3x$ as a differential equation either. I can appreciate this sentiment. But there is no reason to make a convoluted definition when even this pathological case follows all theorems.

 

[Stephen Tashi]

I tried to understand what it is about. I'm not quite sure, though. As soon as you use the term function instead of sequence, the enumerator of the sequence becomes a variable, namely the evaluation point of the function.

I think you are saying that for any sequence $a_0, a_1,a_2$ there is an associated function $f(n)$ defined by $f(n) = a_n$. I agree.

My question is whether we want a definition of "recursion relation" to be so inclusive that an equation like $a(n) = f(n)$ is a "recursion relation".

Micromass says it is mathematically best to allow such equations to be called recursion relations because it preserves a connection between differential equations and the recursion relations that arise in finding power series solutions to those equations. I, personally, am not concerned with preserving that connection. However, I suspect that he is correct, in the sense that if we try to create a definition of "recursion relation" that excludes such examples, the definition will get complicated.

 

[fresh_42]

However, I suspect that he is correct, in the sense that if we try to create a definition of "recursion relation" that excludes such examples, the definition will get complicated.

I think he's right, too (of course). Definitions like this do usually try to cover the largest possible variety and narrow down ranges of consideration by additional (often named) properties or classes. Thus I'd define a recursion of degree $k$ as $a_n = f_\mathcal{I}(g(n),a_\iota)$ with $\iota \in \mathcal{I} \subseteq \{0,1, \dots , n-1\}$ and $|I|=k$.

In the end it will certainly differ from author to author or from paper to paper. Would be interesting to know if there are conventions in language / automaton theory.

 

[micromass]

I think he's right, too (of course). Definitions like this do usually try to cover the largest possible variety and narrow down ranges of consideration by additional (often named) properties or classes. Thus I'd define a recursion of degree $k$ as $a_n = f_\mathcal{I}(g(n),a_\iota)$ with $\iota \in \mathcal{I} \subseteq \{0,1, \dots , n-1\}$ and $|I|=k$.

In the end it will certainly differ from author to author or from paper to paper. Would be interesting to know if there are conventions in language / automaton theory.

I'd even go further than you, and define it as
f(n,a_n, a_{n-1},...)=0
In the same way, I would define a differential equation as
f(x,y,y',...)

 

[fresh_42]

I'd even go further than you, and define it as
f(n,a_n, a_{n-1},...)=0
In the same way, I would define a differential equation as
f(x,y,y',...)

You mean, as - in my notation - $k = k(n)$?
I'm thinking about your second differential equation and whether it covers the time dependent cases, too...

 

[micromass]

No, I didn't really follow your notation at all.

 

[fresh_42]

No, I didn't really follow your notation at all.

Shall the points in $f(n,a_n,a_{n-1},...) = 0$ indicate, that the number of predecessors that define the $n$-th term may vary with $n$ as well? E.g. like $f_{2n} = a_{2n-1}+a_{2n-2}+a_{2n-3}$ and $f_{2n-1} = a_{2n-2}-a_{2n-3}$?
This would generate some challenging sequences.

 

[micromass]

Yes, sure, I see no reason to put any restriction on that.