Questions tagged [recursion]
Recursion is the process of repeating items in a self-similar way. A recursive definition (or inductive definition) in mathematical logic and computer science is used to define an object in terms of itself. A recursive definition of a function defines values of a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory
2,938 questions
10
votes
5
answers
1k
views
Why Does Tao Use Inductive Language When Giving Recursive Definitions?
I’ve read similar questions, but the answers I found were either contradictory or too advanced for my current level. I’m a computer engineering student, and I’m trying to understand a point in Terence ...
- 111
5
votes
1
answer
145
views
Theorem 3.4 of Soare
I am reading Robert I. Soare's "Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets" for a directed reading course. I am having trouble ...
2
votes
0
answers
41
views
matrix methods to solve linear double recursions
One might solve linear recursions in one variable using the characteristic polynomial (or something similar.) The most famous example might the the Fibonacci sequence via the roots of the ...
1
vote
0
answers
71
views
Sequence of polynomials defined by recursion
Consider the following sequence of even polynomials $f_k:[0,1]\to\mathbb R$ ,
$$ \begin{cases} \,f_k(x)\,= \frac{(1-x^2)^2}{2}\,f_{k-1}''(x) \quad \textrm{for } k\geq 2\\ f_1(x)=x^2
\end{cases}$$
I ...
- 951
2
votes
1
answer
117
views
Is function defined by infinite cases partial recursive?
I am trying to prove that a certain function is partial recursive. Suppose we have fixed primitive recursive $g:\mathbb{N} \rightarrow \mathbb{N}$ and for each $d$ let $f_d:\mathbb{N}\rightarrow \...
- 167
4
votes
1
answer
151
views
Can superposition alone generate the Kalmár elementary function $x^y$ from $⟨x + y, x \bmod y, 2^x⟩$?
In Mihai Prunescu, Lorenzo Sauras-Altuzarra, and Joseph M. Shunia (2025), A Minimal Substitution Basis for the Kalmar Elementary Functions, the authors define a minimal generating set for the Kalmár ...
- 41
1
vote
2
answers
173
views
Proving that a recursive function is unique - Tao's Analysis
In Exercise $3.5.12$ in Tao's Analysis $1$, he asks the following:
Let $X$ be a set, and $f:\mathbb{N} \times X \to X$ and let $c \in X$. Prove that there exists an $a:\mathbb{N} \to X$, such that (i)...
- 163
0
votes
0
answers
60
views
Simplifying a recurrence relation
I have two sets of variables denoted $c_{n,m}$ and $\beta_n$, where $n,m \geq 0$ are integers. We assume $n\geq m$. These variables obey the recurrence relations
$$
\begin{align}
c_{n+1,m}&= c_{n,...
- 391
7
votes
1
answer
236
views
Gödel’s Incompleteness Theorems for primitive recursive arithmetic (PRA) without unbounded quantifiers
Gödel's Incompleteness Theorems apply to formal systems $T$ that can represent the provability predicate $\text{Prov}_T(y)$ so that $T\vdash\text{Prov}_T(\ulcorner\psi\urcorner)$ whenever $T\vdash\psi$...
- 373
1
vote
0
answers
114
views
Proof techniques to analyze a recursively defined estimator
I’m studying a recursively defined estimator and want to prove consistency. The estimator is not merely computed by a recursive algorithm—the value on a sample is defined (also) through values on sub-...
- 159
7
votes
0
answers
125
views
Recurrence relation: $a_n=a_{n-1}+\frac{4}{a_{n-1}}$ where $a_1=4$
So the question is as follows:
We shall define a sequence $(a_n)_{n=1}^{\infty}$ as follows: Let $a_1:=4,$ and for all $n\ge 2,$
$$a_n=a_{n-1}+\frac{4}{a_{n-1}}.$$
Now the question originally asked ...
- 717
1
vote
1
answer
104
views
Recursive functions are $\Sigma_1$ in PA? [duplicate]
I am working with recursive functions on $\omega$. It is well known that these functions are representable, in the sense of the following definition:
A function $f:\omega\to\omega$ is representable in ...
- 164
0
votes
0
answers
38
views
Finding the generalized inverse of $A_{n \times n}$ recursively
Suppose I have a matrix $A_{n \times n} , n \ge 2$. Let $n_1,n_2,\cdots,n_k$ be natural numbers such that $\sum_{i=1}^k n_i = n.$ Define $n_i^* = n_1+\cdots+n_i$ Then , $A$ can be partitioned as :
$\...
- 9,340
1
vote
1
answer
105
views
How to convert Boolean algebra recursive function to closed form?
Given a recursive Boolean function $$
f(t) =
\begin{cases}
\text{false} & \text{if} & t \le 0 \\
g(t) & \text{otherwise}
\end{cases}
$$ where $t$ is an integer and $g$ is a function ...
- 11
0
votes
0
answers
183
views
Does Adding Tennant's Principle of Uniform Primitive Recursive Reflection to PA Yield A Decidable Axiom Set?
The title is my question. What follows explains why it is important to me and perhaps others.
In 1931 Godel announced his two incompleteness results for formal systems of arithmetic equivalent to PA-- ...
2
votes
1
answer
85
views
Is this recursively-defined self-referential divisibility sequence infinite?
I came across a curious recursively defined sequence that seems to "count its divisibility pattern."
Definition of the sequence $(a_n)_{n \ge 1}$:
$a_1 = 1$
For $n > 1$,
$$
a_n = \min ...
- 3,613
4
votes
2
answers
235
views
Hermite polynomial integral from zero to infinity
I want to find an analytical expression or a recursion formula for the integral
$$\int\limits_0^{\infty} H_{2n}(x) x H_{2n'}(x) e^{-x^2} \, dx \, ,$$
with $n,n' \in \mathbb{N}$.
I did't get somewhere, ...
8
votes
2
answers
382
views
When constructing primitive recursive functions, can you modify the parameter?
Let $g(a), h(a,n,b), p(a)$ be primitive recursive functions. Consider the function $\phi(a,n)$ defined recursively by
$$
\phi(a,0) = g(a) \\
\phi(a,sn) = h(a,n,\phi(p(a), n))
$$
Question: Is $\phi$ ...
- 7,684
1
vote
1
answer
65
views
Simplification of a highly recursive function with relation to geometry
I want the function:
$f(1)=p(x,a)\\
f(2)=p(p(x,a),a+1)\\
\vdots\\
f(n)=\underbrace{p(p(\cdots p}_{n\text{ times}}(x,\underbrace{a),a+1),\cdots,a+n-1)}_{n \text{ times}}$
Where $n \in \mathbb{Z}$. ...
1
vote
1
answer
95
views
Clarification on the meaning of "any program" in Sipser's explanation of the Recursion Theorem
I'm reading Michael Sipser's Introduction to the Theory of Computation, and I came across the following statement in the section on the Recursion Theorem:
"The recursion theorem provides the ...
- 315
3
votes
0
answers
86
views
Can you have a nested recursively deepening hyperbolic fractal structure?
I am staring at this basically, from Margenstern's work on Cellular Automata in Hyperbolic Spaces, like this paper About the embedding of one dimensional cellular automata into hyperbolic cellular ...
- 3,965
0
votes
1
answer
46
views
Closed formula for intertwined additive and multiplicative sequences
Let integers $m_1=1$ and $n_1=2$.
Define the recursion $m_i=n_{i-1}^2$ and $n_i=2m_{i-1}$.
Is there a closed formula for this sequence at any index $i\in\mathbb N$ and what is their growth?
Is it ...
- 6,341
1
vote
1
answer
98
views
Using the construction in Kleene's recursion theorem to build a quine
Kleene's recursion theorem guarantees that, for every computable function $f$, there is a program $e$ such that $e$ and $f(e)$ compute the same function, or equivalently, $\varphi_e(x) \simeq \varphi_{...
- 3,595
1
vote
0
answers
123
views
Is the set of primitive recursive functions recursive?
This question has probably been asked elsewhere, but I cannot for the life of me find the answer. I understand as follows: set of primitive recursive functions is not enumerable by some primitive ...
- 972
5
votes
3
answers
659
views
Evaluating $\lim_{n\to\infty} f(n)$, where $f(1)=f(2)=0$, $f(3)=1$, and $f(n)=\frac13(f(n-1)+f(n-2)+f(n-3))$ for integer $n\geq4$
Let $f : \mathbb{N} \to [0,1]$ be a function defined by $$
f(n)=\frac{f(n-1) + f(n-2) + f(n-3)}{3},\ n\geq 4$$
with $f(1) = f(2) = 0$ and $f(3) = 1$.
Find the value of $$L = \lim_{n\to\infty} f(n)$$
...
- 622
0
votes
2
answers
175
views
A Puzzling Sequence [closed]
Define $f(n)$ as
if $n$ is even, $$f(n)=\frac{f(n-1)}{f(n-2)}$$
if $n$ is odd,
$$f(n)=f(n-2)-f(n-1)$$
and $$f(1)=a, f(2)=b$$
where $a,b$ are real numbers.
Can you find $a, b$ such that $$\lim_{n \to \...
- 131
1
vote
2
answers
104
views
What iterative solution method to employ when recursion diverges?
I have a function for which I am trying to find the solution iteratively.
$y = x \cdot tan(x)$
I know $y$, I'm searching for $x$. I am trying to solve the problem by coding it, so I wrote a recursion ...
- 123
1
vote
1
answer
60
views
Is it an accepted way to define a function which recursively iterates over a set as $f(\{e\}\cup S\backslash\{e\})=\ldots$?
While trying to learn how to define a function which iterates over a set, I stumbled upon a technique which relies on splitting an element away from its set to be able to perform recursion.
In class I ...
- 13
25
votes
4
answers
2k
views
Minimal path to touch every square's area in an n by n grid
Consider an $n$ by $n$ square subdivided into unit squares. What is the shortest path you can take through the square that touches every unit square? Touching the edges/vertices of the squares is ...
- 363
8
votes
1
answer
392
views
Polynomial recursive relation: a conjecture for the solution
I have a family of polynomials $P_{n,j}(x)$ defined by the following recursive relation: for all $n\geq 1$ and for all $1 \leq j\leq n,$
$$P_{n,j}(x)=P_{n,j-1}(x)-\sum_{i=1}^{j-1}P_{i,i}(x)P_{n-i,j-i}(...
- 1,086
0
votes
0
answers
44
views
Value of $3-\sum_{k=2}^\infty\frac{1}{(k-1) \cdot k \cdot k!} $ [duplicate]
I am trying to find the limit of the sequence $a_n$ defined by the initial term $a_1=3$ and the recurrence relation: $$a_n = a_{n-1} - \frac{1}{(n-1) \cdot n \cdot n!}, \quad \text{for } n = 2, 3, \...
- 423
6
votes
3
answers
323
views
Finding $\lim_{n\rightarrow \infty}x_n$
Let $\forall n\ge 1$
$$\begin{align}x_n^2- 2(x_n+1)x_{n+1}+2024 &= 0\end{align}$$ Given that $x_1=2024$ find $$\lim_{n\rightarrow \infty}x_n$$
The best I could do here was factorize like this
$$(...
- 879
1
vote
2
answers
76
views
$\prod_{i=1}^n (1+\delta_i)=1+\theta_n$ and inequality [closed]
I was reading this paper on floating point numbers but I didn't understand why if $|\delta_i| \le u$ for $i=1:n$ then $$\prod_{i=1}^n (1+\delta_i)=1+\theta_n$$ where $\theta_n \le \frac{nu}{1-nu}.$
- 1,813
4
votes
1
answer
158
views
Proving a relation among powers of a $\pm 1$ skew-symmetric matrix
I have a skew-symmetric $n\times n$ matrix $M$ such that all its upper-triangular entries are $1$:
$$ M_{i,j} = \begin{cases} \,\,\, 1 & \text{ if } i < j \\ \,\,\, 0 & \text{ if } i = j \...
- 113
1
vote
2
answers
172
views
Proving a Recursion Formula for an Integral $ I_n = \int_0^1 x^n e^x \,dx $ and Evaluating Its Limit
Consider the integral:
$$
I_n = \int_0^1 x^n e^x \,dx
$$
Using integration by parts, one obtains the recursion relation:
$$
e = I_n + n I_{n-1}
$$
Using Wolfram-alpha this can be rewritten as:
$$
I_n =...
3
votes
1
answer
149
views
Calculating sine using nested square roots: what is this? Has this been discovered before? [closed]
A while ago, I found that any sine value could be expressed using the square root of two.
The famous example is when the input is $\frac{\pi}{4}$, being $\frac{\sqrt2}{2}$
However, another example is ...
- 39
0
votes
0
answers
98
views
Recursion Theorem proof by Halmos should require exactly one $x$ for any $n$?
We want to proof the existence of a function $u: \omega \to X$ such that $u(0) = a$ and $u(n^+) = f(u(n))$ for some $a \in X$ and some $f: X \to X$.
The proof is done by considering the function whose ...
- 403
3
votes
2
answers
119
views
(Co)recursion: what is the significance of the functor F and the coalgebra $X\to FX$?
I'm trying to understand what the categorical definition of (co)recursion means. Here's the relevant excerpt from nLab:
Corecursion exploits the existence of a morphism from a coalgebra for an ...
- 1,832
0
votes
1
answer
94
views
Recursive to explicit/closed form [duplicate]
A similar question has been asked before but I haven't seen an answer to this specific one after looking for so long.
I have a recursive function where:
$P(2) = 1$
For $n ≥ 3$, $P(n) = (n-2)P(n-1) + ...
- 69
3
votes
1
answer
181
views
Is the equation $a^4+b^4+c^4=2d^2$ with $a=b\,$ completely solved by $x^4-2y^4=\pm z^2$?
In this answer, to solve $a^4+a^4+b^4 = 2d^2$ the author uses a nice recursion. Assume primitive solutions with $\text{gcd}(a,b)=1$.
I. Recursion 1
Starting with,
$$1^4+1^4+2^4 = 2\times\color{blue}{...
- 61.1k
4
votes
2
answers
317
views
Closed form of function from recursive definition
Define $f(x)$ for positive integer $x$ as $$f(x) = (2^x - 1)^n - \sum_{j = 1}^{x - 1}\binom{x}{j} \cdot f(j)$$where $n$ is some constant and $f(1) = 1$. I want to determine $f(x)$ explicitly. Here is ...
- 311
1
vote
0
answers
83
views
Using the monotone convergence theorem to prove odd and even subsequences
{$a_n$} is a sequence with $a_1\gt a_2 \gt0$ defined as:
$$
a_{n+2} =\frac{a_{n+1}+a_n}{2}, n\geq3$$
An answer using characteristic polynomials of the recurrence already exists at the link. I am ...
- 2,674
0
votes
0
answers
61
views
Solve Recurrence Relation with Master theorem Case 3
I need your help with the following problem:
I’m supposed to find a simple function $ g(n) $ for the recurrence relation
$ T(n) = 9 \cdot T\left( \lceil \frac{n}{4} \rceil \right) + 3^n $
with the ...
- 43
7
votes
1
answer
276
views
Exponential Limit Estimation
Background: this came from a casual discussion about the compound interest problem.
Consider the function $f(a,b),a\in\Bbb N, b\in\Bbb R\setminus\{0\}$ where
$f(0,b)=1+\frac{1}{b}$,
for $a\neq 0$, $f(...
- 609
1
vote
1
answer
97
views
If $F$ is $\sf{ELEMENTARY}$-time computable, then $F$ is Elementary Recursive
The Elementary Recursive functions are, roughly speaking, all the functions $\mathbb{N}^k\to \mathbb{N}$ which are definable using only $\sum$ summation and $\prod$ product notation. The complexity ...
- 5,103
0
votes
0
answers
65
views
Linear recursion
I am new to recursion in general and not acquainted with much knowledge on linear algebra. question here
Our teacher had given us an assignment in functions, which had this question:
Now, It can be ...
- 1
1
vote
1
answer
200
views
Explain how to find this formula from the recursion in this paper
I am trying to understand how to find this formula, which seems straight forward, but I am missing something.
In page 20 of this paper (or thesis):
https://egrove.olemiss.edu/cgi/viewcontent.cgi?...
- 1,112
0
votes
1
answer
61
views
solve a recursion formula using a generating function
I have the following formula for a vector $v_n= \ ^t(a_n, b_n)\in \mathbb R^2$ :
$v_n= Av_{n-1}+ Bv_{n-2}$ for two given matrices $A$ and $B$ in $M_2(\mathbb R)$, and we are given $v_1$ and $v_2$ of ...
- 1,112
2
votes
0
answers
116
views
Prove the principle of strong recursion and apply it to the definition of the factorial function.
I need help solving this exercise: Prove the principle of strong recursion and apply it to the definition of the factorial function.
I have attempted to solve it and am presenting the definitions ...
0
votes
0
answers
32
views
Infinite dimensional fixed points and the Mandelbrot set bibliography question
For context: I am studying an electrodynamics problem which iterates recursively. I am doing everything numerically. The idea is (in the context of flat 1+1 dimensional spacetime with a scalar field):
...
- 131