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 the functions for some inputs in ...

learn more… | top users | synonyms

377
votes
6answers
26k views

Why is $1 - \frac{1}{1 - \frac{1}{1 - \ldots}}$ not real?

So we all know that the continued fraction containing all $1$s... $$ x = 1 + \frac{1}{1 + \frac{1}{1 + \ldots}} $$ yields the golden ratio $x = \phi$, which can easily be proven by rewriting it as ...
20
votes
1answer
478 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
16
votes
4answers
566 views

Find all bijections $\,\,f:[0,1]\rightarrow[0,1],\,$ which satisfy $\,\,f\big(2x-f(x)\big)=x$.

A friend of mine gave me the following problem: Find all functions $f:[0,1]\to[0,1]$, which are one-to-one and onto and satisfy the following functional relation: $$ f\big(2x-f(x)\big)=x, \tag{1} $$ ...
14
votes
1answer
318 views

Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
13
votes
3answers
991 views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = ...
12
votes
3answers
1k views

Is there a slowest divergent function?

So I've been playing around with some functions for a while, and started wondering about a slowest divergent function(as in $\lim_{x\to\infty} f(x)\to\infty$) and so I searched around for an answer. ...
12
votes
5answers
731 views

Evaluating tetration to infinite heights (e.g., $2^{2^{2^{2^{.^{.^.}}}}}$)

The Problem How can you evaluate (i.e., get a value for) Tetration (i.e., iterated exponentiation) to infinite heights? For example, what would be the value of this expression? $$ ...
12
votes
1answer
126 views

Is there a name for the recursive incenter of the contact triangle?

Recently, I became aware that there are many more triangle centers than the four I learned about in school. This reminded me of a thought I had when I first learned about the incenter: what point ...
10
votes
2answers
642 views

The set that only contains itself

Ignoring the axiom of regularity (and therefore the implication of "no set can contain itself"), would it be correct to state that the set that contains only itself is unique? My argument is that if ...
10
votes
1answer
278 views

Limit of recursive sequence $n^2q_n=1+(n-1)^2q_{n-1}+2(n-2)q_{n-2}$

When looking at this riddle, I came across the following sequence for the frequency of sampled integers between 1 and $n$ in a without replacement/without neighbour sampling: $$q_1=1,\quad ...
10
votes
4answers
7k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
10
votes
2answers
248 views

How to prove this recursive sequence converges to $\sqrt 2$?

Let $a_0,a_1>0$ be given. Consider the recursive sequence $$a_{n+2}=\frac{1}{a_{n+1}}+\frac{1}{a_n}$$ Prove that $a_n\to\sqrt2$. I attempted to find a bound for $a_n$ but so far I have only got ...
10
votes
1answer
195 views

Solving a recursion efficiently

I have a recursive formula $$v(n+1) = v(n)\dfrac{1+v(n-1)-n}{1+v(n-1)-v(n)}$$ and I also know $$v(1)=2v(0)$$ $$n+1 \le v(n+1) \le v(n)+1.$$ I wish to find, for example, $v(10)$ more efficiently than ...
9
votes
5answers
158 views

Number of sequences of $0$s, $1$s, and $2$s with length $n$ such that there is a $0$ somewhere between every pair of $2$s

