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

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 ...
3
votes
0answers
74 views
+50

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: ...
3
votes
0answers
46 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 ...
3
votes
0answers
47 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 ...
3
votes
0answers
39 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 ...
3
votes
0answers
80 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: ...
3
votes
0answers
82 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 ...
2
votes
0answers
24 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 ...
2
votes
0answers
93 views

$n^{\text{th}}$ digit of $\sqrt{2}$ decimal representation is primitive recursive function

An exercise from Maltsev's "Algorithms and recursive functions". Problem: Let $\sqrt{2} = a_0,a_1a_2\dots a_n\dots$ be the decimal representation of $\sqrt{2}$. Show that the function $f(n) = a_n$ ...
2
votes
0answers
41 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
113 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
67 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
109 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
76 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
83 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
89 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
18 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
20 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
21 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
105 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
68 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
36 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
29 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
19 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
40 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 ...
1
vote
0answers
70 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
24 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
61 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 ...
1
vote
0answers
93 views

Defining things in a non-recursive manner

In this question I asked, if it was possible to define certain functions without the use of the recursion theorem. The answer, among other things, indicated that it theoretically would be possible, ...
1
vote
0answers
154 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
0
votes
0answers
25 views

Finding an explicit formula for An in terms of n.

Let $A_{1}= 5, A_{2} = 7,$ $A_{n+1} = A_{n} + 6A_{n-1}$. Find an explicit formula for $A_n$ in terms of $n$. Suppose $p_{n}$ is a sequence defined by $p_{1} = 0, p_{2} = 1$ & $\forall n$, ...
0
votes
0answers
11 views

How does one know T(a) is the base case in T(n) = T(n-a) + T(a) + cn

T(n) = T(n-a) + T(a) + cn Solve by drawing recursion tree. Typically when solving other recursion tree problems, I've calculated the height of the tree in terms of when the subproblems reach T(1). ...
0
votes
0answers
28 views

Is every natural recursive relation necessarily holomorphic?

Define the set of algebraic primitive recursive relations as the set of functions defined by: $$ F(n,a,k) = F(n-1,F(n-1,F(n-1,a,a),a)...,a)_{\text{nested to depth k}}$$ $$ F(0,a,k) = a + k $$ Along ...
0
votes
0answers
18 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 ...
0
votes
0answers
16 views

Show T(n)=T(n/5)+T(4n/5)+n/2 is $\Omega (n log n)$

I'm tasked with showing T(n)=T(n/5)+T(4n/5)+n/2 is Big-Omega n log n by drawing a recursion tree. The tree shows a lower bound with the following terms: n/2 ... n/10 ... n/50 ... etc. When I solve ...
0
votes
0answers
117 views

Some feedback on the sequence $ a_n=a_{n-1}+4\phi_n $

This sequence is present at OEIS A171503. There, Jacob Siehler explains how this sequence correspond to the number of matrices with determinant one and how this number grows as we allow to vary in ...
0
votes
0answers
19 views

Is this recursive?

I came across this formula in a neuroscience journal: $x = [sigma(y - z)] - w$ where: $z = a + \max(x)$ My question is, can you solve for $x$ if $x$ is a constituent of $z$?
0
votes
0answers
11 views

Closed form of chained Stationary Functions

Consider the following operator $$D_{(a-1)x,x}\left[ f \right] = \frac{f(ax) - f(x)}{(a-1)x} $$ It's pretty easy to see that a nontrival function $g(x)$ such that $$D_{(a-1)x,x}[g] = g$$ Is given ...
0
votes
0answers
32 views

Derive the recursion relation

Consider the nonhomogeneous linear equation $y' = 2y/(1-x) + f(x)$. It is singular at $x=1$, of course, but it is regular at $x=0$ if (the known function) $f(x)$ is analytic there. Assume $y(x) = ...
0
votes
0answers
19 views

Eliminating left recursion of a grammar

I would like to create a grammar in which each binary operation is represented by one parent node with 3 children (operand1 op operand2). However I´m creating the productions such as the other of ...
0
votes
0answers
32 views

Help Solve Recurrence Relation$ T(n) = T(n-1) + O(n)$

This is how far I have gotten: $$T(n) = T(n-1) + O(1)$$ $$T(n-2) = T(T(n-2)) + O(1)) + O(1)$$ $$T(n-2) = T(n-2) + O(2)$$ $$T(n-3) = T(T(n-3) + O(1)) + O(2)$$ $$T(n-3) = T(n-3) + O(3)$$ Finally ...
0
votes
0answers
69 views

In terms of addition, multiplication, exponentiation, tetration, what would be the natural continuation here?

Consider the by addition recursively defined table: $$t(n,1)=1$$ If $n>=k$ $$t(n,k)=\sum _{i=1}^{k-1} t(n-i,k-1)-\sum _{i=1}^{k-1} t(n-i,k)$$ else $$t(n,k)=0$$ Then consider the similar but by ...
0
votes
0answers
53 views

$T(n) = T(n/3) + T(2n/3) + cn$ - recursion tree with constance $c$

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac ...
0
votes
0answers
34 views

Is there a closed form polynomial for this integral recursion?

While working on some statistical problems, I startet playing with integral recursions of the type $$p_{n+1}(x)=\int_a ^x \mathrm{d} y\; q(y)p_n(xy)$$ Here $q(y)$ and $p_0(x)$ are given polynomials, ...
0
votes
0answers
13 views

largest number of regions formed by a certain amount of planes recursion question

The question: What is the largest number of regions formed by $6$ planes in space? I answered a similar question to this and it said "What is the largest number of regions formed by $6$ LINES in ...
0
votes
0answers
12 views

QBF - space complexity in detail

As I'm new to the "complexity theory" stuff I've some trouble with proofs which are "obvious" regarding all books I've found so far. In this case I want some evidence why a certain algorithm has space ...
0
votes
0answers
10 views

Dinamic programming for sum of two largest values from a Uniform parent

I must find a recursion formula to find the sum of two largest values from a Uniform parent [0,1]. I need dinamic programming but I don't know how to organize it.
0
votes
0answers
30 views

Financial mathematics: asion option

I've got a forward starting asian call option: $V_N = max\left( 0,\left(\sum_{j=m+1}^{N}{S_j} - K \right) \right) $ So the payoff is determined by the average stockprice over de latest N-m days and ...
0
votes
0answers
20 views

Developing closed-form from recursive definition

Here is a recursively-defined function where c, d ∈ N. T(n) =    c, if n = 0 d, if n = 1 2T(n − 1) − T(n − 2) + 1, if n > 1 Carry out the five steps for repeated substitution to prove a ...
0
votes
0answers
33 views

Prove using Induction : Recursion

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...