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
2answers
51 views

Looking for the name of polynomials obtained as integrals over a simplex

I'm looking for the name of the following polynomials: $\mathrm{p}_1 = 1$ $\mathrm{p}_2 = x - \frac{1}{2}$ $\mathrm{p}_3 = \frac{1}{2} x^{2} - \frac{1}{2}x +\frac{1}{6}$ $\mathrm{p}_4 = \frac{1}{6} ...
0
votes
1answer
42 views

Is there an explicit formula for this recursive series of matrices

I want to get an efficient way of computing $P_k$ from $P_0$ that satisfies the following recursion: $P_k = FP_{k-1}F^T+Q$ Where $P_k$, $F$ and $Q$ are matrices ($Q$ is diagonal, if it changes ...
0
votes
2answers
37 views

Solving this recursion question

Text-only For the sequence $10,50,250,1250,\ldots$ Determine the first form $a$ and the common ratio $r$. Infer an explicit formula for this sequence. Write its recursive form. ...
1
vote
1answer
55 views

Most “simple” $\mu$-recursive function that is not primitive recursive

Maybe the most prominent example of a $\mu$-recursive function that is not primitive recursive is the Ackermann function. But writing it out as a $\mu$-recursive function ("breaking it all the way ...
3
votes
0answers
50 views

Can the principle of inclusion/exclusion be used to count elements in the intersection of a sequence of sets?

The principle of inclusion-exclusion (PIE) is often used to count the number of elements in a union of $n$ sets in terms of an alternating sum of their various intersections: $$ \left |\bigcup_{i \in ...
0
votes
0answers
35 views

Is there a closed form polynomial for this integral recursion?

While working on some statistical problems, I startet playing with integral recursions of the type $$p_{n+1}(x)=\int_a ^x \mathrm{d} y\; q(y)p_n(xy)$$ Here $q(y)$ and $p_0(x)$ are given polynomials, ...
3
votes
0answers
102 views

How can I convert a recursive equation to a non-recursion one? [duplicate]

While I am aware of several other similar question which have been asked in the past, my mathematical education only extends through calculus, making them beyond my comprehension, and I believe this ...
0
votes
2answers
29 views

Proving convergence of two recursion sequences related to each other

I have a question that I got troubled with and hope for some help. Let $p_n=(x_n,y_n)\in\mathbb{R}^2$ be a sequence of vectors. It is given that $p_1=(1,0)$ and the following ...
0
votes
1answer
55 views

Proving that a recursive sequence converges

The sequence is defined as $ x_{n} = \sum_{k=1}^{n} \frac{1}{3^{k}} $ I have re-written the sequence like so: $x_{1} = \frac{1}{3} $ and $ x_{n} = \frac{1}{3^{n}} + x_{n-1}$ Now it's easier to ...
1
vote
1answer
47 views

How to solve this multivariable recursion?

How to solve this multivariate recursion?: $$a(m, n, k) = 2a(m-1, n-1, k-1) + a(m-1, n-1, k) + a(m-1, n, k-1) + a(m, n-1, k-1)$$ where $m, n, k$ are positive integers. Edit: $a(0,0,0) = a(1,0,0) = ...
2
votes
3answers
232 views

Probability of knocking off all of a dragon's heads

You are fighting a dragon with three heads. Each time you swing at the dragon, you have a $20\%$ of hitting off two heads, a $60\%$ chance of hitting off one head and a $20\%$ of missing ...
8
votes
5answers
146 views

Number of sequences of $0$s, $1$s, and $2$s with length $n$ such that there is a $0$ somewhere between every pair of $2$s

Let $a(n)$ be the number of sequences with length $n$ which consists the digits $0,1,2$ such that between every two occurrences of $2$ there is an occurrence of $0$ (not necessarily next to the ...
10
votes
1answer
106 views

Is there a name for the recursive incenter of the contact triangle?

Recently, I became aware that there are many more triangle centers than the four I learned about in school. This reminded me of a thought I had when I first learned about the incenter: what point ...
1
vote
1answer
47 views

induction, recursive function, discrete mathematics

Please help solve following recursive function. How can I solve $n-10$ for $M(99)$ or $M(98)$ if $n>100$ ? : Find $M(99), M(100)$, and $M(98)$ when $$ M(n) = \begin{cases} n-10, & ...
2
votes
1answer
80 views

How to explain recursion and iteration?

How to explain recursion and iteration to someone without using formulas or single line of code? Difference betwen them, why to use one over another? (a.k.a : How to explain recursion and iteration ...
0
votes
1answer
76 views

Convergence and limit of Muller sequence

The Muller sequence is given by the recursive definition: $U(n+1)=111-\frac{1130}{U(n)}+\frac{3000}{U(n)U(n-1)}$ with $U(0)=5.5$ and $U(1)=\frac{61}{11}$. This sequence is interesting in ...
1
vote
1answer
39 views

Find the general formula of this sequence

Here is the sequence 1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36 36 46 46 60 60 ··· I just know the recursion formula:$\displaystyle ...
3
votes
0answers
57 views

Relation between 2 recurrence equations. [duplicate]

I am stuck with the following recurrence relations (actually asked in a programming question).Given the following relationships, is it possible to find the index of the occurrence of any given number ...
1
vote
2answers
56 views

8th positive odd integer that is an ODD Catalan number? [closed]

The $n^{\text{th}}$ Catalan number is given by the formula $C_n = \frac 1{n+1}\binom{2n}n$. It also satisfies the recurence \begin{align*}C_n &=\sum_{k=0}^{n-1}C_kC_{n-1-k}\\ &= ...
1
vote
1answer
78 views

How to approach an equation of the form $f(x)=y$ where $f$ is recursively defined? [duplicate]

This is a homework problem so I am not looking for someone to solve it for me. I would like to know how I should approach this problem, or in what direction I should research to figure it out myself. ...
2
votes
4answers
55 views

General Solution for a non-Homogeneous Recurrence

What is the general solution to the recurrence: $$x(n + 2) = x(n + 1) + x(n) + n - 1$$ where $n\geq 1$ with $x(1) = 0, x(2) = 1$? It's a question on a practice exam I'm reviewing and I'm not ...
2
votes
1answer
34 views

Recursive functions.

If you have a recursive function $$g(x) = f(f(x))$$ and you know that $$f(0) = 0, f'(0) = 1, f''(0) = 2$$ Will then $$g(0) = 0, g'(0) = 1, g''(0) = 2$$ ?
0
votes
1answer
49 views

Express recurrence in closed form

I am having trouble understanding the process of expressing the following recurrence in its' closed form. First of all, I do not really understand what "closed form" means. If someone could elaborate ...
0
votes
3answers
28 views

Proof for result of sum of 3 elements of recursive sequence

I have a recursive sequence: $$a_1=1\\a_2=1\\a_3=-1\\a_k=a_{k-1}\cdot a_{k-3} (for\,k>3)$$ So this sequence has cycle of 7: $1,1,-1,-1,-1,1,-1$ And I have to calc $a_{2013} + a_{2014} - ...
1
vote
1answer
25 views

Proof by induction for a recursive function f

Consider the function $\operatorname{f}: \Bbb N \to \Bbb N$ defined recursively as follows: 1) Base case: $\operatorname{f}(0) = 0$ 2) Recursive case: $\operatorname{f}(x) = ...
0
votes
1answer
68 views

How can I find the order of growth of this recurrence: $T(n) =\sqrt{n}T\bigl(\sqrt{n}\bigr) + n$

I am trying to find the order of growth ($O(n)$, $O(n\log n)$) of the recurrence $T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + n$. I started to unroll the recurrence and found that I can rewrite it ...
0
votes
1answer
51 views

Matlab Recursion Loop

I need to create a loop to answer part c of the following linear algebra question. I'm new to Matlab so this is extremely confusing. I'm not sure how to make a loop that "counts" from 0-25 in order to ...
0
votes
1answer
35 views

Proof by induction for a recursive function

Really having a tough time doing this question: Consider the function $\operatorname{f}: \Bbb N \to \Bbb N$ defined recursively as follows: 1) Base case: $\operatorname{f}(0) = 0$ 2) Recursive ...
0
votes
0answers
17 views

largest number of regions formed by a certain amount of planes recursion question

The question: What is the largest number of regions formed by $6$ planes in space? I answered a similar question to this and it said "What is the largest number of regions formed by $6$ LINES in ...
1
vote
1answer
61 views

$T(n) = \sqrt n\,T(\sqrt n) + n\log n$

i tried to solve this recursion equation with master theory, and its not working in this way. How many arrays exist in each steo in recursion tree? And how can i solve this problem with another way? ...
0
votes
0answers
16 views

QBF - space complexity in detail

As I'm new to the "complexity theory" stuff I've some trouble with proofs which are "obvious" regarding all books I've found so far. In this case I want some evidence why a certain algorithm has space ...
0
votes
0answers
11 views

Dinamic programming for sum of two largest values from a Uniform parent

I must find a recursion formula to find the sum of two largest values from a Uniform parent [0,1]. I need dinamic programming but I don't know how to organize it.
0
votes
3answers
63 views

Constructing a recursive sequence that converges to sqrt 17

One of the problems that we have for abstract math is the following: Using the recursive sequence definition, construct a sequence that converges to $\sqrt{17}$. It is my understanding that the ...
2
votes
1answer
41 views

How to solve a recursively defined system

It has been a while since I have tackled a problem like this and could use a refresher. I have a recursive system of equations that looks a little like: Where the initial x & y values are ...
3
votes
1answer
130 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-219}-64a_{n-3}+k $$
0
votes
1answer
20 views

