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

7
votes
0answers
174 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
0answers
187 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
128 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
0answers
67 views

Conway's Game OF Life maximum periods on a set x by x game board.

I have taken interest in Conway's Game of Life and want to know if you guys can help me with a mathematical problem :) That is what this website is for right? You need to be familiar with the rules ...
4
votes
0answers
67 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
4
votes
0answers
108 views

uniform convergence in recursive function

Let $\varphi:[0,+\infty)\to \mathbb{R}$ an increasing continuous function that satisfies that $1/2\leq \varphi(x) <1$ for all $x>0$. Let $f_0:[0,+\infty)\to \mathbb{R}$ an increasing function ...
4
votes
0answers
69 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
0answers
64 views

When do Leibniz-like rules lead to unique linear operators

Background Usually one defines differentiation in terms of limits, and then shows that differentiation satisfies the Leibniz (product) rule, $$\frac{d}{dx}(f \cdot g) = f\frac{dg}{dx} + g ...
4
votes
0answers
91 views

How to get the period of oeis.org/A130166 other than by trail?

oeis.org/A130166 a(0)=1; a(n)=prime(mod(a(n-1),1000)) starts with: ...
4
votes
0answers
102 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
3
votes
0answers
57 views

What is the maximum amount of solutions to $f(x+1)f(x)= ax^2+bx+c$.

$f(x)$ is going to be in the form $mx+h$ thus, $(mx+m+h)(mx+h) = ax^2+bx+c$. With basic algebra $m= \pm \sqrt{a}$. Also $(m+h)(h)=c$. I would guess that because $(m+h)h=c$ has two solutions max if $m$ ...
3
votes
0answers
74 views

Recursion asymptotic growth function proof of complexity

I have the following recursive function(an example from a textbook): $$ T(n)=\begin{cases}1&n=1\\T(\lfloor\tfrac n2\rfloor)+T(\lceil\tfrac n2\rceil)+1&n>1\end{cases} $$ A recursion is ...
3
votes
0answers
136 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
2
votes
0answers
13 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
2
votes
0answers
60 views

Closed form of $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $

Given the sequence $a_1 = 1$ and $a_2 = 1 $ with: $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $ Does there exist a closed form computing $a_n$ ? At the moment I have a problem getting a grip on the ...
2
votes
0answers
43 views

Asymptotics of recursion

suppose we have the following two sequences $$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$ $$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$ where ...
2
votes
0answers
48 views

Almost sure convergence of a martingale

I just learned martingales (with no depth) and I am working on the following question. Suppose $S_n$ is a a random walk on the integers and at each step, it increases by 1 with probability $p$ or ...
2
votes
0answers
8 views

Naive Euclidean algorithm - average complexity?

Suppose I compute the GCD in a rather simple-minded recursive way: $$ \gcd(a, b) = \begin{cases} \gcd(a, b-a) & \text{ if }{a < b}, \\ \gcd(a-b, b) & \text{ if }{a > b}, \\ a & ...
2
votes
0answers
36 views

What is the solution to this recursion?

Take $a_0=10^6$. What is $a_n$ (asymptotically) where $a_{i+1}=a_i+\sqrt[\alpha]{a_i}$ where $\alpha>1$? How fast does $a_n$ grow?
2
votes
0answers
84 views

Solving recursions by calculating determinant of an infinite matrix

In this reference (pg. 4) and few others a specific parameter in a recursion formula is solved by setting the determinant of an infinite matrix to $0$. In this precise case we have $c_{n-1} - D_n c_n ...
2
votes
0answers
46 views

Meaning of Biinterpretability.

I'm reading this paper: http://www.math.cornell.edu/~shore/papers/pdf/hyp9.pdf and I am struggling with the meaning of Biintereptability, to quote the paper A degree structure $D$ is ...
2
votes
0answers
45 views

A Problem about Recursion

Consider recursion $$a_n+c_1a_{n-1}+\cdots+c_ma_{n-m}=0~~~~~~~~~~(1)$$ Let $\lambda^m+c_1\lambda^{m-1}+\cdots+c_m=0$ be the characteristic function and $(\lambda_1,n_1),\cdots,(\lambda_s,n_s)$ be ...
2
votes
0answers
76 views

Find the sum of exponentails of squares $\sum_{r=1}^n e^{-\alpha r^2}$

I would like to find $$a_n =\sum_{r=1}^n e^{-\alpha r^2},\qquad \alpha\in\mathbb{R}$$ I tried to solve the equivalent recursion $$a_n=a_{n-1}+e^{-\alpha n^2}\quad(n>0),\qquad a_0=0.$$ with an ...
2
votes
0answers
127 views

Maximizing a continuous recursive function

So I've been working at this for a while and have so far been unable to find any resources on maximizing a particularly strange function that I've been trying to deal with. The function is of the form ...
2
votes
0answers
99 views

Acceptable numbering of partial computable functions required to be one variable?

Soare in a yet unpublished textbook (I happened to be in a class taught by one of his former graduate students where we were field-testing a rough draft of his new textbook) Computability Theory and ...
2
votes
0answers
94 views

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete This is a question from Soare's Recursively Enumerable Sets and Degrees. I have little idea how ...
2
votes
0answers
103 views

Indeterminacy in second degree equations of Spencer-Brown's “Laws of Form”

I am trying to follow G. Spencer-Brown's argumentation regarding 'Equations of the Second Degree' in the Laws of Form. He shows how infinitely growing self-referential forms can be created by using a ...
1
vote
0answers
17 views

Solving a polynomial for cyclic roots

