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

Filter by
Sorted by
Tagged with
0 votes
2 answers
31 views

How to prove the following statement regarding the successor function and addition of natural numbers?

Natural numbers (including 0) and the successor function are defined as per the Peano Axioms (you can check them on wikipedia). Addition is defined recursively as follows: $a+0=a$ $a+S(b)=S(a)+b$ With ...
user avatar
6 votes
3 answers
365 views

Proving a recursive formula is indeed a function

Recently, I have been studying induction proofs, because I wanted to learn about all kinds of different proof techniques. However, I have been stuck now on this particular exercise for a while now. ...
user avatar
  • 415
4 votes
2 answers
95 views

An interesting recurrent equality, possibly easier to solve in its differential form?

I encountered an interesting inequality that I'm not sure how to approach. Here $c$ is a positive constant. $$f(n+1) - f(n) = c f(n)\sum_{m=0}^n f(m)$$ I am not familiar with techniques to solve ...
user avatar
  • 475
-1 votes
0 answers
16 views

Why does not the second recursion theorem guarantee a lest fixed point?

What does it mean that the first recursion theorem guaranties the existence of the lest fixed point, but the second one does not? If there is at least one (pseudo) fixed point then there must be a ...
user avatar
0 votes
0 answers
27 views

Trouble understanding a simple exercise about primitive recursion on natural number set theory.

