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

-1
votes
1answer
39 views

What's the ratio of liquids if I keep topping up one from another [on hold]

I have two containers with different liquids. 500ml and 200ml. I take a tiny sip from the 500ml, top it up from the small one, and mix thoroughly. I repeat this until the small one is completely empty....
0
votes
1answer
22 views

How do I interpret following equations on fibonacii numbers?

I went through an online tutorial (http://codeforces.com/blog/entry/14385) on finding n-th fibonacci number which explains a method as, You are standing at position n in Ox axis. In a step, ...
0
votes
0answers
33 views

Show that $\pi$ is a primitive recursive number [on hold]

Can anyone provide a proof that $\pi$ is a primitive recursive number, or suggest how I might prove it? Thanks
1
vote
5answers
69 views

Closed form of function $f(n) = (1/n) \sum _{x=1}^{n-1} f(x)$ [closed]

Could anyone help me get to the closed form of the function: $$f(n) = \frac 1 n \sum _{x = 1}^{n-1}f(x)$$ $$f(1) = 1$$
0
votes
0answers
22 views

Solving a logarithmic functional recursion

What does recursion $$T(N)=\left(\frac{N^{f(N)}}{(\log N)^{f(N)}}\right)^2T((N\log N)^{1-f(N)})$$ evaluate to where ${f(N):\Bbb R\rightarrow\Bbb R}$ is a function such that $f(N)\in(0,1)$ at every $...
1
vote
1answer
32 views

Using determinants to find a recursive sequence

I am trying to compute a three diagonal determinant in order to find the recursive relation. Let $\Delta_{n}$=$\begin{vmatrix} 11 & 3 & 0 & 0 & \dots & 0\\ 13 & 11 & 3 &...
0
votes
1answer
11 views

Existence of a injective and recursive(but not primitve recursive) fucntion that has a primitve recursive inverse.

The Question is as follows: For a one-to-one function f:N -> N, it's inverse is defined as: $$ f^{-1}(n) = \begin{cases} m+1 & \text{if }f(m)=n \\ 0 & \text{if } \forall m\in\mathbb N:...
1
vote
4answers
42 views

nonhomogeneous recurrence relation with $f(n)=4*n-3$

I am trying to solve this recurrence relation: $a_n=a_{n-1}+4n-3$ I was trying to solve it using characteristic equation. First I found homogeneous solution: $a_n-a_{n-1}=0$ $x=1$ $a_n=A*1^n$ And ...
0
votes
2answers
37 views

how many sequences above 1,2,3,4,5,6,7 that don't contain odd couples

I got stucked a little with this question. would appreciate your help. the question is "find a recursive relation that counts how many sequences of order n above ${1,2,3,4,5,6,7}$ that don't contain ...
0
votes
3answers
69 views

Find recurrence relation with general solution $a_n=A+Bn+C2^n+\frac{1}{3}n2^{n-1}$

General solution is: $a_n=A+Bn+C*2^n+\frac{n}{3}*2^{n-1}$ Can you give me some tips on solving this? Any help would be appreciated.
0
votes
0answers
90 views

Solutions to recurrence relations

Consider functions $s_{m},c_{m},d_{m}$ defined by the following recurrence relations $$s_{1}=n$$ $$c_{1}=s$$ $$d_{1}=0$$ $$s_{2}=n$$ $$c_{2}=s-n$$ $$d_{2}=d$$ $s,n, d$ are integers. If $c_{m}>...
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
280 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
1answer
23 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
257 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
38 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
1answer
19 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
32 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
40 views

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
32 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
19 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
22 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
790 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
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 ...
1
vote
0answers
25 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
23 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
28 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
50 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?
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
60 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
52 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
129 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
28 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 ...