Log property in proof of Master theorem

The family of recurrence considered is of the form $$ T(n) = aT(n/b) + n^c $$ $a,b,c$ are integers. One case of master theorem states: if $c< log_b a$, then $T(n) = \Theta(n^{log_b a}) $. I have ...
1
vote
2answers
30 views

Is there solution for equation which is recursive?

I have this following vector equation:$$\vec x = \vec x_0 + (1/2) * f(\vec x, t)t^2$$ where $\vec x$ has initial value when first fed into function $f$. All vectors are 3 dimensional and function $f$ ...
3
votes
2answers
118 views

Finding the convergent value of a recursion similar to Arithmetic-Geometric Mean recursion

The sequence is defined as follows : Start : $(x_0,y_0)$ with $ 0 < x_0 < y_0 $ Step : $x_{n+1} = \frac {x_n+y_n} {2}$ , $y_{n+1}= \sqrt{x_{n+1}y_n} $ Find $\lim_{n\to \infty}(x_n,y_n)$ . ...
0
votes
1answer
40 views

Solution of recurrence

I need some explanations at the proof of the following theorem. Theorem: Let $a$, $b$ and $c$ be nonnegative constants. The solution to the recurrence $$T(n)=\left\{\begin{matrix} b & ,\text{ ...
3
votes
1answer
47 views

A general or simple method to solve this iterative/recursive problem?

I have the following iteration $$ y_n\mapsto n\sum_{m=1}^{n+1}y_m $$ starting with $y_1$ being a positive real number. Is there a standard method to find the coeffcients of all $y_n$ after ...
1
vote
1answer
25 views

Find a closed form equation of the following sequence: ${0,0,-2,0,4,0,-6,…}$

Find a closed form equation of the following sequence: ${{0,0,-2,0,4,0,-6,...}}$ I know $1+-1^n$ = 0 if n is odd and 1 if n is even. However finding alternating signs when plugging in only even ...
4
votes
1answer
68 views

Proving $V=V_{\sf On}$ in $\sf Z+Reg$

Define the function $$V_0=\emptyset,\qquad V_{\alpha+1}={\cal P}(V_\alpha),\qquad V_{\delta}=\bigcup_{\beta<\delta}V_\beta.$$ Since we are working in $\sf Z$ (i.e. $\sf ZF$ without the axiom of ...
5
votes
1answer
33 views

Conditional iterations constant.

Let $f(0)=2.$ Define for positive integers $n$ : $f(n+1) = \frac{3}{2} f(n)$ if $f(n)$ is even. $f(n+1) = \frac{3}{2}(f(n)+1)$ if $f(n)$ is odd. We now have $\lim_{n->\infty} \dfrac{4* (3/2)^{n} ...
0
votes
1answer
20 views

How can i find the complexity of this recurrence relation?

Basically i'm having this recurrence relation which i don't know how to get the complexity of it by using the iterative method $T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if ...
2
votes
2answers
124 views

Recursion on a class instead of a set

According to Wikipedia, the recursion theorem states the following: Let $X$ be a set, and $f:X\to X$ a function. For any $x\in X$, there exists a unique function $g:\omega\to X$ such that $g(0)=x$ ...
0
votes
0answers
31 views

Financial mathematics: asion option

I've got a forward starting asian call option: $V_N = max\left( 0,\left(\sum_{j=m+1}^{N}{S_j} - K \right) \right) $ So the payoff is determined by the average stockprice over de latest N-m days and ...
0
votes
1answer
37 views

Solution to recursion equation

Solve the recursive equation $$ T(n) = T(n-1) * T(n-2) $$ with $T(1) = a$, $T(2) = b$ How do I solve this algebraically? I unrolled the recursion and got a solution of $a^{f_n}b^{f_{n+1}}$, ...
0
votes
1answer
82 views

How to find explicit formula using backwards iteration

For this problem I tried to solve it by iterating downward so: an = an-1 - n an-1 = 2*(2an-2 - (n-1)) - n = 4an-2 - 3n + 2 an-2 = 2*(4an-3 - 3n + 2) - n = 8an-3 - 7n + 4 an-3 = 2*(8an-4 - 7n + ...
-1
votes
1answer
26 views

How to prove that if $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$ then $T(n)=O(n^2)$

I have this recursion relation: $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$. How do I show that: $T(n)=O(n^2)$ Thank you!! (P.S. I hope it's OK to ask it, but I'm looking for the simple ...
2
votes
1answer
39 views

Ways of defining a recursive function that counts right-parenthesis in a string

I'm trying to find a more elegant way of defining a recursive function on $\{(,)\}$ that counts right-parenthesis in a string. Let r be a function on $\{(,)\}$ defined recursively so that: ...