Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recursion]

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 a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory

3
votes
4answers
39 views

Solving non-linear recurrence relation $p_{n+1} = \frac{2p_n}{p_n + 1}, p_1 \neq 0$

Given the following recurrence relation $p_{n+1} = \frac{2p_n}{p_n + 1}, p_1 \neq 0$, I want to show that as $n \rightarrow \infty, p_n \rightarrow 1$. By assuming that such a limit exists, and ...
1
vote
1answer
32 views

Recurrence Relation Closed Formula

Consider the recursion $x_n = 3(x_0x_{n−1} + x_1x_{n−2} + · · · + x_{n−1}x_0)$, with $x_0 = 1$. Find closed form for $x_n$. Since this is non linear, I cannot assume $x_n=\lambda^{n}$ and try to ...
1
vote
0answers
19 views

Combinatorial argument for solution of recursion behaving similarly as Pascals triangle?

Given the following recursion: $$ F(n,d) = F(n-1,d) + F(n-1,d-1) + 1 $$ With initial conditions $F(0,d)=1,F(n,1)=1$ and $n\in\mathbb N_0, d\in\mathbb N$. I noticed that it holds (By writing out the ...
1
vote
0answers
23 views

Solving the recurence $T(n) = T(n/5) + T(7n/10) + n$ using substitution method

I am not sure how to handle this problem given no base case. Is it enough to assume that $T(n/5) + T(7n/10) <= c(n/5) + c(7n/10)$, and substitute that back in? This seems like a weak way of proving ...
2
votes
1answer
22 views

Structural induction on recursive function problem

Getting a bit stuck on the following problem: Let $B$ be the language over the alphabet {(,)} that is inductively defined as: $\Lambda$ $\in$ $B$ (where $\Lambda$ represents an empty string) If $X$ ...
2
votes
2answers
36 views

I'm having a hard time rationalizing the proof that $2^n > n^2$ if $n >4$

I'm not sure how to apply $n > 4$ in the proof, when I work it out I get that $n >2$... Basis Step $P(5) = 2^5 > 5^2 = 32 > 25 $ which is True Hypothesis assume $P(k) = 2^k > k^2$ is ...
0
votes
1answer
29 views

Definition of Productive set

I don't understand the definition of Productive Set in the Cutland's Computability book. DEFINITION: A set $A$ is productive if there is a total computable function $g$ such that whenever $W_{x} \...
0
votes
3answers
34 views

Find a formula for the sum of the first $n$ even positive numbers

I'm having a hard time grasping the concept of creating a formula to represent: $0 + 2 + 4 + ... + 2n$ when $n$ is a nonnegative integer. Looking it up I see that it is $n(n+1)$ However I can't ...
0
votes
3answers
28 views

How to understand this recursive definition?

My question is: Now know through my Discrete-Mathematics course what recursion is, but this notation confuses me. $$ \mathbf a_n = \begin{cases} n, & \text{for $ 0\le n \le 2 $ } \\ a_{n-3}+a_{...
0
votes
0answers
25 views

Floor Summation Closed Form?

Let $ a_1,a_2,a_3,...a_n $ be a set of positive integers. Does there exist any closed form for the approximation of the sum $$ \sum_{i=p}^n\operatorname{floor}\left(\frac{a_p}{i-p+1}\right) ?$$ If ...
2
votes
0answers
16 views

Validity of construction involving recursively defined functions.

I'm currently struggling with the validity of defining a function using what I think is membership of a recursively defined set. I am confused as to whether this construction requires the axiom of ...
0
votes
0answers
39 views

Is $\{x_{nk}\}$ defined by $x_{nk} = \frac{k}{k+n+1}$ computable?

Currently I am reading Pour-El and Richard Computability in Analysis and Physics. In Chapater $0$, they give a definition of computable double sequence. Definition: A double sequence will be ...
1
vote
1answer
73 views

Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively?

Question: Does the sequence $(\frac{1}{n})_{n=1}^\infty$ converge to $0$ effectively? The definition of effective convergence that I am using is: There exists a computable function $e:\mathbb{N}\...
0
votes
3answers
48 views

Solving a recurrence relation with a definite integral?

In my attempt to derive an equation for the population of Minecraft cows in a farm given some number of 5 minute periods, n; I'll spare the game mechanics at play. I came up with the following ...
2
votes
2answers
83 views

Are induction and recursion twin sisters?

I am asking a soft question. For me it feels like induction and recursion are dual to each other (in somewhat category-theory-like sense, which I can not define rigorously): both do have at least ...
1
vote
1answer
30 views

Half-catalan numbers

I've been interested in counting how many binary trees there are with n leaves. I consider 2 trees to be the same if I can swap the children of nodes to get the other one. I've started by figuring ...
0
votes
0answers
45 views

Is the finite set of all partial functions in $\mathbb{N}$, $f:(0,n)\rightarrow (0,n)$, computable?

I have developed the next conjecture: CONJECTURE: The set of all partial functions in $\mathbb{N}$, $f:(0,n)\rightarrow (0,n)$, being n a finite natural number, is a set of computable functions, ...
1
vote
0answers
46 views

Recursion with trigonometric functions

I have to solve a very strange recurrence relation. Has anyone an idea how to derive a closed formula for $r_i$? At least a 'good' upper bound would be nice. Currently I have no idea how to solve ...
0
votes
0answers
44 views

Is there any recursive relation

Is there any (recursive) relation over the below sums on a sequence of integer numbers $a_1$, $a_2$, $\ldots$, $a_n$? $$S_i = \left\lfloor\frac{a_i}{1}\right\rfloor +\left\lfloor\frac{a_{i+1}}{2}\...
1
vote
2answers
51 views
0
votes
0answers
19 views

Solving Recursion with a Ceiling Function

We are given an array $\{B_1, B_2, \dots, B_k\}$ with $B_i\geq 1$ for all $i$, and an integer $N >> max_i B_i$. The objective is to find upper and lower bounds to the terms $\{N_1, N_2\dots, ...
0
votes
0answers
46 views

Examples of computable sequence of rational numbers

I am a beginner to computability theory and curently reading Pour-El and Richard Computability in Analysis and Physics, Chapter $0$. At page $14,$ they provided a definition for computable sequence ...
0
votes
1answer
31 views

Would finding perspective distance using infinite subdivisions be impossible due to self-recursion?

I am currently trying to solve a perspective problem. Say you had a projected 3D rectangle (not neccesarily square) face defined by the four points $P_0,P_1,P_2,P_3$ as follows: My goal is to obtain ...
1
vote
1answer
37 views

How many ways are there to cover an 8 by 8 square with 32 identical 2 by 1 rectangles?

How many ways are there to cover an 8 by 8 square with 32 identical 2 by 1 rectangles? This is different from this question because the layout can be recursive on two dimensions. I would start from a ...
0
votes
1answer
42 views
1
vote
1answer
31 views

Probably recurrent function

Let there be a recurrent function, $f(n) = f(n-1)+f(n-2)+p_1f(n-1)+p_2f(n-2)$, where $p_1, p_2$ accept $0$ or $1$ with a probability of $\frac{1}{2}$. What is the mathematical expectation of the ...
0
votes
0answers
8 views

projection functions class closed by primitive recursion and composition?

I've stumbled upon the following exercise and I am having some doubts with the solution: Let $\mathcal{C}=\{{u_i}^n:1\leq i \leq n\}$ be the class of all the projection functions. Decide if the ...
1
vote
1answer
18 views

recursive relation on derangement of objects

Let $a_{n}$ represent the number of derangements of $n$ objects . If $a_{n+2}=p a_{n+1}+q a_{n}\;\forall n\in\mathbb{N}$ then what is $\displaystyle \frac{q}{p}$? What I have tried: I have used $$ ...
1
vote
1answer
41 views

Using the substitution method on $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$ [duplicate]

My task at hand is to find a tight asymptotic upper bound for the recurrence $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$. My initial idea has been to substitute $m=\lg n$ and define a new recurrence $s(m)=p(2^...
0
votes
0answers
9 views

Deriving AR(1) Time Series Model with repeated substitutions

I am simply trying to go from formula (2.10) to (2.11) in Analysis of Financial Time Series from Ruey Tsay. What I am not understanding is how the substitution results in 2.11 do not include the mean,...
1
vote
1answer
80 views

Show that $x \in W_{x}$ is undecidable

The Cutland's book called Computability has a theorem whose proof i don't understand and i have developed another simpler proof. Could you tell me if this proof is correct? DEFINITION 1: $\phi_{x}, x ...
0
votes
3answers
19 views

Find an expression for Sn+1 in terms of Sn and Sn-1 which holds for all n >= 2

Let Sn be the number of ternary strings of length n in which every 1 is followed immediately by a 2 (these strings cannot end with a 1). Find an expression for Sn+1 in terms of Sn and Sn-1 which holds ...
1
vote
0answers
21 views

Recursion ceiling and radicals of integers

Given $n,k\in\mathbb Z$ what is the minimum $r$ needed such that following iteration is $\leq2$? $$n_0=n$$ $$n_1=\lceil n_0^{1/k}\rceil$$ $$\vdots$$ $$n_{i+1}=\lceil n_i^{1/k}\rceil$$ $$\vdots$$ $$...
-3
votes
1answer
80 views

Are all non-computable functions from $\mathbb{N}$ to $\mathbb{N}$ denumerable?

In the Cutland book called Computability, there is a very interesting exercise on page 81. Show that the set of all non-computable total functions from $\mathbb{N}$ to $\mathbb{N}$ is not ...
0
votes
2answers
53 views

How to imitate a loop statement in math?

I need to iterate through expression several times and quit iteration process when certain value is reached but use algebraic notation. Summation notation would have worked if it didn't sum the ...
0
votes
0answers
5 views

Closed form expression for simple 2D recurrence

It is given that $T(i,j) = T(i-1,j) + T(i,j-1)$ with boundary conditions $T(i,0)=T(0,j)=1$. Does there exist a closed-form mathematical expression for $T(n,n)$? I tried making a table of values of $T(...
0
votes
0answers
12 views

Value of a Two Variable Recursive Function

I have a function $f(x, y)$ where the base cases are $f(0, y) = y$, $f(x, 0) = 0$, and $f(x, 1) = 1$. In all other cases, $f(x, y) = max(\frac{f(i+1, y-1)*i+f(i-1, y+1)*y}{y+i})$, where $i$ ranges ...
2
votes
1answer
48 views

How to find the second solution to an ODE of the form $xy''+y'-xy=0$?

I am learning about the Frobenius method to solving ordinary differential equations, but I seem to have some difficulty with finding the second linearly independent solution to the above equation (...
0
votes
2answers
30 views

Sinusoidal Generation in Recursive Algorithm

I need to generate sinusoidal values for varying frequencies. I'm making a DTMF tone generator but I must generate my own values of sine using recursive algorithms. The exact wording of how I'm ...
1
vote
1answer
28 views

solving the first 5 elements of a given recursion sequence

Given: The sequence $(u_{n})$ with $u_{n+2}=4 \cdot u_{n+1}-u_{n}$ and $u_{4}=194$ with $u_{1}<u_{2}$ , $u_{i} \in \mathbb{N}_{0}$ To solve: $u_{1},u_{2},u_{3},u_{5}$ I tried solving it by ...
0
votes
1answer
52 views

How to show a function is primitive recursive?

Show that the following function is primitive recursive, by giving its name in official notation, with names for functions drawn solely from the initial primitive recursive functions: f (x) = x^2 + 3x ...
0
votes
1answer
52 views

Competition algorithm

$n$ athletes ($a_1,...,a_n$) are arranged in a line. At each time $t$, two adjacent athletes race each other. The loser is removed from the line and the winner stays in the same position. This ...
0
votes
1answer
23 views

Closed form for an exponential recurrence

I was wondering what the closed form for a function $f(x)$ is when $f(x)=a*f(x-1)+b^\left(x-1\right)-c^\left(x+1\right)$, and $f(0) = d$ is given. Assume $a$, $b$, $c$, and $d$ are all greater than 1. ...
0
votes
2answers
28 views

Evaluating $T(n)=T(n-1)+c\log(n)$

$$T(n)=T(n-1)+c\log(n)$$ where $T(1)=d$ $$T(n)-T(n-1)=c\log(n)$$ $$T(n)-T(1)=c\sum_{i=1}^{n}\log(n)$$ $$T(n)-d=c\cdot n\cdot \log(n)$$ $$T(n)=c\cdot n\cdot \log(n)+d$$ So $T(n)=O(n\log(n))$ Is it ...
2
votes
1answer
82 views

How do I rewrite this integrals properly?

For a physics project I have to calculate the curvature of a certain particle which deflection dependent on it's current position. I've got three functions: $\theta{(t)}$ which is the deflection at ...
0
votes
0answers
15 views

Maximum Expected Fishing Day (Recurrence Relation)

John joined a meetup where organize day long fishing trip once a month. The organizers are vary poor at planning, so will organize fishing on a random day of the month without any advance notice. ...
1
vote
1answer
50 views

Prove a recursive function $f(p_i) = (p_i/2)g(p_i) \to \infty$ as $p_i \to \infty$?

Let's say we have a set of numbers $\{5,9,13,17,21,\ldots, 5+4i,\ldots\}$ and each $p_i$ is a member of this set, namely $p_0 = 5, p_1 = 9, p_2 = 13$ , etc. Consider the following functions defined ...
2
votes
0answers
88 views

Set of primitive recursive functions is not finitely generated

Let $PR$ be the set of of [primitive recursive functions][1]. Given $X\subset PR$, let $$ \hat X=\{ h(g_1(\vec x),\dots,g_k(\vec x)):k\in \mathbb{N}\wedge h,g_1,\dots,g_k\in X\}, $$ i.e. $\hat X$ is ...
-2
votes
2answers
26 views

Recursive Relation $T(n)=T(n-1)+1$

I have wrote a recursive code of the type: function(n){ if n==1: return else{ do something function(n-1) } Now I am trying to analyze the ...
3
votes
2answers
26 views

Andrew wants to cross a 12-foot long bridge. He can either take a 1 foot step or a 2 foot step.Provide a recursive formula for this problem.

Other notes about the problem: Keep in mind that a 2 foot step then a 1 foot step is different than a 1 foot step then a 2 foot step. I have found it easy to think of the bridge as a 1x12 game board ...