Consider the function $f: \omega \rightarrow P\omega$ defined recursively through: \begin{equation*} \omega \in P\omega \quad \text{and} \quad h : \omega \times P\omega, (n,A) \rightarrow \{n^+ + k \...
user avatar
  • 599
3 votes
2 answers
137 views

Possible positions of the knight after moving $n$ steps in Chessboard.

Problem There is a knight on an infinite chessboard. After moving one step, there are $8$ possible positions, and after moving two steps, there are $33$ possible positions. The possible position after ...
user avatar
  • 843
2 votes
1 answer
79 views
+50

How do you prove the existence of the addition function without pre-supposing it?

Context: self-study from Smullyan and Fitting's Set Theory and the Continuum Problem (revised ed., 2010). So I have this question, which is exercise 8.4 (a) in Chapter 3 (page 44 of Dover edition). ...
user avatar
  • 4,038
1 vote
1 answer
29 views

Existence of initial conditions for the convergence of a recursively defined sequence to zero

Motivation Consider a sequence $m_k$ of non-negative real numbers satisfying the following recursion : $0<m_0 <1$ and there exists constants $C>0,D>1,q>1$ such that $$ m_{k+1} = C \...
user avatar
1 vote
0 answers
25 views

Prove that the following recursive functions (defining addition) are equivalent for all natural numbers

$S$ represents the successor function. $S(0)=1, S(1)=2, S^{-1}(3)=2$ and so on. First definition: $$a+b=sum1(a,b)\\ sum1(a,b)=a, \rm{if\ } b=0\\ sum1(a,b)=S(sum1(a,S^{-1}(b))), \rm{if } \neg b=0$$ ...
user avatar
0 votes
1 answer
28 views

Recurrence Equations: Uneven amount of letters

I have a recurrence relation problem that states the following: Given the alphabet $\sum = \{a,b,c\}$ how many words can be formed that have an uneven amount of "a"'s From my understanding: ...
user avatar
0 votes
0 answers
27 views

Solving the recurrence relation $\mathcal{T}(n) = \sqrt{n}\text{ }\mathcal{T}(\sqrt{n}) + \mathcal{O}(n^{2}) $

Given Recurrence Relation $$\mathcal{T}(n) = \sqrt{n}\text{ }\mathcal{T}(\sqrt{n}) + \mathcal{O}(n^{2}) $$ Master Theorem doesn't apply here. Tried using $n= 2^{k}$, but got stuck at $$\mathcal{T}(2^{...
user avatar
1 vote
0 answers
14 views

Analytical expression for tetrahedral progression

During my engineering studies we did get some Calculus and Algebra background, but I have a lack of knowledge in other topics such as Combinatorics, Recurrences and Progressions. Therefore I would ...
user avatar
-3 votes
2 answers
37 views

Finding sequence [closed]

I'm looking for the pattern of this series -> $1, 2, 1, 2, 1, 2$. Any help would be appreciated. $S_k = 2/S_{k-1}, k \in \mathbb{Z}, k \ge 2, S_1 = 1.$
user avatar
0 votes
0 answers
71 views

Is this formula stable? $\frac{|x|-|y|}{x-y}$ as $x$ approaches $y$.

I want to analyze the stability of this formula $\frac{|x|-|y|}{x-y}$ as $x$ approaches $y$. But this formula is not a recursion! I used to analyze the stability of recursion by computing the first n ...
user avatar
  • 1
1 vote
0 answers
17 views

Solving recurrence with boundary conditions on both sides

I want to solve the following recurrence, for any parameter $x>0$: $ a[i]= \frac{1}{x} a[i+1]+ (1- \frac{1}{x}) a[i-1]$ for $i \in \{1,...,n-1\}$ $a[0]= 0, a[n]=1$. i.e. find a closed form for $a[i]...
user avatar
  • 133
1 vote
1 answer
53 views

Solving self-consistent equations

I am attempting to use python to programmatically calculate the values in a dataset given the following equations: \begin{align} f_{ij} = \frac{g_{ij}}{\sum_{k} g_{ik}} \\\\ g_{ij} = \frac{...
user avatar
2 votes
1 answer
63 views

How can I find an analytic solution to a recursive sum such as this one? [closed]

I am looking for a closed-form, analytic solution to the following recursive formula: $g(m) = -\sigma + \frac{\sigma \kappa}{1 - \beta}\sum_{l=1}^{m}(1 - {\beta}^{l})g(m-l), \forall m>0$ where $g(0)...
user avatar
1 vote
3 answers
72 views

If I define summation recursively, how do I prove formally that both of the following definitions are equivalent?

First definition: $\sum_{x=a}^{b} f(x)=f(b)+\sum_{x=a}^{b-1} f(x)$ if $a\leq b$, and equals $0$ otherwise Second definition: $\sum_{x=a}^{b} f(x)=f(a)+\sum_{x=a+1}^{b} f(x)$ if $a\leq b$, and equals $...
user avatar
0 votes
0 answers
41 views

How to define $n!$ using recursion theorem?

I am wondering that how can we define a map that is required by recursion theorem which can be used to define $n!$ to make it have properties that followed:1.$0!=1$ 2.$(n+1)!=(n!)(n+1)$. The recursion ...
user avatar
0 votes
0 answers
16 views

PDE with mass immigration and mass killing at zero

I am interested in the following PDE: Let $1> \alpha > \frac12$ and $$\frac{d}{dt} f(x,t) = \frac{d}{dx} f(x,t) + \alpha (x+1)^{-\alpha -1} \left[1- \exp\left(-f(0,t)\right)\right], \mbox{ for }...
user avatar
  • 381
0 votes
1 answer
30 views

Closed form of a recursive integral

I have a recursive integral, $f(T) = f(0) + \frac{\gamma}{2} \int_{0}^T f(t)^2 dt$ where $f(0) \in \mathbb{R}^+$, $\gamma \in \mathbb{R}$ and $T \in \mathbb{R}^+$ all take known numerical values. Is ...
user avatar
  • 15
0 votes
1 answer
39 views

Inductive proof for recursive function

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists over the alphabet. I've encountered the following function: $f([])=[]$ $f([x])=[x]$, for $x \in \Sigma$ $f(x:L)=f(L)$, for $x \in \Sigma$ ...
user avatar
  • 11
5 votes
1 answer
89 views

Find number of functions such that $f(f(x)) = f(x)$, where $f: \{1,2,3,4,5\}\to \{1,2,3,4,5\}$ [duplicate]

Consider set $A=\{1,2,3,4,5\}$, and functions $f:A\to A.$ Find the number of functions such that $f\big(f(x)\big) = f(x)$ holds. I tried using recursion but could not form a recursion relation. I ...
user avatar
  • 51
0 votes
1 answer
44 views

How to write the general solution for the recurrence relation: $x_{n+1} = x_n e ^ {\frac{1}{x_n}}$?

Consider the sequence $(x_n)_{n\geq0}$, with $x_0>0$ and satisfying the recurrence relation: $$x_{n+1} = x_n e ^ {\frac{1}{x_n}},$$ how you go about writing $x_n$ in terms of $x_0$, and the ...
user avatar
0 votes
0 answers
33 views

infinite recurrence relation

I am trying to solve the following recurrence relation $$ a_{2k} = 3 \theta^2 a_{2k-2} + 12 \theta^4 \sum_{l=1}^{k-1} (7 \theta)^{l-1} a_{2k-2l-2}, $$ with initial condition $a_{0} = 1$. Here $\theta \...
user avatar
0 votes
1 answer
58 views

Primitive Recursion representation in first order PA (Gödel theorems)

I'm a bit confused on the reasons why when proving that primitive recursion rule is representable in a PA first order theory one has to utilize ways such as the Gödel function to encode finite ...
user avatar
0 votes
0 answers
53 views

Is this partition formula known?

Let $P(n)$ be the number of partions of $n$, and $P(n,k)$ the number of partions of $n$ using exactly $k$ positive summands. Then I found that \begin{align} P(n) = 1 + \sum_{k=1}^{\lfloor \frac{n}{2}\...
user avatar
0 votes
0 answers
17 views

Proving a recursively defined mapping is right-unique and left-total [duplicate]

The question was originally written in German, but from what I understand, the gist is, that I'm supposed to show that the mapping is both left-total and right-unique. Let A be a set, $a \in A$ and $h:...
user avatar
2 votes
2 answers
101 views

Generate an explicit formula for: $a_n=a_{n-1}+n^2-5n+7, a_3=2$

So I'm currently solving this math homework problem and I've set up a recursive formula: $a_n=a_{n-1}+n^2-5n+7; a_3=2$ Right now, I'm having trouble as to where to start. I was listing out the cases ...
user avatar
4 votes
1 answer
61 views

How many multiples of 7 contain a 7 in their decimal representation?

The first few multiples of $7$ that contain a $7$ in their decimal representation are $7, 70, 77, 147, 175, 217 ..$ (OEIS A121027). My question is how many such numbers exist below $n$: $$ f(n) = \...
user avatar
0 votes
1 answer
23 views

Is there a sense in which a countably generated sigma-field is computable?

This is a bit of a soft question because I'm not very strong in computability and recursion theory, but here goes. In measure theory, one starts with a measurable space $(\Omega, \mathcal F)$, which ...
user avatar
  • 7,931
0 votes
0 answers
24 views

Transform recursive exponential sequence with multiple factors to explicit

Take $$A_n = A_{n-1}^2 + A_{n-1}$$ This is a recursive formula for the sequence $(A_n)$ But I need an explicit formula for this sequence, does anyone know how to transform this expression to an ...
user avatar
3 votes
3 answers
64 views

Recursion for the number of words of length $n$ over the alphabet $\{0, 1, 2\}$ such that there are neither $11$ nor $22$ blocks

Let $a_n$ be the length of words over an alphabet $\{0,1,2\}$ such that there are neither $11$ nor $22$ "blocks". I. e. $001020$ would be allowed, $001120$ wouldn't because we have a $11$ ...
user avatar
  • 1,887
1 vote
2 answers
76 views

Solving recursive equation without Master's Theorem

Cheers, I am asked to find the time complexity of a recursive algorithm, which splits the starting problem on $\sqrt{n}$ subproblems, of size $\sqrt{n}$ each, and then combines the solution in linear ...
user avatar
0 votes
1 answer
26 views

problem with recurrence relation

Given that : $\ U_{0} =\frac{3}{4} $ $\ U_{n+1} = \frac{U_{n}^2}{2U_{n}^2-2U_{n}+1}, n \in \mathbb{N}$ The question was to prove by recursion that : $\ \frac{1}{2}\lt U_{n} \lt 1$ I tried to solve ...
user avatar
  • 101
1 vote
1 answer
20 views

Equidistant "Recursive" form to explicit form

Let $$x_i = \frac{x_{i+1}+x_{i-1}}{2} \quad \text{for $i \in \{2,...,k\}$}$$ and $x_0 = 1$, $x_{k+1}=0$ I want to prove that $x_i = 1-\frac{i}{k+1}$ I noticed that $$x_i = \frac{x_{i+1}+x_{i-1}}{2}=\...
user avatar
  • 1,406
2 votes
1 answer
47 views

Closed form formula instead of recursive sequence [closed]

I'm trying to create a computational model for a neuroscience project, but the computation times are too long for it to be useful. In particular, there is an iterative recursive step that is too slow (...
user avatar
  • 21
0 votes
1 answer
32 views

Recursive function producing a sequence of disjoint sets

$f : X \to X$ is an injective function. The recursive sequence of sets $Z_0, Z_1, Z_2,\dots$ is defined by the following rules: 1) $Z_0 = X \setminus f(X)$ 2) $Z_{n+1} = f(Z_n)$ for any $n \geq 0.$ ...
user avatar
1 vote
2 answers
30 views

Calculating the number of possible paths from an arbitrary starting point

I have a grid of size $n\times n$, where the origin is set at $(0,0)$ and the coordinates of the points on this grid, can only be positive. Let's say that we start at the point $(i,j)$. We can only go ...
user avatar
  • 532
1 vote
1 answer
94 views

How to more rigorously formalise “value of (Weaver's) P-name” in set theory forcing (recursion)?

Background I have been reading some introductory material on forcing, specifically Nik Weaver's Forcing for mathematicians. What Weaver calls a “$P$-name”, I will call “Weaver's $P$-name” because it ...
user avatar
2 votes
1 answer
47 views

Recursively generate 3-regular planar graphs

I'm trying to prove that there are an unbounded number of (non-isomorphic) 3-regular planar graphs with faces of degree 3 or 6. I know that there are only 4 faces of degree 3 in such a graph. I cannot ...
user avatar
  • 23
1 vote
3 answers
93 views

solve the recurrence relation $a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $

Solve the recurrence relation $$a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $$ With initial conditions: $a_0 = −2$ $a_1 = 0$ $a_2 = 5$ I solve the homogenous part like that: $$a_n - 7a_{n-1} + 16a_{...
user avatar
  • 11
0 votes
1 answer
44 views

Iteration (very basic question on terminology)

A finitary union of sets $\bigcup_{n=1}^{n} S_i \leftrightarrow S_1 \cup S_2 \cup \ldots S_n$ or a series such as $\sum_{n=1}^{n} 2^{-n} = 1$, they all represent the same generic operation of ...
user avatar
  • 507
2 votes
1 answer
69 views

Why is there a pattern in exponents where x^y and (x+1)^y increases by y! "accelerated" by y in?

I've noticed with exponents a certain pattern that occurs. 1^2=1 | 2^2=4 | 3^2=9 | 4^2=16 | 5^2=25 1+3 =4 | 4+5 =9 | 9+7=16 | 16+9=25 You find 3, 5, 7, and 9; all 2 in between. It takes 2 times of ...
user avatar
  • 21
0 votes
2 answers
29 views

Solving a recursive equation system with max operator

I have this set of equations: $y=1+0.5x$ $x=1+max(0.5y,0.5c)$ Where $c$ is some constant. I am wondering what way is there to solve this.
user avatar
  • 113
0 votes
0 answers
25 views

Let $a_1=1$, for each $n\geq 1$ let $a_{n+1}=\sqrt{3+2a_n}$. Prove with induction that for all $n\in\mathbb{N}$, we have $a_{n}\leq a_{n+1}\leq 3.$ [duplicate]

Let $a_1=1$ and for each $n\geq 1$ let $a_{n+1}=\sqrt{3+2a_n}$. Prove with induction that for every $n\in\mathbb{N}$, we have $$a_{n}\leq a_{n+1}\leq 3.$$ For the base case $n=1$, I already know it ...
user avatar
1 vote
0 answers
28 views

How to solve recursive equation $ T\left(n\right)=\sqrt{nT\left(\sqrt n\right)+100n}$

I saw this equation somewhere : $ T\left(n\right)=\sqrt{nT\left(\sqrt n\right)+100n}$ and I have really no idea how to solve it. clearly, it can not be solved using Master Theorem directly. also I ...
user avatar
1 vote
3 answers
91 views

How can I solve this recurrent equation? [closed]

...
user avatar
  • 23
1 vote
0 answers
33 views

Expected Value of First Number over 12

We roll a fair 6 sided die and keep a running sum $S$ of the rolls so far. We stop as soon as $S$ is greater than 12. What is the expected value for $S$. The simplest approach I can think of is using ...
user avatar
  • 1,212
0 votes
1 answer
42 views

Recursive formula does not work as intended

For my cs class Ive been given the following task. I have n different beers, and the i'th beer has a price of p[i]. the prices are: p1 = 2, p[2] = 3, p[3] = 2, p[4] = 1, p[5] = 4. I also have c coins, ...
user avatar

1
2 3 4 5
52