Questions tagged [recursion]

Question 1

I have a DAG where every node has a (usually small) set of candidate integers. A candidate a is compatible with b if (a | b) or (b | a). For every root I want to choose one candidate per node to ...

Question 2

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 ...

Question 3

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 ...

Question 4

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 ...

Question 5

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 ...

Question 6

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 \...

Question 7

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 ...

Question 8

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)...

Question 9

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,...

Question 10

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$...

Question 11

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-...

Question 12

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 ...

Question 13

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 ...

Question 14

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 : $\...

Question 15

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 ...

Stack Exchange Network

Questions tagged [recursion]

Max–min assignment on a DAG when nodes have candidate values with compatibility constraints

Why Does Tao Use Inductive Language When Giving Recursive Definitions?

Theorem 3.4 of Soare

matrix methods to solve linear double recursions

Sequence of polynomials defined by recursion

Is function defined by infinite cases partial recursive?

Can superposition alone generate the Kalmár elementary function $x^y$ from $⟨x + y, x \bmod y, 2^x⟩$?

Proving that a recursive function is unique - Tao's Analysis

Simplifying a recurrence relation

Gödel’s Incompleteness Theorems for primitive recursive arithmetic (PRA) without unbounded quantifiers

Proof techniques to analyze a recursively defined estimator

Recurrence relation: $a_n=a_{n-1}+\frac{4}{a_{n-1}}$ where $a_1=4$

Recursive functions are $\Sigma_1$ in PA? [duplicate]

Finding the generalized inverse of $A_{n \times n}$ recursively

How to convert Boolean algebra recursive function to closed form?

Hot Network Questions