# I The general notion of a recurrence relation

#### Stephen Tashi

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

Related Set Theory, Logic, Probability, Statistics News on Phys.org

#### stevendaryl

Staff Emeritus
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?
You can't say that a sequence is or is not recursive. You say that the definition of the sequence is.

You have a functional $F$ of type $R^\omega \rightarrow R^\omega$. A particular sequence $\overrightarrow{a}$ is said to be a fixed point of $F$ if:

$F(\overrightarrow{a}) = \overrightarrow{a}$

Then you can say that the function $F$ is a recursive definition of a sequence $\overrightarrow{a}$ if it is the unique fixed point of $F$.

Every sequence has a trivial recursive definition: $\overrightarrow{a}$ is the unique fixed point of the constant functional

$F(x) = \overrightarrow{a}$

#### fresh_42

Mentor
2018 Award
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?
From my book about automatons and languages:

Let $g,h$ be two known functions with $n,n+2$ arguments, resp. The function $f$ on $n+1$ arguments is called primitive recursion of $g$ and $h$, if
• $f(x_1,\ldots ,x_n,0) = g(x_1,\ldots ,x_n)$
• $f(x_1,\ldots ,x_n,y+1) =h(x_1,\ldots ,x_n,y,f(x_1,\ldots ,x_n,y))$

#### SSequence

@fresh_42
One thing is that this definition only defines/describes one kind of recursive definition, even for natural numbers (not a criticism ofc, just something obvious that still might be worth mentioning). In hindsight, of course when one adds a small operation to these definitions (the "general recursive functions") they become equal to collection of partial computable functions.

However, that is not clear at first. For example, the concept of general recursive function was there before lambda calculus was realised as computing tool by Church. So, there were two things he did:
(1) Via usual reduction arguments, show that both "general recursive functions" and "lambda calculus" are equally powerful.

(2) This is the part that is interesting with regards to the question. Church gave Kleene number of quite complicated kind of recursions/recursive equations (in a general sense), and asked him to show that lambda cal. could simulate/calculate them. And it turned out lambda cal. was powerful enough to do it. So after that he formulated his definition/thesis.

=====================

The book "Recursive Functions in Computer Theory" (Rozsa Peter) might be a good resource (as far as various recursive definitions corresponding to functions of natural numbers are concerned). I don't think it is an easy read though. I don't know of any other book (a newer one for example) that covers this kind of topic exclusively.

P.S. Of course none of this still covers the more general topic of when we change the domain/range of our functions from ℕ to ℝ.

Last edited:

#### Stephen Tashi

You can't say that a sequence is or is not recursive. You say that the definition of the sequence is.

You have a functional $F$ of type $R^\omega \rightarrow R^\omega$. A particular sequence $\overrightarrow{a}$ is said to be a fixed point of $F$ if:

$F(\overrightarrow{a}) = \overrightarrow{a}$

Then you can say that the function $F$ is a recursive definition of a sequence $\overrightarrow{a}$ if it is the unique fixed point of $F$.
That's certainly a "bullet proof" definition!

Is there a way to define a more specialized type of recursion that treats only the case when a "recurrence relation" is used to implement the function $F$? - which begs the question of how to define a "recurrence relation".

#### stevendaryl

Staff Emeritus
That's certainly a "bullet proof" definition!

