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
vote
1answer
108 views

a recurrence relation for mountain permutation

I really dont know where to start? Can you give some hints?
3
votes
1answer
85 views

What lies between primitive recursion and total recursion?

My understanding is that there are total recursive functions that are not primitive recursive, such as the Ackermann function. What classes of functions (or sets) lie between primitive recursion and ...
0
votes
0answers
24 views

Solving $T(n)=T(n-1)+\log n$ with repeated substitution

Solve $T(n)=T(n-1)+\log n, T(1)=1$ using repeated substitution. Substituting back, we have: $T(n) = T(n-i) + log(n-i+1) +... + \log(n-1)+\log(n)$ And for which $i$ we have $n-i=1$? that is ...
0
votes
0answers
33 views

Proof of Master Theorem using Recurrence Relation By Substitution

Question : T(n)=10⋅T($⌈\frac{n}{3}⌉$)+O($n^2$) I have a solution to that problem but it uses other approach. I'd like to use recursion by substitution method but I'm stuck at the last stage. Here's ...
2
votes
0answers
8 views

Naive Euclidean algorithm - average complexity?

Suppose I compute the GCD in a rather simple-minded recursive way: $$ \gcd(a, b) = \begin{cases} \gcd(a, b-a) & \text{ if }{a < b}, \\ \gcd(a-b, b) & \text{ if }{a > b}, \\ a & ...
0
votes
1answer
23 views

How can I write a partial recursive function “maximum(x,y,z)”?

It is quite easy to write a partial recursive function "max(x,y)": 1.substraction1: substraction(x) = if x=0 then 0 else x - 1 @R(z1,i21) 2.substraction2: substraction(x,y) = if x < y then 0 ...
1
vote
2answers
40 views

Showing that a Sequence is defined recursively

How can I show that the sequence is defined recursively? Show that the recursively defined sequence $(x_n)_{n\in\mathbb{N}}$ with $$x_1=1, \qquad\qquad x_{n+1}=\sqrt{6+x_n}$$ converges and ...
1
vote
1answer
43 views

Recursive formulas and integration [duplicate]

Using integration by parts find a recursive formula of $\int cos^n(x) dx$ and use it to find $\int cos^5 x dx$ I have no idea how to do this and my knowledge does include integration by parts etc. I ...
0
votes
1answer
40 views

Recursion for strings

Write a recursive procedure to compute the number of strings from {A, C, T, G} of length n that do not have 2 consecutive A’s
0
votes
1answer
26 views

Big O - Recurrence

I am given a function as follows: ...
10
votes
1answer
191 views

Solving a recursion efficiently

I have a recursive formula $$v(n+1) = v(n)\dfrac{1+v(n-1)-n}{1+v(n-1)-v(n)}$$ and I also know $$v(1)=2v(0)$$ $$n+1 \le v(n+1) \le v(n)+1.$$ I wish to find, for example, $v(10)$ more efficiently than ...
0
votes
0answers
20 views

What many associative ways are possible an expression of n variables? [duplicate]

Let's say we have an expression AxBxC and x is associative. Then we can solve it as (AxB)xC or Ax(BxC) i.e 2 ways, similarly for 3 variables, I found 5 ways. How can we find a general formula for n ...
1
vote
4answers
65 views

Prove that $x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n}\geq\sqrt{2}$

Let $(x_n)_{n\in\mathbb N}$ be a recursively defined sequence with $x_1=9$ and $$x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n}\text{ for }n\geq 1.$$ Show that $x_n\geq\sqrt{2}$ for all $n$. Because ...
1
vote
1answer
73 views

What is the inverse to hyperoperation for positive integers?

According to Wikipedia hyperoperation for positive integers is defined as $$ H_{n}(a,b)=H_{n-1}(a,H_{n}(a,b-1)) $$ with some base conditions. Question: Recursivly define a sequence of binary ...
2
votes
0answers
36 views

What is the solution to this recursion?

Take $a_0=10^6$. What is $a_n$ (asymptotically) where $a_{i+1}=a_i+\sqrt[\alpha]{a_i}$ where $\alpha>1$? How fast does $a_n$ grow?
6
votes
1answer
83 views

Game in a circle

$N$ players play a game. They stand in a way such that they form a regular $N$-gon. Players are numbered from $1$ to $N$. The players throw boomerangs in clockwise order, in turns. At first player $1$ ...
2
votes
4answers
95 views

Limit of sequence $a_{n+1}=3/(2+a_n)$, $a_1=0$

The task is to find the limit of sequence, given by following recursion: $$ a_1=0, a_{n+1}=\frac{3}{2+a_n} $$ so at first I tried to find some first parts of the sequence $$a_1=0, a_2=\frac{3}{2}, ...
0
votes
2answers
39 views

Expression using powers of n for recursive summation notation

I have this question: Find an explicit expression, i.e. a simple fraction involving powers of n, for the following sum: $\sum_{j=1}^n \sum_{k=j}^n k$ Setting n at 5, I can see that the notation ...
2
votes
1answer
59 views