For any complex value of c, the following polynomial has 6 complex root values of p: $$1+c+2 c^2+c^3+p+2 c p+c^2 p+p^2+3 c p^2+3 c^2 p^2+p^3+2 c p^3+p^4+3 c p^4+p^5+p^6$$ For a general 6th order ...
1
vote
0answers
28 views

How to solve even/odd divide-and-conquer problems?

I am looking into something called the Josephus problem, which seems to be popular, so I am sure there are lots of explanations online, but I want to do the work myself, but I do need a small push to ...
1
vote
0answers
15 views

nodes equation cant find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level N where $X$ is located to narrow our ...
1
vote
0answers
22 views

How to show that F is recursive?

In the road to Godel's incompleteness theorem, Problem saying: Show that Frame For $G:\omega\times\omega\times\omega^{n}\rightarrow\omega$ a recursive function, the function ...
1
vote
0answers
25 views

recursion trees and big theta bounds

Draw recursion trees and use them to find big theta bounds on the solutions to the following recurrences. For each, assume that T(1) = 1 and that n is a power of the appropriate integer. ex) T(n) = ...
1
vote
0answers
43 views

Proving that for $F_k = F_{k-1} + F_{k-2}$, $F_k$ is even iff $3|k$

Consider the recursion $F_k = F_{k-1} + F_{k-2},$ $ k\geq 2,$ $F_0 = 0$ and $F_1 = 1$, then show that $F_k$ is even iff $3|k$ I tried to do a proof by induction: The statement is true for base ...
1
vote
0answers
18 views

Solving systems of reccurence equations to get number of recursions to reach a stationarity point?

I'm tring to solve a system of recurrence equations to then formalize a formula depending on the number of recursions to calculate this number of recursions to reach the stationarity of the system ...
1
vote
0answers
58 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
1
vote
0answers
21 views

Recurrence relation for the colored balls problem

Right now I am attempting to solve the recurrence thats solves a famous problem (the colored balls problem: http://mathoverflow.net/questions/41939/a-balls-and-colours-problem) given by $2i(n-i)Z_i = ...
1
vote
0answers
32 views

Is a linear random walk with jump recurrent?

Let $\lambda_0=10^5$ or any other large integer. Define the recursive "process": $\lambda_t=\text{sample from a Poisson distribution with mean }\lambda_{t-1}$. Is this process recurrent? I mean, after ...
1
vote
0answers
39 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
1
vote
0answers
39 views

Runtime of recursive algorithm - Master's Theorem

I wrote a computer program that solves a question, and I am interested in knowing what is the runtime. My aim is for $O(\log n)$, and I'd like someone more experienced (and smarter?) to review my ...
1
vote
0answers
23 views

function with a recurrence relation

I have this recursive equation: $$\begin{align*} F(m,n)&=F(m,n-1)+F(m-1,n)-F(m-1,n-1-m)\\\\ F(m,0)&=F\left(m,\frac12m(m+1)\right)=1\\ F(m,i)&=0\text{ if }i<0\text{ or ...
1
vote
0answers
22 views

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: \begin{align*} f_{\alpha,\gamma} \left( \begin{array}{c} t\\ v ...
1
vote
0answers
32 views

Recursive definition of sequences inverse/equivalency.

So here's the problem: "Give a recursive definition of the sequence ($a_n$), $n = 1, 2, 3, ...$ if $a_n = 4n - 2$." Here's my answer:$$t_1 = 2; t_n = t_{n-1} + 4$$ However, I know this could also ...
1
vote
0answers
364 views

Proving a recursive algorithm as correct using induction

My objective is to give a recursive algorithm for finding the maximum of a finite set of integers, "making use of the fact that the maximum of n integers is the larger of the last integer in the list ...
1
vote
0answers
192 views

Probability of rolling n dice to match another set of dice, d, given r rolls (like yahtzee)

(Note: I will eventually code this, but i'm primarily interested in the math behind it) I'm trying to create a function in Java to calculate the probability of getting a desired outcome from n rolled ...
1
vote
0answers
44 views

Need clarification on recursive functions.

Given any function $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ and a recursive $h:\mathbb{N}_0 \rightarrow \mathbb{N}_0$ , I know that to prove $h\circ f$ is recursive I only need to prove that $f$ is ...
1
vote
0answers
33 views

Approximate Solution to Backwards Recurrence of Dynamic Game

Suppose we keep tossing a fair dice until we reach some cumulative sum greater than or equal to $N$. Then, let $S_k$ be the expected value of the final sum, given that the current sum is $k$. We have ...
1
vote
0answers
33 views

Recursive relation-Theta notation

Consider the recursive relation: $$T(n)=T(an)+T((1-a)n)+cn$$ where $0<a<1$ and $c>0$ are constants(independent of $n$).Show that $T(n)=\Theta(n \lg n)$ That's what I have tried: We ...
1
vote
0answers
96 views

Is the proof of non-totality of a function $f$ trivial if $f$ is recursively defined only on a subset of $\Bbb N$?

I define a fuction $*$ in a recursive way on a subset of natural numbers (with subset I mean that is $*$ define in the second argument only for $\Bbb N-\{0,1\}$ in other words we have $*:\Bbb N ...
1
vote
0answers
25 views

Show $f(x)$ is partial recursive using the

So I want to show that the function $f(x)=0 $ if $x$ is even and not defined otherwise, is partial recursive using the $\mu$ operator (bounded search function, which is partial recursive). Plan is to ...
1
vote
0answers
70 views

Is undecidability of arithmetic a corollary of Tarski undefinability theorem?

Arithmetic is undecidable, in other words the set of Godel numbers of theorems of arithmetic is not recursive, and so there is no algorithm/ recursive function to decide if a statement is provable or ...