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

18
votes
1answer
444 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 ...
15
votes
4answers
545 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} $$ ...
11
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. ...
10
votes
5answers
656 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? $$ ...
10
votes
3answers
857 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) = ...
10
votes
1answer
248 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?
10
votes
1answer
110 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 ...
8
votes
5answers
149 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 ...
8
votes
1answer
92 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, ...
7
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 ...
7
votes
3answers
441 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 ...
7
votes
1answer
594 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 ...
6
votes
3answers
348 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 ...
6
votes
1answer
150 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 ...
6
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 ...
6
votes
0answers
121 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: ...
5
votes
2answers
385 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
4answers
5k 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 ...
5
votes
1answer
118 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.
5
votes
1answer
172 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,~ ...
5
votes
1answer
33 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} ...
5
votes
1answer
86 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. ...
5
votes
1answer
108 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.
5
votes
0answers
128 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, ...
5
votes
2answers
92 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
0answers
166 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 ...
4
votes
5answers
1k 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 ...
4
votes
2answers
422 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.
4
votes
2answers
84 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 ...
4
votes
2answers
312 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} = ...
4
votes
3answers
92 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} ...
4
votes
1answer
171 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 ...
4
votes
2answers
76 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 ...
4
votes
1answer
70 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 ...
4
votes
1answer
1k 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 ...
4
votes
2answers
94 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?
4
votes
1answer
135 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} ...
4
votes
1answer
524 views

Non-linear Recursion

I'm trying to prove (or disprove and improve if possible) that the sequence $a_{n+1}=\frac{a_n^2+1}{2}$, where $a_0$ is an odd number greater than 1 contains an infinite number of primes. However, I ...
4
votes
1answer
67 views

Prove $g$ is PR. $g(n) = f(n) \text{ if n} \notin A$. $f$ is PR. $g$ is total. $A$ is a finite set.

Show that if f:N $\rightarrow$ N is primitive recursive, A $\subseteq$ N is a finite set, and g is a total function agreeing with f at every point not in A, then g is primitive recursive. My ...
4
votes
1answer
77 views

Number of times $g(p_1)$ occurs in $\sum_{d\mid n}g(d)$

$$ g(n)=\begin{cases} 1 & \text{if }n=1 \\[10pt] \sum_{d\mid n,\ d\ne n} g(d) & \text{else} \end{cases} $$ How can I calculate $g(n)$ efficiently? I was trying to collect all the $g(p)$ ...
4
votes
3answers
182 views

How to solve infinitely nested logarithms

I have an iterative process that starts with $$x_1 = \log_{10}(a)$$ Following iterations are as follows: $$x_2 = \log_{10}(a-b\cdot x_1)$$ $$x_3 = \log_{10}(a-b\cdot x_2)$$ $$x_4 = ...
4
votes
1answer
595 views

Primitive recursive functions and characteristic functions. Methods of proof- examples. Illumination.

I am puzzling over a sentence in an example in a textbook, showing that a function $f$, defined by cases, is primitive recursive. Let $E$ be the set of even natural numbers. The function $f$ defined ...
4
votes
1answer
549 views

Recursively Solving a Bellman Equation

Problem Overview I am to figure out $v_\pi$ of a certain Markov state. Given Information A set of actions, $a$ containing ${up, down, left, right}$ $v_\pi(12), v_\pi(13), v_\pi(14)$ (I am given ...
4
votes
0answers
56 views

Can the principle of inclusion/exclusion be used to count elements in the intersection of a sequence of sets?

The principle of inclusion-exclusion (PIE) is often used to count the number of elements in a union of $n$ sets in terms of an alternating sum of their various intersections: $$ \left |\bigcup_{i \in ...
4
votes
1answer
241 views

Is there any way to solve recurrence equations with variable coefficients?

So far I have done some problems that are best solved using generating functions. These mostly contain variable coefficients. A simple one is $H(n) = (n+2)H(n-2)$. I have found solutions to these ...
3
votes
3answers
182 views

Fixed point combinator and functions with no fixed point

In lambda calculus the fixed point combinator is defined as: It is very easy to see how $Yg =g(Yg)$ for any $g$ by using $\beta$-reduction. At the same time I wonder what is the meaning of ...
3
votes
7answers
2k views

Find the nth term of a recursive sequence

I have a the following sequence: $$\begin{gather} a_1 = 3 \\ a_{n + 1} = 1 + \frac{a_n}{2} \end{gather} $$ How can I find the $a_n$ term?
3
votes
2answers
44 views

Number of $1$s in the binary representation of $n$

Trying to define the function $b(n)$ which counts the number of $1$s in the binary representation of $n$ arithmetically I came up with the following definition: $$b(n)=m :\equiv (\exists k_1\dots ...
3
votes
3answers
58 views

How to get from $1 + (-1)^{n+1}$ to $1 + [((−1)^{n }) − 1] (−1)$

I need some help with the algebra here. I have the following explanation, and I really can't follow the algebra. Could you also maybe give me some tips on how to think about such problems. $a_n = 1 ...
3
votes
2answers
391 views

Solving a mathematical recursion to find explicit function

I came across the recursive sequence $$ \begin{align} a_{n+1}&=(r-2)a_n+(r-1)b_n\;,\\ b_{n+1}&=a_n\;, \end{align} $$ and the explicit formula $$ a_n=(-1)^n(r-1)+(r-1)^n\;. $$ I saw that ...