Is there a way to define a more specialized type of recursion that treats only the case when a "recurrence relation" is used to implement the function $F$? - which begs the question of how to define a "recurrence relation".
Well, I think that the usual idea of "course of values" recursion is that:
1. The value of $a_0$ can be calculated without knowing anything else. In terms of our function $F$, this means that whenever $F(\overrightarrow{x}) = \overrightarrow{y}$, then $y_0 = a_0$.
2. The value of $a_1$ can be calculated using only $a_0$. That means that whenever $F(\overrightarrow{x}) = \overrightarrow{y}$, if $x_0 = a_0$, then $y_1 = a_1$
3. The value of $a_2$ can be calculated using only $a_0, a_1$. That means that whenever $F(\overrightarrow{x}) = \overrightarrow{y}$, if $x_0 = a_0$, and $x_1 = a_1$, then $y_2 = a_2$
4. Etc.
The more general kind of recursion works this way:
1. There is a well-founded relation $x \succ y$ on the natural numbers. A relation is well-founded if there is no infinite sequence of elements: $x_1$, $x_2$, ... such that $x_1 \succ x_2 \succ x_3 \succ...$
2. For each $n$, the value of $a_n$ depends on $\{ a_m | n \succ m \}$
The idea is that to know $a_{n_0}$, I need to know other values, $a_{n_1}, a_{n_2}, ...$ To figure out each of those, I need to know yet other values. But if I'm going down in a well-founded relation, then eventually I'll get to a minimal value of $n$. To compute $a_n$ for that value of $n$, I don't need to know anything.

#### Stephen Tashi

The more general kind of recursion works this way:
1. There is a well-founded relation $x \succ y$ on the natural numbers. A relation is well-founded if there is no infinite sequence of elements: $x_1$, $x_2$, ... such that $x_1 \succ x_2 \succ x_3 \succ...$
2. For each $n$, the value of $a_n$ depends on $\{ a_m | n \succ m \}$
I'm trying to define appropriate concepts for dealing with situations like the example from https://www.physicsforums.com/threads/recursive-square-root-inside-square-root-problem.954655/ where the original post asks for a recursion relation for the sequence implied by the notation:

$\sqrt{ 2 + \pi \sqrt{ 3 + \pi \sqrt{4 + ... }}}$

Defining $a_n$ to be a truncation of that calculation, it is clear how to express $a_n$ as a function (algorithm) that begins by computing $\pi \sqrt{n+1}$ and proceeds to evaluate expressions in the square roots containing that value. So $a_n$ is a funtion of $n$.

It isn't clear (to me) how to express $a_n$ as a function of previous terms of the sequence in some way that the values of those previous terms are actually "important" in determining $a_n$.

By contrast, in a recurrence relation like $a_n = 3 a_{n-1} + a_{n-2}$ or $a_n = 3 a_{n-1} + 5n$ intuition says that the previous terms are "important" in determining the value of $a_n$.

What definitions involving the concept of recurrence can express the intuitive idea conveyed by typical examples of recurrence relations - namely that previous terms are "important" or "useful"? Is it possible to prove that sequences defined in some manner can never satisfy "useful" recurrence relations? - and that other types of sequences must satisfy such relations?

#### stevendaryl

Staff Emeritus
I'm trying to define appropriate concepts for dealing with situations like the example from https://www.physicsforums.com/threads/recursive-square-root-inside-square-root-problem.954655/ where the original post asks for a recursion relation for the sequence implied by the notation:

$\sqrt{ 2 + \pi \sqrt{ 3 + \pi \sqrt{4 + ... }}}$

Defining $a_n$ to be a truncation of that calculation, it is clear how to express $a_n$ as a function (algorithm) that begins by computing $\pi \sqrt{n+1}$ and proceeds to evaluate expressions in the square roots containing that value. So $a_n$ is a funtion of $n$.
I would write the recurrence relation as $a_n = \sqrt{n + \pi a_{n+1}}$.

That's an instance of the more general notion of recurrence relation, which is to look for a fixed point of a functional $F(\overrightarrow{a}) = \overrightarrow{a}$. But unlike a recursive relation, each $a_n$ depends on $a_{n'}$ for infinitely many different $n'$. That makes it not a recursive function, because the "depends on" relationship is not well-founded (there is no minimal element). The fact that the expression involves $n$ as well as $a_{n+1}$ doesn't seem so significant to me, except for the fact that you're not just finding a single limit.

It isn't clear (to me) how to express $a_n$ as a function of previous terms of the sequence in some way that the values of those previous terms are actually "important" in determining $a_n$.
What you could try is to have a sequence of sequences:

