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

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
271 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 [on hold]

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 $...
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 ...
6
votes
2answers
252 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
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 ...
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.
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, ~...~, ...
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).
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 ...
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 ...
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
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
67 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 ...
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
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 ...
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 ...
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
29 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?
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 ...
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 ...
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
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 ...
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
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 ...
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
161 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 ...
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
26 views

primitive recursive conditional

I am confronted with the assertion that the following expression describes the conditional: $\text{Cond}\left[ t, f, g \right] = \text{Pr} \left[pr^2_1, pr^4_2 \right] \circ(f,g,t)$. This is meant ...
0
votes
0answers
6 views

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
0
votes
1answer
18 views

Midpoints of a recursively subdivided square

I have a rectangle that I recursively subdivide along the horizontal and vertical axis in successiv order. The sides of the rectangle are both equal to one so the original midpoint is (x, y) = (0.5, 0....
4
votes
1answer
64 views

Prove that for $k>1$ $a_n$ is a perfect square

I'm having problems with this exercise. Let $k > 1$ be an integer. We define $(a_n)_{n \in \Bbb N_0}$ as: $$a_0 = 1$$ $$a_1 = 1$$ $$a_{n+2} = (k^2-2)a_{n+1}-a_n-2(k-2)$$ Prove that $\forall n \in \...
0
votes
0answers
14 views

Recurrence relation without master's theorem

$$T(n) = T(n/2) + O(n \log n).$$ I don't think I can use master's theorem because $a = 1$, $b = 1$ then $\log b a$ is $log_2(1) = 0$. And $f(n) = n\log(n)$, so $c = 1$. Then $c \ne 0$. So second form ...
1
vote
4answers
53 views

Mathematical Notation of Sequence of Functions

Let's say I have a finite set of functions $F=\{f_1,f_2,f_3,...,f_n\}$ and I want to show a recursive function that is constructed by an arbitrary sequence of applications of functions in $F$ to input ...
2
votes
1answer
33 views

Enumerating the primitive recursive functions without repetition

According to this paper (and this one), it is possible to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. I am ...