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

0
votes
2answers
52 views

Solving a recurrence relation such that $\sum_{k=0}^\infty x_k = 1$

Question Let $x_0$ be arbitrary, $p \in (0,1)$ and assume the following holds: $$x_1=\frac{(1-p)^2(1+2p)}{p^3}x_0$$ $$x_2=\frac{(1-p)^3(1+3p-3p^3)}{p^6}x_0$$ and in general: $$ x_k(1-p)^3 + 3p(1-p)^2 ...
0
votes
0answers
18 views

Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
0
votes
2answers
33 views

Solving a recursive relation

Let $\{c_t\}_{t = 1}^k$ be a (non-monotone) sequence of real numbers such that $c_t \in (0, 1]$ for all $t = 1, \dots, k$. Consider the recursive sequence $$ \left \{ \begin{array}{ll} x_1 & = c_1 ...
0
votes
0answers
38 views

Recurrence relationship for crawling a directory

I am trying to write a recurrence relationship for problems that can be solved using recurrence. As an example recurrent for finding the 3^4 (which is 3*3*3*3) can be written as: ...
0
votes
3answers
44 views

How to create a formula for a recursive sequence? [duplicate]

Let $\left (a_n \right )_{n=1}^{\infty}$ be an infinite sequence. $\left (a_n \right )_{n=1}^{\infty}$ is defined by: $a_1 = 0$ $\; \; \; a_{n+1} = \frac{1}{1+ a_n}\; \; \forall n \in \mathbb{N}...
0
votes
0answers
35 views

Panjer’s family of distributions and Probability Generating Functions

This isn't homework etc just revision where I do not have the solutions and I have no idea how to approach this question. Any tips or guidance will be greatly appreciated. Thanks. Let the probability ...
1
vote
1answer
15 views

Understanding the derivation of the Bellman equation for state value function

In reinforcement learning theory, from Sutton and Barto, page 46-47 the Bellman equation for a state-value function is: \begin{equation} \begin{aligned} v_\pi (s) :&= \mathbb{E}\left[G_t | S_t=s\...
1
vote
0answers
35 views

Sum of an odd recursive sequence

Let $a_0 = 1$ $a_1 = 1 - \frac{e}{2}$ $a_n = \frac{e}{2^n} - \frac{1 - a_{n-1}}{n - 1}$ for $n > 1$. Find $\sum_{r=0}^{\infty}a_r$.
0
votes
0answers
12 views

Computability: Primitive Recursive Predicate Existence iff computation is defined

If T is a primitive recursive predicate. How do I prove that if comp(p,x) is defined ⇔ ∃y. T(p,x,y) I thought of a function with x as input for each q,y, if the T(q,y,x) holds then it is defined, ...
0
votes
1answer
29 views

How many combination to choose k out of n with recursion - wrong answer help

How many combinations of choosing $k$ numbers out of $\{1,2...,n\}$ so there are no consecutive numbers in a group, example: $\{1,4,9\}$. Find a recursion formula for $n\geq 0, k\geq0$. I was ...
0
votes
2answers
57 views

A sequence $A(n)$ that satisfies $A(n) = \frac{A(n-1) + A(n-2) + A(n-3)}{3}$

Show that there exist $c_1, c_2, \lambda_1, \lambda_2 \in \mathbb{C}$ such that $A(n)= c_1\lambda_1^n+c_2\lambda_2^n + c_3$ for all $n \geq0$ Hint: The system that defines $A(n)$ is linear of third ...
1
vote
0answers
33 views

Recurrence in exercise divides and conquers

I am new to this site, I hope to contribute. For now i have the following problem of recurrences in a subject of discrete mathematics: Consider the algorithm, called StoogeSort in honor of the ...
0
votes
0answers
18 views

recursive integral with small coefficient

I have a recursive equation that looks like this: $$\beta^{i+1}(x) = C^2\int_{0}^1 dy \frac{y \beta^i(y)}{y[\alpha(y)^{i}]^2 + [\beta^{i}(y)]^2}$$ $$\alpha^{i+1}(x) = 1-C \int_{0}^1 dy \frac{y \...
2
votes
1answer
85 views

Why such a complicated definition of recursion for $\mathbb{N}$ in HoTT?

The HoTT book defines $\mathbb{N}$ to have $0:\mathbb{N}, succ: \mathbb{N\to N}$ and a recursion constructor $\prod_{C:\mathcal{U}}C\to (\mathbb{N}\to C\to C)\to \mathbb{N}\to C$ with a certain ...
0
votes
1answer
23 views

Find the recursive definition for these two sets of numbers

Good afternoon, I'm struggling with finding the proper recursive definitions for these two sets of numbers: problem 1: 1, –1, 2, –2, 4, –4, 8, –8, 16, –16, … problem 2: 1, 2, 3, 6, 11, 20, 37, 68, ...
0
votes
1answer
26 views

write a recursive definition of strings

How would I construct a recursive definition for a function f, on strings over the alphabet {a,b,c} such that f(x) returns the same string expect every occurrence of b is replaced by c.
0
votes
0answers
42 views

How we can count the number of squares that contain a point?

For n squares. Each square is determined by the coordinates of the bottom-left point and the length of each edge. The i th square has the coordinates of the bottom-left point is $(x_i, y_i)$ and the ...
5
votes
2answers
82 views

finding a solution for this recurrence relation

Find the sequence satisfying the recurrence relation $$n a_{n+1} = (n+1) a_n+n(n+1)$$ with the initial condition $a_0=0$. I'm trying to find a solution for this recurrence relation. After dividing ...
0
votes
0answers
20 views

Strategy for determining the closed form of a sequence

Is there a strategy that I should be implementing when trying to find the closed-form of sequences? Right now, I'm relying a fair bit of pattern-recognition (i.e. it's a crapshoot), which isn't ...
0
votes
1answer
27 views

Two different approaches yield different results

The problem: < Find the base cases and a recursive step to the number of possibilities to place n different balls in r different cells when each cell must contain at least one ball. I have two ...
1
vote
1answer
33 views

Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p $ and (...
0
votes
1answer
41 views

Recursion formula to number of binary vectors without $k$ $1$'s

Find a recursion formula for the number of binary vectors in length n that doesn't contain $k$ consecutive $1$'s. $(k\geq 2)$ If $n<k$ it's clear there are not limitations therefore $2^n$. If $n\...
2
votes
2answers
67 views

Recursional Formula for Integration

Consider the following integral, $$I(n)=\int_0^{\pi/2}\cos^nx\cos(nx)dx $$ I tried taking one $\cos x$ out and then integrating by parts. I also tried integrating by parts using $\cos(nx)$ as the ...
1
vote
0answers
22 views

Random recursive function that stays near the initial value

I am working on a procedural CG scene and have populated a starry sky with particles of random size. My goal is to make the stars twinkle - in this case, by varying their size and/or alpha channels. ...
0
votes
0answers
18 views

Reed,Simon Theorem XII.1: Use of recursive substitution in the proof

We have a function $F(\beta,\lambda)$ (polynomial of degree $n$) which is analytic near $\beta_0$ and $\lambda_0$. So we can write $$F(\beta,\lambda)=\sum_{m=0}^n(\lambda-\lambda_0)^mf_m(\beta)$$ ...
0
votes
0answers
28 views

When is the system of recursive equations $y_{n+1} = Ay_n$ stable?

Let $y_n = (y_{1n}, y_{2n})^T.$ I'm wondering what the condition on the matrix $A$ is for the recursive system of equations $$y_{n+1} = Ay_n$$ to be stable (i.e neither $y_1$ or $y_2$ blows up). Can ...
0
votes
1answer
31 views

A specific and interesting recurrence relation

Let f and g be increasing functions such that the sets {f(1),f(2),...} and {g(1),g(2),...} partition the positive integers. Suppose that f and g are related by the condition g(n)=f(f(n))+1 for all $n&...
1
vote
1answer
56 views

Give a closed formula for the recursive series of $S_1 = \frac{a_1}{b_1}, S_{n+1} = \frac{a_{n+1}}{b_{n+1}+S_n}$

The Problem: The following real numbers are given: $$a_1,a_2,a_3,...\in\Bbb{R}\backslash\{0\} \\ b_1,b_2,b_3,...\in\Bbb{R}\backslash\{0\}$$ We define a recursive series of: $$S_1 = \frac{a_1}{b_1} ...
1
vote
3answers
40 views

What is this recursive function approximating? ($x_i = x_{i-1}^2 / x_{i-2}$)

I came across this recursive function in some code, and it is within a function called "interpolate". Essentially the rule is: $x_i = x_{i-1}^2 / x_{i-2}$ which can also be defined as: $x_i = \...
2
votes
0answers
36 views

What is a method to prove this trigonometric recursion without mathematical induction?

tl:dr at the end: So I started of scribbling this simple function in my notebook $ f(\theta) = (1+\sin\theta + \cos\theta)$ $ = \sin^2\theta + \cos^2\theta + \sin\theta + \cos\theta$ $ = (\sin\...
0
votes
0answers
27 views

Power series solutions for solving ODE

Consider the equation $$ \rho^2t''-2\rho^3t'+[(\epsilon''-1)\rho^2-\frac1{\sqrt{\omega_r}}\rho-l(l+1)]t=0 \tag{1} $$ where $$ t(\rho)=\rho^m\sum_{v=0}^\infty a_v\rho^v \tag{2} $$ and where $m=l+1$ and ...
0
votes
1answer
19 views

How can I choose the highest resulting combination out of arbitrary sized chunks, worth an arbitrary amount each

I am given a set of companies that each want to buy my product in different sized chunks. I have a maximum of 28 Million units to sell and each company pays a different amount of money for their order....
3
votes
1answer
89 views

Prove $O(\frac{1}{T})$ convergence rate

Suppose we have the following first-order non-homogeneous recurrence relation $$z_{t+1} \leq \frac{1}{(1+b_1c_t)^2}\big(\left(1+b_2c_t^2 \right)z_t + b_3c_t^2\big) $$ where $t$ is an integer which ...
0
votes
0answers
97 views

dynamic programming - recursion

We have $n$ requests to plant trees. Each request comes with a position $p_i$ which means we have to plant the tree $p_i$ meters away from a specific constant point. Also, there should not be another ...
4
votes
4answers
219 views

Closed form of recurrent arithmetic series summation

Knowing that $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$ how can I get closed form formula for $$\sum_{i=1}^n \sum_{j=1}^i j$$ or $$\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j k$$ or any x times neasted ...
-1
votes
2answers
36 views

Recurring Decimal in base 3

I have this decimal $y=0.012012012012....$ I was wondering how I could put this into the form of a rational number in base 3. So far I have $y= \frac{0}{3}+\frac{1}{3^2}+\frac{2}{3^3}+\frac{0}{3^4}......
1
vote
0answers
24 views

Non existence of certain hyperarithmetical functions

In what follows, $\phi_n$ is the $n$th partial recursive function, and $\phi_n^g$ is the $n$th partial recursive function with oracle $g$. We say $x\in\mathbb{N}$ is pre-total if the following two ...
0
votes
2answers
18 views

Backward substitution of a difference equation

I was trying to understand the intuition behind this. I understand how the following reccurence was done: $$X_{t} = \alpha X_{t-1} + C^{2}$$ $$ \alpha X_{t-1} = \alpha X_{t-2} + C^{2} $$ $$ \alpha^{...
1
vote
1answer
24 views

Trouble finding the formula for f(n) of a recursive function.

I've been working on this problem: Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If ...
1
vote
1answer
94 views

Recursion with three variables.

For u(a,b,c) is a function of a,b,c $\in Z $, We have the recursive relationships: $$u(a,b,c)=1/6[u(a-1,b+1,c)+u(a-1,b,c+1)+u(a,b-1,c+1)+u(a+1,b-1,c)+u(a,b+1,c-1)+u(a+1,b,c-1)]+1$$ and constraints: ...
0
votes
0answers
30 views

Question 18 from chapter 1 concrete mathematics. Problem in understanding the solution.

I was trying to understand the solution of problem number 18 of the first chapter of Concrete Mathematics. The question is as (where $Z_n$ is the maximum number of areas possible by the intersection ...
4
votes
1answer
62 views

Finding a closed form for coefficients in $x^{3n}=x_0\left(a_nx+b_n+\frac {c_n}{x}\right)$

Consider, $$ x^3=x+1 $$ Let $x_0$ be a solution to the above equation. Now consider $x^{3n}$. For $n=2$ we have: $$ x^6=(x+1)^2 $$ $$ =x^2+2x+1 $$ $$ =x\left(x+2+\frac {1}{x}\right) $$ $$ =x_0\left(x+...
2
votes
5answers
108 views

Can $a(n) = \frac{n}{n+1}$ be written recursively?

Take the sequence $$\frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \dots$$ Algebraically it can be written as $$a(n) = \frac{n}{n + 1}$$ Can you write this as a ...
2
votes
1answer
37 views

Deterministic rule sets and unique $\Phi$-proofs

I'm studying generalized inductive definitions and I got the following question; here, I use the "rule" definition of a g.i.d., instead of the monotone operator approach. So let $\Phi$ be a set of ...
0
votes
0answers
30 views

Explicit formula for recursive equation

I would like to find the explicit formula for $f(a)$, where the recursive formula is $f(a)=(a^2+r^2)p-q^2-f(r)$, $p=\lfloor 1+\log_2 a \rfloor$, $q = 2^p$, and $r=q-a$. The base case is $f(1) = -1$. ...
0
votes
5answers
32 views

Finding a formula for $f(n)$: $f(0)=1, f(1)=2, f(n)=2f(n-2)$ for $n \ge 2$

I had a hard time figuring out a formula for this. Is there a trick that could be used? The formula in the back of the book is $2^{\lfloor \frac{n+1}{2}\rfloor}$ for $n > 0$.
2
votes
0answers
25 views

Does the series of the inverse of 10 to the power of the Recaman sequence converge?

I was wondering if the following series converged: $$\sum^\infty_{n=0}\frac{1}{10^{R_n}}$$ Where $R_n$ is the n-th number in the Recaman sequence. My original thoughts were that it would converge if ...
0
votes
0answers
37 views

Proof by induction: Summation and recursion

I am fairly new to mathematical proofs, so there are things that may look essential that I still don't know. I was stuck on this problem. Let $u_1=2$ and $u_n=2+\sum_{i=1}^{n-1} 2^{n-2i} u_i$ , $\...
2
votes
1answer
32 views

Recurrence relation paths traced on a tetrahedron

I am attempting a recurrence relation question in which the number of possible length $n$ paths $a_n$ is being calculated. A path is defined as a traversal along a tetrahedron between connected ...
0
votes
0answers
32 views

A recursive sum [duplicate]

Let's say we start with the number one, then we add $(1/1)$. Now we have $2$. Then we do $2 + (1/2)$. Now we have $2.5$. Then we do $2.5$ plus $(1/2.5)$. If we continue this forever, I am fairly sure ...