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

4
votes
0answers
158 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
29 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
71 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
94 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
60 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
73 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: ...
2
votes
0answers
69 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
79 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
78 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
40 views

Finding the convergent value

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)$ . ...
1
vote
0answers
24 views

Ways of defining a recursive function that counts right-parenthesis in a string

I'm trying to find a more elegant way of defining a recursive function on $\{(,)\}$ that counts right-parenthesis in a string. Let r be a function on $\{(,)\}$ defined recursively so that: ...
1
vote
0answers
14 views

Complexities of Recurrences in the form $t(n) = t(\alpha n) + t(\beta n) + cn$

When considering recurrence relations, they are generally of a form similar to $$t(n) = t(\alpha n) + t(\beta n) + cn$$ and there are three cases to be considered for our values of $\alpha$ and ...
1
vote
0answers
11 views

Recursion and Time Complexity Concept

I have been solving this question which appeared in one of the entrance exam. The question is as follows: ...
1
vote
0answers
22 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
47 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$ ...
1
vote
0answers
14 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
37 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
61 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
23 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
34 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 ...
1
vote
0answers
24 views

recursive definition produces different sequence than non-recursive

I had a homework problem where I had to give a recursive definition for the sequence $$a_n = n(n+1)$$ Which produces {2, 6, 12...}, so I first came up with this (I'll call it answer 1): $$a_{n+1} ...
1
vote
0answers
49 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
100 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 ...
1
vote
0answers
59 views

Reasoning about a recursive function

First of all, I am a computer science student, not a maths student. So maybe this is a trivial question, I just would like to understand it :) Suppose I have the following (pointless) recursive ...
1
vote
0answers
81 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
151 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
40 views

Discrete maths - Recursion, formula and induction question

A sequence $S_{0},S_{1},\ldots$ is defined recursively as follows: $$ S_{0} = 3\,,\quad S_{k} = S_{k - 1} + 2k\quad\mbox{for}\quad k \geq 1 $$ Calculate a few terms of the sequence and conjecture a ...
0
votes
0answers
23 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
13 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
28 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 ...
0
votes
0answers
45 views

How to model equation system involving recursion?

It is trivial to solve for the "chocolate wrapper" problem using a computer, and a loop: Little Bob loves chocolates, and goes to a store with \$N in his pocket. The price of each chocolate is ...
0
votes
0answers
13 views

Recursion, Induction, and Vinogradov Notation

I have a recursion relation $$ S(x, p_{n+1}, k) = S(x, p_n, k) - c(p_n) S\bigg(\frac{x}{p_n}, p_n, k p_n\bigg) + S\bigg(\frac{x}{p_n^2}, p_n, k p_n^2\bigg) \quad $$ where $c(l)$ are constants such ...
0
votes
0answers
48 views

Arithmetic Turing machines

Consider the family $T_{1}$ of Turing machines with two tape symbols $b,1$ ($b$ the blank symbol). The family $T_{1}$ is Turing complete. Identify the tape with $\mathbb{Z}$ and let $0\in \mathbb{Z}$ ...
0
votes
0answers
14 views

What is an extragradient method?

I've searched Google, but it seems that only research journal papers appear in search results, where some new, improved, or specialized extragradient method is discussed. I've also searched Wikipedia ...
0
votes
0answers
28 views

Writing convergence acceleration algorithm as a recursion type formula

Cohen et al. describes an algorithm for speeding up the convergence of an alternating series as follows: Initialize: $$d=\left(3+ \sqrt{8}\right)^n; \quad d=\frac{1}{2} \left(d+ \frac{1}{d}\right)$$ ...
0
votes
0answers
141 views

range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
0
votes
0answers
65 views

Recursion Theorem question

I am trying to prove the following in Enderton's text 'Elements of Set Theory' (exercise 8 of chapter 4): Let $f$ be a one-to-one function from $A$ into $A$, and assume that $c \in A - ran \ f$. ...
0
votes
0answers
34 views

How to solve this recursive integral?

$$f(p)= \int_a^\infty\frac{\exp(\iota k\dot p)}{k^2 + f(k)} dk$$ I thought of solving it like if I guess $f(k)$ equals a number then after solving the integral it should be itself.
0
votes
0answers
9 views

A question concerning the domain of function that is recursively defined.

I have a problem concerning nested functions and whether they're well-defined. I have the following definition for all $t\in \mathbb{Z}$. A function $y_t:\mathbb{R}^3\rightarrow\mathbb{R}$ such that ...
0
votes
0answers
36 views

Amount of sub-matrices created by Laplace expansion

I have created a program that solves a matrices determinant using the Laplace expansion method, and I was wondering if there is a equation which provides how many sub-matrices are created and used in ...
0
votes
0answers
69 views

Kleene's recursion theorem

Would anybody be able to provide me (someone with little familiarity with the subject matter) with a bit of background to the Recursion Theorem and guide me towards some texts on its mathematical and ...
0
votes
0answers
30 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
0
votes
0answers
22 views

Expressing three recursive forms into one using parameters?

I have the following recursive function that takes three forms and I want to express it in one form: Initial: $f(x) = m * f(x-1)$, $f(0) = value.$ Forms: 1 - $f(t) = m * f(t-1)$. where t is at ...
0
votes
0answers
54 views

Can the method of generating functions be applied to linear recursions of order $>4$?

I just got in touch with the method of solving recursions with generating functions. However, even if it is not mentioned anywhere, it seems to me, this approach is not applicable for recursions of ...
0
votes
0answers
48 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
0
votes
0answers
31 views

Closed form for a special recursion?

Does the recurrence relation $$ a(n+1) = a(n)^2 + 1,\quad a(1)=1, $$ have a closed form solution? I have tried hard to find it, but failed. Any ideas ? I am particular interested in prime ...
0
votes
0answers
53 views

Recursive function

Having difficulty with a question, was hoping someone could take a look and explain (if) where i'm going wrong. Consider the following recursive definition of a function $f:N\to N$ Base case: For ...
0
votes
0answers
39 views

How many number of ways are there for getting a special prime?

Definition of special prime : Any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) is a special prime. Thus -21, -30, 0, 5, 14 etc are special ...
0
votes
0answers
65 views

Repeated function composition

I have a recursive function repeat, that composes n calls to f with a start value ...
0
votes
0answers
45 views

Find the characteristic equation of a recursive function

I want to determine whether the following recursive function is unstable; $$ x(t+1) = \left( wx+sx(t)^b \over w+x(t)^bs + (1-x(t))^b(d-s) \right) $$ Wikipedia is telling me that I want to have the ...