$a_{n,m}$

where you have an initial guess:

$a_{n,0} = 0$

and then let $a_{n,m+1} = \sqrt{n + \pi a_{n+1,m}}$

Then you take the limit as $m \rightarrow \infty$ if it exists.

So
• $a_{n,0} = 0$
• $a_{n,1} = \sqrt{n}$
• $a_{n,2} = \sqrt{n + \pi \sqrt{n+1}}$
• $a_{n,3} = \sqrt{n + \pi (\sqrt{n + \pi \sqrt{n+1}})}$
• etc.
I think that it's easy enough to prove that the sequence is convergent.

If the limit as $m \rightarrow \infty$ of $a_{n,m}$ is convergent, then it means that we can re-express the recurrence this way:

Let $d_{n,k}$ be digit number $k$ in the decimal expansion of $a_n$. Then each $d_{n,k}$ depends on only finitely many $d_{n',k'}$. Unfortunately, there may be no closed-form expression saying how many.

#### Stephen Tashi

I would write the recurrence relation as $a_n = \sqrt{n + \pi a_{n+1}}$.
Aren't you discussing a different sequence than the $\{a_i\}$ that I defined?

For example, I proposed discussing
$a_1 = \sqrt{ 2}$
$a_2 = \sqrt{2 + \pi \sqrt{3} }$
$a_3 = \sqrt{2 + \pi \sqrt{3 + \pi \sqrt{4}}}$.
etc.

In terms of that, I think your sequence is:
$B = \lim_{k \rightarrow \infty} a_k$
$b_1 = B = \sqrt{ 2 + \pi \sqrt{3 + \pi \sqrt{4 + ....}}}$
$b_2 = ( \sqrt{ \frac{B^2 - 2}{\pi} })^2 = \sqrt{ 3 + \pi \sqrt{4 + ...}}$
$b_3 = ( \sqrt{ \frac{b_2^2 - 3}{\pi}})^2 = \sqrt{4 + \pi \sqrt{5 + ...}}$
etc.

That's an instance of the more general notion of recurrence relation, which is to look for a fixed point of a functional $F(\overrightarrow{a}) = \overrightarrow{a}$. But unlike a recursive relation, each $a_n$ depends on $a_{n'}$ for infinitely many different $n'$.
I understand the phrase "depends on ....for infinitely many different $n'$ " if the meaning is that computing $b_{n+1}$ depends on knowing $B$.

That makes it not a recursive function, because the "depends on" relationship is not well-founded (there is no minimal element).
I think this is a tricky situation. I can deny that $B$ is a minimal element on the intuitive grounds that "You can't define $B$ without referring to an infinite number of terms of the sequence $\{a_i\}$". However, I can also take the view that $B$ is a minimal element for the sequence $\{b_i\}$ , even though $B$ is "unknown".

