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

15
votes
4answers
516 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} $$ ...
15
votes
1answer
312 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 ...
10
votes
5answers
581 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? $$ ...
9
votes
3answers
783 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) = ...
8
votes
1answer
75 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
1answer
543 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
2answers
196 views

Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion $$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{$*$}$$ which I know should be satisfied by the moments of the unit ...
6
votes
3answers
253 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
191 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?
6
votes
1answer
111 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
866 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 ...
5
votes
2answers
335 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
4k views

What is the solution to the following recurrence relation with square root?

This looks like a question asked earlier, but it isn't T(n) = T (sqrt(n)) + 1 ... if n>1 =1... if n=1 My professor gave this to me in class yesterday. This is where I'm stuck.. T(n) ...
5
votes
1answer
110 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
2answers
265 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 ...
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
77 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
104 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.
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
3answers
1k 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 ...
4
votes
2answers
83 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
3answers
81 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
143 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
1answer
65 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
2answers
80 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
119 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
451 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
827 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
1answer
57 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
74 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
114 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
165 views

Prove a function is primitive recursive

Help me please $f(x)=x+a$, where $a$ is a constant.
4
votes
1answer
437 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
160 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
1answer
207 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
128 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
2answers
227 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.
3
votes
2answers
37 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
57 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
7answers
1k 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
347 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 ...
3
votes
3answers
92 views

Explanation of the recursion for number of surjections

I have a question about the recursion of the number of surjections from $\{1,\ldots,n\}$ to $\{1,\ldots,k\}$: $$\mathrm{Sur}(n,k) = k \cdot \mathrm{Sur}(n-1,k-1) + k \cdot \mathrm{Sur}(n-1,k).$$ My ...
3
votes
2answers
365 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 ...
3
votes
3answers
72 views

Prove convergence and find the value of the limit of the sequence

Sequence $$a_{n+1}=(1+\frac{1}{3^n})a_n$$ $$a_1=1$$ The question asks to prove its convergence and find its limit. I have tried all the usual ways but am unable to solve it. The question also says ...
3
votes
2answers
96 views

How to solve recursion?

I have tried to solve some recursion: $$f_n = \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n} f_{n-2} + 1, \quad f_0 = 0, f_1 = 1$$ I would like to use a generating function: $$F(x) = ...
3
votes
2answers
101 views

Argument over an induction proof

My friend gave me a problem. Define a sequence $<a_n>$ by the recurrence relation :$$ a_{n+2} - 6a_{n+1} + 8a_n = 0 $$ and $a_1 = 4, a_2 = 8 $. Find the general term $a_n$ in closed form. ...
3
votes
1answer
64 views

Recursively Defined Entities

So I am having some trouble understanding how one is to come up with the recursive definition to the following problem... We are given a rectangle of width $2$ and length $n$. Suppose we have ...
3
votes
2answers
85 views

Finding the convergent value of a recursion similar to Arithmetic-Geometric Mean recursion

The sequence is defined as follows : Start : $(x_0,y_0)$ with $ 0 < x_0 < y_0 $ Step : $x_{n+1} = \frac {x_n+y_n} {2}$ , $y_{n+1}= \sqrt{x_{n+1}y_n} $ Find $\lim_{n\to \infty}(x_n,y_n)$ . ...
3
votes
1answer
164 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
3
votes
1answer
5k views

Is 0^infinity indeterminate?

Is a constant raised to the power of infinity indeterminate? I am just curious. Say, for instance, is 0 raised to infinity indeterminate? Or is it only 1 raised to the infinity that is?