Let $a(n)$ be the number of sequences with length $n$ which consists the digits $0,1,2$ such that between every two occurrences of $2$ there is an occurrence of $0$ (not necessarily next to the ...
9
votes
4answers
698 views

Definition of General Associativity for binary operations

Let's say we are talking about addition defined in the real numbers. Then, by induction we define $\sum_{i=0}^{0}a_i=a_0$ and $\sum_{i=0}^{n}a_i=\sum_{i=0}^{n-1}a_i+a_n$ for $n> 1.\:$ Now, how do ...
9
votes
1answer
113 views

Prove that $a_n$ is a perfect square if $n$ is even without generating functions or Taylor series.

Let $a_n$ be the number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $n$. For example, $a_5 = 6$, since there are six integers with the desired property: $41, 14, 311, ...
8
votes
3answers
2k views

How can I explain this integer partitions function recursion?

How to explain how this algorithm works? I need to write an article about this but I can't explain why this recursion works fine. It defines the number of partitions of a given integer ...
8
votes
2answers
155 views

Find Nth formula of recursive formula $a_n=a_{n-1}+n(n-1)a_{n-2}$

$$a_n=a_{n-1}+n(n-1)a_{n-2}$$ $$a_0=1, a_1=-\frac{1}{2}$$ Is it possible to find explicit formula for $a_n$ just by using $a_0$ and $a_1$? I know how to solve this problem if $a_n=Aa_{n-1}+Ba_{n-2}$ ...
8
votes
3answers
762 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: \[ g(1)=\alpha \] \[ g(2n+j)=3g(n)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \] I ...
8
votes
1answer
646 views

Bell numbers, recursions, bijections

The $n$th Bell number, named after Eric Temple Bell (although he was far from the first to think about them), is the number of partitions of a set of cardinality $n$. If they are written in the top ...
7
votes
5answers
208 views

How to get nth derivative of $e^{x^2/2}$

I want to calculate the nth derivative of $e^{x^2/2}$. It is as follow: $$ \frac{d}{dx} e^{x^2/2} = x e^{x^2/2} = P_1(x) e^{x^2/2} $$ $$ \frac{d^n}{dx^n} e^{x^2/2} = \frac{d}{dx} (P_{n-1}(x) ...
7
votes
1answer
240 views

Complicated Multivariate Recurrence Relations For Generating Polynomials

I have the following multivariate recurrence relations all from the same system: First, suppose that $0\le k\le j\le m$, and let $N$ be an independent integer. Then we have for expressions $a(k,~ m,~ ...
7
votes
1answer
195 views

Compute a probability in Random Walk by Martingales

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a ...
7
votes
1answer
86 views

Functional equation: Show $0\le f(n+1)-f(n)\le 1$ and find all $n$ such that $f(n)=1025$.

The function $f:\mathbb{N}\to \mathbb{R}$ satisfies all of $$\begin{align}f(1)&=1, \\ f(2)&=2,\\ f(n + 2) &= f(n + 2 − f(n + 1)) + f(n + 1 − f(n)) \tag{1} \end{align}$$ Show ...
7
votes
1answer
126 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
7
votes
2answers
1k views

Can every recursive formula be expressed explicitly?

I'm not sure if my wording is entirely correct, but I was just wondering if every recursive formula can be turned into an explicit formula. I am asking this because various sources online gives me ...
7
votes
0answers
178 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
6
votes
2answers
651 views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
6
votes
1answer
126 views

Killer Tree! (one of my old questions)

There is a problem that killed me! but I couldn't solve it: We have a tree graph witch its structure is what is on image. Proof that there is no reduplicative numbers in each line.
6
votes
2answers
207 views

Are hyperoperators primitive recursive?

I apologize if this question is too basic. I have read that the Ackerman function is the first example of a computable but NOT primitive recursive function. Hyperoperators seem to be closely related ...
6
votes
1answer
85 views

Game in a circle

$N$ players play a game. They stand in a way such that they form a regular $N$-gon. Players are numbered from $1$ to $N$. The players throw boomerangs in clockwise order, in turns. At first player $1$ ...
6
votes
1answer
37 views

Conditional iterations constant.

Let $f(0)=2.$ Define for positive integers $n$ : $f(n+1) = \frac{3}{2} f(n)$ if $f(n)$ is even. $f(n+1) = \frac{3}{2}(f(n)+1)$ if $f(n)$ is odd. We now have $\lim_{n->\infty} \dfrac{4* (3/2)^{n} ...
6
votes
1answer
97 views

Eigenvalues appear when the dimension of the Prime Index Matrix is a prime-th prime. Why?

I had a look at the eigenvalues of the matrix, I called it Prime Index Matrix (is there a better name?), constructed like the following: $$ P_{k,p_k}=P_{p_k,k}=1, $$ where $p_k$ is the $k$th prime. ...
6
votes
1answer
110 views

undecidability of the structure $(\omega,+,2^n)$

Is the structure $(\omega,+,2^n)$ undecidable? There is no easy way to define multiplication using a formula.
6
votes
0answers
208 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
6
votes
0answers
131 views

Asymptotic behavior a recursion involving min/max

Usually when I face solving recursions I use generating functions but I'm not aware of any "tools" to use when min/max expressions are involved. For example, I have the following recursive term: ...
6
votes
2answers
101 views

Prove function is Fibonacci sequence

Stuck on how to finish a question I'm working on. Have to find the number of bitstrings of length n with no odd length maximal runs of ones. For example, when n=3 there are three such bitsrings: 011, ...
5
votes
5answers
2k views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
5
votes
2answers
439 views

A Recurrence Relation Involving a Square Root

Consider the recurrence relation: $a_{n+1} = \sqrt{a_n^2 -k},$ where $k>0$, $n\in\{0,1,n:a_n^2\geq k\}$, and $a_0>0$ is known. Is it possible to obtain an expression for $a_n$ in terms of ...
5
votes
2answers
579 views

Why is $\log(b,n) = \lfloor \log_b(n) \rfloor$ primitive recursive?

I read in an introduction to primitive recursive function and Wikipedia that $$\log(b,n) = \lfloor \log_b(n) \rfloor$$ is primitive recursive. But how can that be? Is there any easy proof (and ...
5
votes
1answer
132 views

From Primitive Recursive to Recursive by Iterating over more than one Argument?

Is the only way a function can be recursive and not primitive recursive by growing faster than primitive recursion allows (as with Ackerman's function)? If so, then consider the following. Primitive ...
5
votes
2answers
91 views

Alternative unconditional form of $\sqrt{n -\sqrt{n -\sqrt{n -\cdots}}}$?

Consider $a_n$, where $$\begin{align} a_n &=\small{\sqrt{n -\!\!\!\sqrt{n -\!\!\!\sqrt{n -\!\!\sqrt{n -\!\!\sqrt{n -\!\!\sqrt{n -\!\sqrt{n - \cdots}}}}}}}}\end{align}$$ Using a recursive ...
5
votes
2answers
301 views

Precisely, what is a primitive recursive definition?

If I understand correctly, the language of primitive recursive arithmetic has a distinguished function symbol $S$, together with a function symbol for each primitive recursive definition (hereafter ...
5
votes
2answers
491 views

If a recursive sequence converges, must its inverse be divergent?

Suppose I have a recursive sequence $\displaystyle a_{n+1} = \frac{a_{n}}{2}$. Clearly, the sequence converges towards zero. Now, suppose I define an "inverse" sequence $\displaystyle b_{n+1} = ...
5
votes
3answers
108 views

Recursion, multiplication and exponential

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
5
votes
2answers
160 views

Chaos theory and fractal geometry: Constructing from data

I understand that fractal geometry represents behaviour of 'chaotic' system, if I am not wrong. And also, fractals are generated by a recursive function. But, lets say I have random data lying with ...
5
votes
1answer
84 views

Proving $V=V_{\sf On}$ in $\sf Z+Reg$

Define the function $$V_0=\emptyset,\qquad V_{\alpha+1}={\cal P}(V_\alpha),\qquad V_{\delta}=\bigcup_{\beta<\delta}V_\beta.$$ Since we are working in $\sf Z$ (i.e. $\sf ZF$ without the axiom of ...
5
votes
1answer
2k views

Fibonacci with Mortal Bunnies

I am trying to understand a twist on the Fibonacci bunnies scenario, where the bunnies die x generations after their birth (where x is a positive integer). An example is shown here. I understand the ...
5
votes
2answers
144 views

Probability (usage of recursion)

In an hour, a bacterium dies with probability $p$ or else splits into two. What is the probability that a single bacterium produces a population that will never become extinct?
5
votes
1answer
152 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...