Mathematics Stack Exchange
Mathematics Stack Exchange

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

Recursion is the process of repeating items in a self-similar way. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition.

Basically, a class of objects exhibiting recursive behaviour can be characterised by two features:

  • There must be a base criterion for which the function should not call itself.

  • Every other iteration of the function should move it closer to the base condition.

2829 questions
1
vote
1 answer

Logistic Map closed form for $x_{n+1}=rx_n(1-x_n), n\in\mathbb N_0$?

$x_{n+1}=rx_n(1-x_n), n\in\mathbb N_0.$ I am only interested in $r=4.$ On Wikipedia I found the following statement: Every solution $(x_n)^\infty_{n=0}\subset [0,1]$ of the recursion can be written as $x_n=\sin^2(2\pi y_n)$, with…
Montaigne
  • 855
1
vote
1 answer

Statement & proof of theorem to justify "complete recursion"?

Sometimes a sequence $(s_n)_{n \in \mathbf{N}}$, where $\mathbf{N}$ is the set of natural numbers, is defined as follows: (a) let $s_0 = ...$; (b) for $n \geq0$ assume that $s_0, s_1, s_2, \dots, s_n$ have already been defined; then define $s_{n+1}$…
murray
  • 778
  • 3
  • 16
1
vote
1 answer

Example of a recursively enumerable set as a limit of recursive sets

I am reading Soare's book and I am trying to understand the following statement: A function f has r.e. degree iff it is the limit of a recursive sequence ${f_{s}}_{s \in \mathbb{N}}$ and its modulus of convergence $m \leq_{T}f$. However, I am…
user350168
  • 393
1
vote
0 answers

Recursion Relations

Why is it required that a recursion be bounded? For example given $U_n = aU_{n-1} + c$ where $a$ and $c$ are constants. Why is it necessary that you specify that $n>1$ in your response.
lehasa seoe
  • 11
1
vote
1 answer

Recursion - series examples

Given: $$p(n+1) = 2^n \cdot \sqrt{2\cdot {\left( 1 - \sqrt{1 - \left(\frac{p(n)}{2^n}\right)^2}\right)}}$$ And: $$p(2) = 2\cdot \sqrt{2}$$ Find $p(n)$. I an unable to come up with a generalization for $p(n)$. Please help.
user411196
  • 11
  • 2
1
vote
1 answer

Recursively calculating a function

Let $f\colon \mathbb N\times \mathbb Z \to \mathbb Z$ defined by $f(x,0)=x$ for all $x\in \mathbb N$ $f(0,y)=2y$ for all $ y \in \mathbb Z$ $x\gt0$ and $y\lt0$$\implies f(x,y)=2y$ $x\gt0$ and $y\gt0$$\implies f(x,y)=f(x-1, f(x,y-1))$. Compute…
Alex
  • 649
1
vote
1 answer

recursion and inductive proof

Just so no one thinks I am trying to get one over on anyone, this is a homework question. I have solved all the other problems, but I don't know where to begin with this one. I am not asking for an answer, just a direction or hint (that I can…
thePetester
  • 21
1
vote
5 answers

nonhomogeneous recurrence relation with $f(n)=4*n-3$

I am trying to solve this recurrence relation: $a_n=a_{n-1}+4n-3$ I was trying to solve it using characteristic equation. First I found homogeneous solution: $a_n-a_{n-1}=0$ $x=1$ $a_n=A*1^n$ And then I tried to find particular solution, but I got…
TijuanaTaxi
  • 331
1
vote
1 answer

Validate Dobinski's formula using recursive Bell number formula

As we know, Bell number can be given using two formula $B_N=\sum_{k=0}^{N-1}C_{N-1}^{k}B_k$ (recursive) $B_N=e^{-1}\sum_{k=0}^{\infty}\frac{k^N}{k!}$ (Dobinski's formula) Now I want to substitute Dobinski's formula into recursive one to validate…
Vimos
  • 121
1
vote
2 answers

Prove that no function exists from $\mathbb{N}$ to $\mathbb{N}$ such that $f(n) \gt f(n+1)$

The recursion theorem says that if we have a function called $G$ from $A \times \mathbb{N} \to A$ there exists a function called $f$ from $\mathbb{N} \to A$ such that $f(0)$ equals to one of the members of $A$ and $f(n+1)=g(f(n),n)...$ so how can we…
NO-ONE_LEAVES_HERE
  • 19
1
vote
2 answers

Generalization of recursive formula

Ok, here is the problem, I have formula: $a_n=a_{n-1}+2^{n-4}-a_{n-4}$ with initial variables $a_0=0$, $a_1=0$,$a_2=0$ and $a_3=1$ If not for $2^{n-4}$ member in recursion, I probably would manage to get general form, but $2^{n-4}$ makes things way…
Timo Junolainen
  • 639
1
vote
3 answers

How do I solve following recursion

I have been trying to solve this $f(n) = 2 \cdot f(n-1) - f(n-2) + 2 \cdot k$ and failed , can anybody help ? $n>4$ The values of $ f(1) = a,\,f(2) = b,\, f(3) = c$ and $f(4) =d $ where $ a,b,c,d,k $ are constants EDIT: This is an example $ a=1/6…
User170496
  • 41
1
vote
1 answer

Recurrence relations

For each integer $n ≥ 1$, let $t_n$ be the number of strings of $n$ letters that can be produced by concatenating (running together) copies of the strings $“a”$, $“bc”$ and $“cb”$. For example, $t_1$ = $1$ (“a” is the only possible string) and $t_2$…
dave
  • 103
1
vote
0 answers

Stability with 2 dimensional recursion functions.

First of all, hello. I'm having trouble determining whether fixed points are stable or unstable. I have a recursion function:…
BlockCat
  • 11
1
vote
3 answers

Given that $f(n)=3f(n-1)-2f(n-2)$ for $n>1$ and given that $f(0)=0$, $f(1)=1$, what is $f(10)$?

I understand how to work out this question using brute force (manually substituting the numbers in) was just wondering if there was a faster and less tedious way of doing this question.
Hyune
  • 101
1 2 3
…
12 13