(By the way, in this thread my goal is not to compute $B$. I'm interested in finding a definition that precisely describes the vague notion "The n+1st term of the sequence depends in an important way only on the previous k terms". )

#### stevendaryl

Staff Emeritus
Aren't you discussing a different sequence than the $\{a_i\}$ that I defined?

For example, I proposed discussing
$a_1 = \sqrt{ 2}$
$a_2 = \sqrt{2 + \pi \sqrt{3} }$
$a_3 = \sqrt{2 + \pi \sqrt{3 + \pi \sqrt{4}}}$.
etc.

In terms of that, I think your sequence is:
$B = \lim_{k \rightarrow \infty} a_k$
$b_1 = B = \sqrt{ 2 + \pi \sqrt{3 + \pi \sqrt{4 + ....}}}$
$b_2 = ( \sqrt{ \frac{B^2 - 2}{\pi} })^2 = \sqrt{ 3 + \pi \sqrt{4 + ...}}$
$b_3 = ( \sqrt{ \frac{b_2^2 - 3}{\pi}})^2 = \sqrt{4 + \pi \sqrt{5 + ...}}$
etc.
Sorry, I got the indices wrong.

Yes, I would consider your $a_n$ to be the $n^{th}$ approximation to $b_1$. Repeating my definition, but with your notation:
• $b_{n,0} = 0$
• $b_{n,m+1} = \sqrt{n + \pi b_{n+1,m}}$
Then $b_n = lim_{m \rightarrow \infty} b_{n,m}$.

Then your $a_n = b_{2,n+1}$

I think this is a tricky situation. I can deny that $B$ is a minimal element on the intuitive grounds that "You can't define $B$ without referring to an infinite number of terms of the sequence $\{a_i\}$". However, I can also take the view that $B$ is a minimal element for the sequence $\{b_i\}$ , even though $B$ is "unknown".
Yes, it depends on whether you are trying to compute $b_n$ in terms of $b_{n+1}$, or vice-versa. In one direction, the "depends-on" relationship is well-founded; in the other direction, it's not.

In the forward direction, you have:
• $b_2 = B$
• $b_{n+1} = \frac{(b_n)^2 - n}{\pi}$
In that case, I wouldn't say that $B$ is unknown---I would say that it is arbitrary, or unspecified. The equations can be solved for any value of $B$.

(By the way, in this thread my goal is not to compute $B$. I'm interested in finding a definition that precisely describes the vague notion "The n+1st term of the sequence depends in an important way only on the previous k terms". )
As I said, it's not the sequence that has or fails to have this property, it's the definition. The same sequence can have more than one definition.

#### Stephen Tashi

In that case, I wouldn't say that $B$ is unknown---I would say that it is arbitrary, or unspecified. The equations can be solved for any value of $B$.
I can't agree with "arbitrary." because $B$ is defined as $lim_{k \rightarrow \infty} a_n$ (if the limit exits) and $\{a_k\}$ is a specific sequence.
As I said, it's not the sequence that has or fails to have this property, it's the definition. The same sequence can have more than one definition.
Yes, a sequence can have more than one definition (just as an integer can have more than one factorization), but there may be limitations on what choice we have in those definitions (just as there are limitations on whether an integer can be written, say, as a product of 3 distinct prime nuimbers). It is intuitively plausible that the sequence $\{a_k\}$ defined above cannot be defined with a "typical" recurrence relation where the n-th term depends in a significant way on only some fixed number of the previous terms. By "cannot", I don't merely mean "nobody knows how to do it". I'm thinking that if a precise definition of a "typical" recurrence relation can be created, it migh be possible to prove some sequences cannot be written as typical recurrence relations.

#### stevendaryl

Staff Emeritus
I can't agree with "arbitrary." because $B$ is defined as $lim_{k \rightarrow \infty} a_n$ (if the limit exits) and $\{a_k\}$ is a specific sequence.
I didn't think it was defined to be that limit. I thought that was an approach to computing it. $B$ is defined by the infinite expression

$B = \sqrt{2 + \pi \sqrt{3 + ...}}$

which is really not a definition at all, but is a relationship among infinitely many reals $b_2, b_3, b_4, ...$ where

$b_n = \sqrt{n + \pi b_{n+1}}$

If you have such a sequence, then $B = b_2$.

I suppose you can take the approximation scheme for infinite nested radicals as the definition of what the term means, in which case, it is a definition.

#### Stephen Tashi

I didn't think it was defined to be that limit.
I'm talking about how I defined it.

I thought that was an approach to computing it. $B$ is defined by the infinite expression
$B = \sqrt{2 + \pi \sqrt{3 + ...}}$
which is really not a definition at all,
Yes, it's just notation in search of definiiton.

but is a relationship among infinitely many reals $b_2, b_3, b_4, ...$ where

$b_n = \sqrt{n + \pi b_{n+1}}$

If you have such a sequence, then $B = b_2$.
That seems to be popular way of defining what the notation shall mean but since (my) $\{a_k\}$ and your $\{b_k\}$ are different sequences it isn't clear what the existence of a recurrence relation for one has to do with the existence of a recurrence relation for the other.

I suppose you can take the approximation scheme for infinite nested radicals as the definition of what the term means, in which case, it is a definition.
As I said, I'm not primarily interested in the value of $B$ however we choose to define it. I'm interested in classifying sequences according to limitations on how they can be defined. As you said, a sequence is recursive or not with respect to a particular definition of that sequence. However that implies that we can make a definition like: The sequence $\{q_n\}$is "essentially recursive" means there exists a recursive definition for $\{q_n\}$.

I suspect with a typical definition of "recursive", every sequence will be "essentially recursive". So I'm interested is a more restrictive definition of "recursive" - one that expresse the intuitive notion that not all sequences can be expressed as recurrence relations of some non-trivial type..

Last edited:

#### SSequence

I didn't think it was defined to be that limit. I thought that was an approach to computing it. $B$ is defined by the infinite expression

$B = \sqrt{2 + \pi \sqrt{3 + ...}}$

which is really not a definition at all, but is a relationship among infinitely many reals $b_2, b_3, b_4, ...$ where

$b_n = \sqrt{n + \pi b_{n+1}}$

If you have such a sequence, then $B = b_2$.

I suppose you can take the approximation scheme for infinite nested radicals as the definition of what the term means, in which case, it is a definition.
This is close to my thinking about this expression. However, there are some questions for which it would be interesting to have answers and/or proof. All the considerations below also apply to expression in the quoted post.

For example, suppose $a_0,a_1,a_2,a_3,a_4,.....$ is an infinite sequences of positive natural numbers. Now if we consider the following two expressions:
$E_0=\sqrt{a_0 + \sqrt{a_1 + ...}}$
$E_1=\sqrt{a_1 + \sqrt{a_2 + ...}}$
Then we can ask the following questions:
(Q1) Consider the following two sequences:
$\sqrt{a_0},\sqrt{a_0 + \sqrt{a_1}},\sqrt{a_0 + \sqrt{a_1+\sqrt{a_2}}},.......$
$\sqrt{a_1},\sqrt{a_1 + \sqrt{a_2}},\sqrt{a_1 + \sqrt{a_2+\sqrt{a_3}}},.......$

Is it true that the first sequence is convergent if and only if the second one is.

(Q2) Suppose both the sequences in (Q1) are convergent. If the first converges to a real number $r_0$ and the second to value $r_1$, then is it true that:
$r_0=\sqrt{a_0+r_1}$

==============

This isn't related to the main topic, but can we derive some more miscellaneous facts? For example, if we have $b_0,b_1,b_2,b_3,b_4,.....$ as a sequence of positive natural numbers such that $b_i>a_i$ for all $i \in \mathbb{N^+}$, and if the sequence in (Q1) is convergent for the sequence of $b$'s then corresponding real it converges to will be greater than one obtained by the sequence of $a$'s.

#### Stephen Tashi

This is close to my thinking about this expression. However, there are some questions for which it would be interesting to have answers and/or proof. All the considerations below also apply to expression in the quoted post.
The questions you have may be appropriate for the thread https://www.physicsforums.com/threads/recursive-square-root-inside-square-root-problem.954655/ , but how do they concern the topic of this thread, which is recurrence relations? For example, a sequence can satisfy a recurrence relation and not be convergent.

#### SSequence

For example, a sequence can satisfy a recurrence relation and not be convergent.
Yes, but the questions in post#14 try to consider a few more points.

Of course they still aren't that relevant to a "generic" notion of "recurrence relation" but they seem relevant to the casual notation of nested radicals (such as def. of $B$, $E_0$ and $E_1$ in post#14) ...... in terms of trying to understand better whether the casual notation has a degree of "coherence" or not.

My point was that the casual notation (for $B$, $E_0$ and $E_1$) seems to imply, for example, that if $b_3$ is convergent then $b_2$ is convergent (and vice versa) ...... in other words $b_2$ is convergent iff $b_3$ is. But if you take the definition of $b_2$ and $b_3$ as a sequence of concrete numbers, it isn't immediately clear. This is what I was trying to get at with (Q1) in post#14.

And secondly the casual definition also seems to suggests definitively that $b_2 = \sqrt{n + \pi b_{3}}$ (once it is established that both $b_2$ and $b_3$ are convergent). However, it isn't immediately clear when you take definition of $b_2$ and $b_3$ as a sequence of concrete numbers. This is what (Q2) was about.

P.S.
By $b_2$ and $b_3$ as sequence of concrete numbers I mean the limit of following sequences (first def. of $b_2$ and then $b_3$):
$\sqrt{ 2}, \sqrt{2 + \pi \sqrt{3} }, \sqrt{2 + \pi \sqrt{3 + \pi \sqrt{4}}},....$
$\sqrt{ 3}, \sqrt{3 + \pi \sqrt{4} }, \sqrt{3 + \pi \sqrt{4 + \pi \sqrt{5}}},....$

Last edited:

#### Stephen Tashi

Of course they still aren't that relevant to a "generic" notion of "recurrence relation" but they seem relevant to the casual notation of nested radicals (such as def. of $B$, $E_0$ and $E_1$ in post#14).
However, the topic of the thread isn't the convergence of sequences of nested radicals. I think nested radicals and the ambiguities of notation involving "$....$" are fascinating topics, but please start a different thread to discuss them. Otherwise this thread will get hijacked by a big digression into nested radicals.

#### SSequence

Alright sure, I wasn't trying to derail the thread. I was just pointing that out mostly as a separate post. I found this interesting (and it seemed "partly" relevant what was being discussed in the preceding posts in the thread). But if as OP you think this digresses from the main discussion, no problem.

#### Stephen Tashi

I'll try these definitions:

Definition 1: A sequence $\{a_i\}$ is recursive means that there exists a positive integer $k$ and a function $f$ such that for each integer $n > k$, the n-th term of the sequence satisfies $a_n = f( a_{n-1}, a_{n-2}, ...a_{n-k})$

The function $f$ together with the integer $k$ shall be called a recurrence relation for the sequence $\{a_i\}$.
I'm want Definition 1 to be worded so $f$ is not a function of $n$. Definition 1 makes no assumption that a sequence has a unique recurrence relation or that a recurrence relation defines a unique sequence.

Definition 2: A sequence $\{a_i\}$ is recursively definable means that there exists a recurrence relation $\{f,k\}$ for $\{a_i\}$ such that $\{a_i\}$ is the unique sequence having initial terms ${a_1,a_2,...a_k}$
Now to deal with the problem that the sequence defined by

$a_1 = 1$
$a_n = g(a_{n-1}, n) = 2 a_{n-1} + 3n \$ [eq. 1]

seems (intuitively) to be recursive even though eq 1: $a_n = 2 a_{n-1} +3 n$ is not a recurrence relation due to the presence of "n" in the argument list of $g$.

The general idea is to express $n$ as some function of the terms of the sequence.

From eq. 1, we have $3n = a_n - 2 a_{n-1}$.

Applying eq. 1 to compute $a_{n+1}$:
$a_{n+1} = 2 a_n + 3(n+1) = 2 a_n + 3n + 3 = 2a_n + (a_n - 2a_{n-1}) + 3$
$a_{n+1} = 3 a_n - 2 a_{n-1} + 3$
Reindexing gives:
$a_{n} = 3 a_{n-1} + 2 a_{n-2} + 3$.

$f(a_{n-1},a_{n-2}) = 3 a_{n-1} + 2 a_{n-2} + 3$ does satisfy the definition of a recurrence relation for the sequence but it requires specifying $a_0$ and $a_1$ to uniquely determine the sequence.

What can be done for the general case where the a sequence is specified by $a_n = g(a_{n-1}, n)$ and the function $g$ is not so simple? I think that some such sequences are not recursive. Which ones are?

"The general notion of a recurrence relation"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving