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

0
votes
1answer
36 views
+50

A question about many-one reducibility of two sets

We want to show that $ \big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea. Would be grateful for your help.
2
votes
1answer
40 views

I need a common term for a recursive sequence

Some days ago, I made a question here about a common term for recursive sequence. I gained very good solutions. Thanks again. Today, I was thinking of a general case which is given below. Assume $p$ ...
3
votes
2answers
273 views

Find a formula for a sequence

I'm trying to find a formula for the following sequence: $\{\sqrt{3},\sqrt{3\sqrt{3}},\sqrt{3\sqrt{3\sqrt{3}}},...\}$ I thought of solving it recursively and I got this formula: $a_{n}=\sqrt{3*a_{n-...
0
votes
0answers
13 views

Showing a function, defined by bounded maximization of a parameter where another function is zero, is primitive recursive [closed]

Let $g:\mathbb N^2 \to \mathbb N$ be a primitive recursive function and define $f: \mathbb N \to \mathbb N$ by $f(n)$ = largest $m$ such that $m \leq n$ and $g(n,m) = 0$. If there is no such $m$, set $...
6
votes
2answers
253 views

The largest root of a recursively defined polynomial

Suppose that for all $x \in \mathbb{R}$, $f_1(x)=x^2$ and for all $k \in \mathbb{N}$, $$ f_{k+1}(x) = f_k(x) - f_k'(x) x (1-x). $$ Let $\underline{x}_k$ denote the largest root of $f_k(x)=0$. I ...
0
votes
1answer
20 views

Does the recursion theorem give practical means of constructing the indices mentioned in it?

I'm going through a textbook and the recursion theorem was introduced. The proof is a bit all over the place and kind of hard to follow so I thought I'd ask my question here. The theorem, as stated in ...
11
votes
4answers
787 views

How to find explicit formula for two recursions?

I have to find explicit solution for two intertwining recursions $$\begin{align} f(n)&=f(n-2)+2g(n-1) \\ g(n)&=g(n-2)+f(n-1) \end{align}$$ for $f(0)=1, f(1)=0, g(0)=0 ,g(1)=1$. What ...
0
votes
1answer
35 views

Recursive Definition of Bitstrings exam help

I have an exam and my instructor told me to know how to solve this type of question could anyone help? not sure what to do. "A bit-string is a finite sequence of zeros and ones. For this question, ...
0
votes
0answers
16 views

Primitive recursive function, constructing a proof

I've came upon an example in the book that is not that clear to me. The disparity function is proved to be primitive recursive in the following way: $$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(...
1
vote
1answer
24 views

# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ...
0
votes
0answers
40 views

Solution to a first order linear difference equation

The two questions are with respect to the following first order linear difference equation $(Y_{t} - Y_{t-1}) = (1-\lambda) (X_{t-1} - Y_{t-1})$, for $t \geq n$ Also, note that the process ...
1
vote
1answer
31 views

Validate Dobinski's formula using recursive Bell number formula

