Definition of "recurrence relation"

In summary: This is true, but it doesn't change the fact that the recurrence relation is defined explicitly in terms of the sequence, while the function is defined implicitly through its values at each index. Therefore, it is more convenient and accurate to consider the recurrence relation as the primary concept and the corresponding function as a consequence of it.In summary, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, where each further term is defined as a function of the preceding terms. The index of the "further term" may also be
  • #1
Stephen Tashi
Science Advisor
7,861
1,599
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##".
 
Mathematics news on Phys.org
  • #2
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.
 
  • #3
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}##
 
  • #4
micromass said:
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".
 
  • #5
Stephen Tashi said:
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.
 
  • #6
fresh_42 said:
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.
 
  • #7
Stephen Tashi said:
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.
 
  • #8
fresh_42 said:
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
[tex]f(n,a_n, a_{n-1},...)=0[/tex]
In the same way, I would define a differential equation as
[tex]f(x,y,y',...)[/tex]
 
  • #9
micromass said:
I'd even go further than you, and define it as
[tex]f(n,a_n, a_{n-1},...)=0[/tex]
In the same way, I would define a differential equation as
[tex]f(x,y,y',...)[/tex]
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...
 
  • #10
No, I didn't really follow your notation at all.
 
  • #11
micromass said:
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.
 
  • #12
Yes, sure, I see no reason to put any restriction on that.
 

Related to Definition of "recurrence relation"

1. What is a recurrence relation?

A recurrence relation is a mathematical equation that describes a sequence of numbers or values in terms of one or more previous terms in the sequence. It is often used to model sequential processes or relationships between variables.

2. How is a recurrence relation different from a regular mathematical equation?

A recurrence relation differs from a regular mathematical equation because it defines a sequence of values rather than a single value. It also uses previous terms in the sequence to generate the next term, whereas a regular equation typically uses specific values for each variable.

3. Can you give an example of a recurrence relation?

One example of a recurrence relation is the Fibonacci sequence: F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1. This equation defines a sequence of numbers where each term is the sum of the two previous terms.

4. How are recurrence relations used in real-world applications?

Recurrence relations are commonly used in fields such as computer science, physics, and economics to model and analyze sequential processes. They can also be used to solve problems in optimization, algorithms, and data analysis.

5. What are some techniques for solving recurrence relations?

There are several techniques for solving recurrence relations, including substitution, iteration, and the characteristic equation method. Other methods, such as generating functions and master theorem, are also used for more complex recurrence relations.

Similar threads

Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
Replies
13
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
960
  • General Math
Replies
0
Views
833
Replies
1
Views
2K
Replies
8
Views
1K
Replies
4
Views
2K
  • General Math
Replies
4
Views
776
  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
1K
Back
Top