Use of pigeonhole principle in ramsey-theorem about monochromatic triangles.

Im trying to prove that for any number n the complete graph with $p(n)$ vertices whose edges have been colored with n colors in some way has a monochromatic triangle (a triplet of nodes that are ...
0
votes
1answer
29 views

Recursion equation - problem with one same root

i have problem with Recursion equation. It look like this: $x(k+2) + 2x(k+1) + x(k) = 0 $ , $x(0) = 3$, $x(1) = 6$ then i' m gettin: $x^2 + 2x + 1 = 0$ zero value are: $\Delta = 0$ , $x_{0} = -1$ ...
0
votes
1answer
23 views

Showing S is a subset of A by structural induction.

I have a problem similar to: Let S defined recursively by (1) 5 ∈ S and (2) if s ∈ S and t ∈ S, then st ∈ S. Let A = {5^i| i ∈ Z+}. prove that S ⊆ A by structural induction. I've only done ...
1
vote
1answer
28 views

Proving A is a subset of S by mathematical induction?

Suppose I have a question similar to: Let $S$ be defined recursively by (1) $5 ∈ S$ and (2) if $s ∈ S$ and $t ∈ S$, then $st ∈ S$. Let $A = \{5^i \mid i ∈ Z+\}$. Prove that $A ⊆ S$ by ...
0
votes
1answer
44 views

Show that a 2-cycle is attracting.

How do I show that the 2-cycle {-1,0} is attracting for the function $F(x)=x^2-1$ The textbook says that an attracting point is one that has an interval around it in which $F^n(x)$ converges to it. ...
0
votes
1answer
8 views

Prove that {$y_1$,$y_2$} is a 2-cycle for $F(x)$

Prove that if F(x) is continuous and $F^n(x_0)$ converges to $y_1$ for n even and $y_2$ for n odd then {$y_1$,$y_2$} is a 2-cycle for F(x). note: $F^n(x_0)$ means applying the function $F(x)$ $n$ ...
2
votes
2answers
58 views

What is $x^2$-1 applied n times

For the function $F(x)=x^2-1$. How do I write $F^n(x)$ ($F$ applied $n$ times) in terms of $x$?
0
votes
0answers
28 views

Trigonometric Recursive Formula

Show that $\cos(nθ) = f_{n}(\cosθ)$ for polynomials $f_{n}(x)$ satisfying $f_{n+1}(x) = 2xf_{n}(x) - f_{n−1}(x)$. Find all the roots of $f_{2}(x) + f_{3}(x) = 0$ and write them in the form ...
10
votes
2answers
218 views

How to prove this recursive sequence converges to $\sqrt 2$?

Let $a_0,a_1>0$ be given. Consider the recursive sequence $$a_{n+2}=\frac{1}{a_{n+1}}+\frac{1}{a_n}$$ Prove that $a_n\to\sqrt2$. I attempted to find a bound for $a_n$ but so far I have only got ...
0
votes
0answers
13 views

How to obtain edge set that containing the widest path from s to t by partitioning and searching?

The following is my algorithm for finding bottle-neck path by sub-ranges searching. Actually I just want to get the smallest set that containing the widest path from s to t. In the algorithm, ...
4
votes
0answers
67 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
1
vote
1answer
51 views

Derive a ϴ(1) formula for a Recurrence relation

I'm given a piece wise function with sequence $a_0$ $a_1$ etc $$a_n = \begin{cases}8 & n=0\\-7 & n=1\\25 & n=2\\7a_{(n-2)}+6a_{n-3} & otherwise\end{cases}$$ I'm asked to derive a ...
0
votes
0answers
42 views

Write Function as Composition (i.e. with “$\circ$”) with Summation Component Function

I wish to write the composition of several functions, e.g. $f(g(h(x,y)))$, using the function composition operator "$\circ$", e.g. $f\circ g\circ h$. The point is to clarify what the overall function ...
7
votes
5answers
183 views

How to get nth derivative of $e^{x^2/2}$

I want to calculate the nth derivative of $e^{x^2/2}$. It is as follow: $$ \frac{d}{dx} e^{x^2/2} = x e^{x^2/2} = P_1(x) e^{x^2/2} $$ $$ \frac{d^n}{dx^n} e^{x^2/2} = \frac{d}{dx} (P_{n-1}(x) ...
5
votes
1answer
68 views

How to deduce the recursive derivative formula of B-spline basis?

Description Let $\vec{U}=\{u_0,u_1,\ldots,u_m\}$ denotes a non-decreasing sequence of real numbers, i.e, $u_i\leq u_{i+1} \quad i=0,1,2\ldots m-1$. and the $i$-th B-spline basis function of ...
0
votes
1answer
21 views

Recursive to explicit formula from power function

I have a recursive formula of a method $f\left(a,b\right)$: $f\left(a,b\right) = \begin{cases} f\left(a,\lfloor \frac{b}{2} \rfloor\right) \cdot f\left(a,b-\lfloor \frac{b}{2} \rfloor\right) & ...
1
vote
2answers
82 views

Prove that no function exists from $\mathbb{N}$ to $\mathbb{N}$ such that $f(n) \gt f(n+1)$

The recursion theorem says that if we have a function called $G$ from $A \times \mathbb{N} \to A$ there exists a function called $f$ from $\mathbb{N} \to A$ such that $f(0)$ equals to one of the ...
0
votes
0answers
39 views

How to solve three recurrences dependent on each other?

Given $a$,$b$,$s$ and $y$. Let $U_0=s$, $V_0=0$ and $W_0=s$, and $U_{n+1}={s b ((1-2 y) V_{n}+2 y W_{n})}/\sqrt{(1-y) (U_{n}^2 a^2+V_{n}^2 b^2)+y W_{n}^2 b^2}$ $V_{n+1}=-s a U_{n} ...
0
votes
1answer
32 views

Classifying the solutions of the function $f(x)= \frac{1}{2}f(x-1)+\frac{1}{2}f(x+1)$

I found this question on a GRE practice exam. It is stated as follows. Let $f$ be a real-valued function defined on the set of integers and satisfying $f(x)= \frac{1}{2}f(x-1)+\frac{1}{2}f(x+1)$. ...
0
votes
2answers
64 views
0
votes
2answers
41 views

Finding a recurrence

I am trying to figure out a recurrence for these numbers: $f(1)=0$ $f(4)=16$ $f(16)=128$ $f(64)=768$ The base case is $f(1)=0$ the numbers inputed into f must be powers of 4. I am not sure what ...
0
votes
0answers
25 views

Verify that $f(n) = \dfrac{1}{n+1} \displaystyle{{2n}\choose{n}}$ is solution of the given function equation. [duplicate]

I was going through binary trees in C and came across the following number known as Catalan number which gives the number of possible trees. $$ F(n) = \dfrac{1}{n+1} \displaystyle{{2n}\choose{n}} $$ ...
2
votes
0answers
84 views

Solving recursions by calculating determinant of an infinite matrix

In this reference (pg. 4) and few others a specific parameter in a recursion formula is solved by setting the determinant of an infinite matrix to $0$. In this precise case we have $c_{n-1} - D_n c_n ...
0
votes
0answers
39 views

Tricky notation: Need help formulating an expression to define a recursive function involving substitutions

I'm having a difficult time trying to come up with an inductive definition for a function I'm calling $f_i(k)$ in terms of constants $\rho$, $d$, the $1 \times n$ vector $q$, and a $n \times n$ matrix ...
0
votes
3answers
72 views

Explicit formula for a recurrance relationship $A_n = A_{n-1} + 2n + 1$

$$a_n = a_{n-1} + 2n + 1 $$ $$ a_0 = 1 $$ $$ a_1 = 4 $$ $$ a_2 = 9 $$ I know the basics of how to use characteristic polynomials, but I'm not sure how the $2n$ would be represented in the ...
2
votes
2answers
77 views

The amount of times a number need to be squared rooted

Consider the following recursive function $f()$ def f(x,n=0): if x<2: return n return f(math.sqrt(x),n+1) $f(x)$ calculates the number of ...
0
votes
0answers
34 views

Modeling the minimum number of moves in the Tower of Hanoi problem. [Concrete Mathematics Textbook]

I read the other related question but it doesn't quite answer my question. "If Tn is the minimum number of moves for the Tower of Hanoi problem T0 + 1 = 1; Tn + 1 = 2Tn-1 Now if we let Un = Tn + ...
1
vote
0answers
25 views

recursion trees and big theta bounds

Draw recursion trees and use them to find big theta bounds on the solutions to the following recurrences. For each, assume that T(1) = 1 and that n is a power of the appropriate integer. ex) T(n) = ...
0
votes
1answer
74 views

Prove this complex inequality by mathematical induction [closed]

Define a sequence of numbers $S_n$ (for integers $n\ge0$) recursively as follows: $$S_n=\left\{\begin{array}{ll} 1& \text{ if }n = 0, \\ 2& \text{ if }n = 1, \\ 3& \text{ if }n = 2, \\ ...
0
votes
1answer
56 views

Definition by Recursion - Need for Rigour

Suppose you define the factorial $n!$ by \begin{align} \tag{1}0!&:=1,\\ \tag{2}(n+1)!&:=(n+1)n!. \end{align} Consider the following argument showing that $n!$ is a uniquely defined function. ...
0
votes
1answer
30 views

Equation involving recursive n:th-roots.

Inspired by this question, replacing square roots with $n$-roots: $$\sqrt[n]{X+\sqrt[n]{X+\sqrt[n]{X+ \dots}}} =\sqrt[n]{X\sqrt[n]{X\sqrt[n]{X \dots}}}$$ Then find the $X$ value?