As we know, Bell number can be given using two formula $B_N=\sum_{k=0}^{N-1}C_{N-1}^{k}B_k$ (recursive) $B_N=e^{-1}\sum_{k=0}^{\infty}\frac{k^N}{k!}$ (Dobinski's formula) Now I want to substitute ...
1
vote
1answer
404 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
0
votes
1answer
50 views

Help to solve Divide and Conquer

How can I solve the following Divide and Conquer example? If you don't have enough time please just tell me the idea? Thanks $$T(n)=T\left(\frac{n}{7}\right)+T\left(\frac{11n}{14}\right)+n$$
0
votes
0answers
31 views

How to show that a function is primitive recursive?

If we have a function $g ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N}$ which is primitive-recursive. How to show that the function $f ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N} $ with $f(x_1, ~...~, ...
6
votes
0answers
159 views

A new type of Arithmetic-Harmonic mean for $n$ numbers

Let's introduce the following iterative procedure. Take two numbers $x_0$ and $y_0$. $$a_0=\frac{x_0+y_0}{2}~~~~~~~~~~~b_0=\frac{2x_0y_0}{x_0+y_0}$$ $$x_1=\frac{x_0+a_0+b_0}{3}~~~~~~~~~~~y_1=\frac{...
0
votes
1answer
18 views

the set of extendable p.c. functions is not N

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$. Would be grateful for your help.
0
votes
1answer
20 views

Modeling the maximum number of moves in Tower of Hanoi problem

What would be the recursive algorithm for solving the Tower of Hanoi problem (with n disks and 3 pegs) in maximal number of moves (i.e. going through all possible disks/pegs combinations).
0
votes
1answer
38 views

Prove a relation is primitive recursive, x is prime?

Is $\{x \in \mathbb{N}| \mbox{ x is prime}\}$ primitive recursive? Hello, $x \in \{x \in \mathbb{N}| \mbox{ x is prime}\} $ if and only if $ \forall y : y \le x \Rightarrow (y=1 \vee y=x \vee \neg (...
4
votes
0answers
46 views

Computing cube roots using three number means

I've asked a question some time ago about Computing square roots with arithmetic-harmonic mean but it turned out that this method is exactly the same as Newton's method (or Babylonian method) for ...
4
votes
0answers
69 views

Skiponacci: $p | a_p$ Alternate Solution

For the Skiponacci sequence: $a_0=3, a_1=0, a_2=2,$ and $a_{n+1}=a_{n-1}-a_{n-2}$ for $n>2$, prove that any prime $p$ divides $a_p$. Is there any alternate solution other than using ...
0
votes
1answer
612 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 \\...
6
votes
2answers
331 views

Precisely, what is a primitive recursive definition?

If I understand correctly, the language of primitive recursive arithmetic has a distinguished function symbol $S$, together with a function symbol for each primitive recursive definition (hereafter ...
1
vote
0answers
24 views

Variance of exponential moving average

I'm not quite sure what the form for the rolling recursive variance should look like. I have that the recursive average is $m_t = \alpha x_t +(1-a)m_{t-1}$. Then would the rolling recursive variance ...
1
vote
0answers
19 views

Nodes equation: can't 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
34 views

Any way to characterize this family of polynomials?

I have a family of polynomials generated by the recurrence relation $P_{n+1}(w) = (1+w)P_n ^{\ \prime}(w) -(3n-1 +nw)P_n(w) \\ P_1(w) =1$ The family is related to the Lambert $W$-function by its ...
0
votes
0answers
36 views

What does this theorem say in english?

Let $(P,Sc,1)$ a Peano's system, $G:P\times P\rightarrow P, H:P\rightarrow P$ are functions. Then $\exists ! F:P\times P\rightarrow P$ such that i)$F(x,1)=H(x)\forall x\in P$ ii)$F(x,Sc(y))=G(x,F(x,...
1
vote
1answer
35 views

A Question about Computable Functions

Barry Copper states following in his Computability theory book which I have a question about them. Exe.4.5.1: Show that if $\varphi_e(x) \downarrow $ is a computable relation, then so is ...
1
vote
2answers
138 views

Proof of x-intersection of the Mandelbrot Set?

I'm trying to prove that the Mandelbrot set intersects the X-axis on the interval [-2,.25]. I understand and have proven that the Mandelbrot set lies in a radius of 2. Mostly, I'm wondering how to ...
1
vote
1answer
77 views

factoring cubic polynomial equation using Cramer's rule.

1) I have question about factoring cubic polynomials. In my note it says "Any polynomial equation with positive powers whose coefficients add to 0 will have a root of 1. Another, if sum of the ...
0
votes
0answers
21 views

How to solve a nonlinear recursion relation?

Given the following recursion relation \begin{equation} E^{(n)}=(E^{(n-1)}-\alpha_1)\,e^{-\alpha_2\,(\alpha_3E^{(n-1)}+b)} \end{equation} where $\alpha_i$'s and $b$ are some constants. I am trying ...
1
vote
2answers
37 views

Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles.

There are three kind of tile. One is of size 1. Second is of size 2 of green color. Third is of size 2 with blue color. These are the values I found but I can not figure out the formula. P1 1 p2 3 p3 ...
0
votes
0answers
27 views

Are these functions computable - Understanding computable functions

There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...
2
votes
3answers
48 views

Recursion Proof by Induction

Given: f(1) = 2 f(n) = f(n-1) + 3, for all n>1 It can be evaluated to: ...
1
vote
1answer
30 views

What is the slowest growing function that is total but not primitive recursive?

For what I have in mind is the Ackermann-Buck function. If there isn't a slowest growing function do you have examples of other function slower growing than Ackermann-Buck's function?
3
votes
1answer
128 views

Is there some kind of deep relationship between substitution and recursion?

Define $\mathbb{N}$ as the initial object in the following category: Objects. Sets $X$ equipped with a function $S : X \rightarrow X$ and an element $0:X$. Morphisms. Functions that preserves ...
0
votes
1answer
25 views

A Question About Recursive Functions

We want to find a recursive function $f(x,y)$ in order to have this equality: $$ \mathbf \varphi_{f(x,y)} = \varphi_x + \varphi_y$$ I know we should use "s-m-n" theorem, but I can't find the ...
0
votes
2answers
30 views

Finding Recursive formula for value of a game

I understand the value of the game changes depending on what pile I take the coin from. If I take a coin from the front, I get $i+1$ coins (if I take $i = 1$, now $i =2$). This happens until $i = j$ ...
0
votes
0answers
17 views

Ordinals defined by successor and union

Let $M$ be the smallest set of ordinals satisfying $0\in M$ $x\in M\implies x+1\in M$ $S\subseteq M\implies \bigcup S\in M$ What does $M$ look like? Is it all ordinals? Is it all countable ...
1
vote
1answer
74 views

Recursive calculation - How would it be started?

First off, let me assure you that this is my very last resource. I have tried everything, because I understand that posting a question that needs a hyperlink to be understood is annoying. But I would ...
0
votes
0answers
58 views

How to find the first 5 values of a recursive relation where certain sequences are not known?

Write down the first five values of each of the following recursive sequences. (a) r(0) = 2, r(n) = [r(n-1)] -n -1 for all integers n>=1 (I couldn't write the values as ace of r and s so I just wrote ...
0
votes
1answer
51 views

Find a Recursion Formula with boundary conditions

A game is played as follows. Coins with value $x_1, . . . , x_n$ are laid on a table in a row. Two players alternate turns taking a coin from either end of what’s left of the row of coins until the ...
0
votes
1answer
38 views

Valuing a game using recursion

An urn contains 4 marbles: 2 red and 2 green. You extract them one by one without replacement. If you extract a green marble, I pay you 1 dollar; if you extract a red marble, you pay me $1.25. You can ...
0
votes
0answers
27 views

Solving a recurrence relation using a subtitution method $T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) $

I got stuck when I want to solve this recursive relations by substitution $$ T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) . $$ $$ T(n+1)=2 T(\frac {n} {2} )+ \Theta\left(n\right) . $$ $$ T(n)=T(\...
0
votes
0answers
26 views

Finding a shorter recursive equation

The assignment is the following: (a) Given a sequence $(a_n)_n$ which satisfies the recursive equation $a_n = \sum\limits_{k = 1}^d c_k \cdot a_{n-k}$ with $c_d \not= 0$. Furthermore $Q = 1 - c_1t - \...
0
votes
0answers
14 views

Nature of state - recursion?

I always wondered how mathematicians define state (or rather: where it comes from?). This is tricky, because I always thought that in math there is only one "thing" - a pure, stateless function. Few ...
1
vote
1answer
59 views

How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
0
votes
1answer
20 views

How to find the function that is computed from a recursive algorithm? [closed]

The following is a recursive algorithm : Procedure unknown(n belongs to N) If n=0 then return 0 else return unknown (n-1)+5 The function that is computed from ...
2
votes
2answers
162 views

Understanding the step-hop problem mathematically

I am working on a problem where one is given n number of steps. They can take either one, two, or three steps. How many number different possible ways are there to climb the n steps? I can solve this ...
0
votes
2answers
250 views

Solving the Recurrence Relation/Series fn = 1 + fn-1*(M) where M is a constant

So I'm trying to solve this week's FiveThirtyEight Riddler. In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people ...