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

0
votes
0answers
6 views

Eliminating left recursio of a grammar

I would like to create a grammar in which each binary operation is represented by one parent node with 3 children (operand1 op operand2). However I´m creating the productions such as the other of ...
0
votes
0answers
13 views

Help Solve Recurrence Relation$ T(n) = T(n-1) + O(n)$

This is how far I have gotten: $$T(n) = T(n-1) + O(1)$$ $$T(n-2) = T(T(n-2)) + O(1)) + O(1)$$ $$T(n-2) = T(n-2) + O(2)$$ $$T(n-3) = T(T(n-3) + O(1)) + O(2)$$ $$T(n-3) = T(n-3) + O(3)$$ Finally ...
1
vote
0answers
13 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
0
votes
2answers
39 views

The powerset of the set of natural numbers - Cantor's Theorem

It is a fact that if $A$ is any set then there is no bijection between $A$ and its powerset $P(A)$. If $A$ is finite, this is pretty clear just by looking at the sizes of $A$ and $P(A)$. But if I ...
2
votes
1answer
53 views

Is recursion a type of iteration?

From what I understand, in simple terms, The definition of iteration : The act of repeating a process The definition of recursion : The act of repeating smaller process of the same problem It ...
-1
votes
0answers
37 views

How to solve this recursion for large values of n?

I am trying to solve a programming question for which I have figured out the recursion to be as follows: f(n) = f(n/2) + f(n/3) + f(n/4) where n/2 , n/3 and n/4 are integer divisions which are ...
0
votes
1answer
26 views

Lin Alg 100-Level Recursion Problem

I want to pave a $2\times n$ rectangle with $1\times 2$ blocks which come in two colours, white and grey. Let $w_n$ be the number of different ways this can be done. I determined the recursive ...
0
votes
0answers
46 views

In terms of addition, multiplication, exponentiation, tetration, what would be the natural continuation here?

Consider the by addition recursively defined table: $$t(n,1)=1$$ If $n>=k$ $$t(n,k)=\sum _{i=1}^{k-1} t(n-i,k-1)-\sum _{i=1}^{k-1} t(n-i,k)$$ else $$t(n,k)=0$$ Then consider the similar but by ...
0
votes
0answers
32 views

$T(n) = T(n/3) + T(2n/3) + cn$ - recursion tree with constance $c$

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac ...
3
votes
2answers
79 views

Proof by Iteration

It seems that I suffer the "too-much-logic-too-pedantic-too-confused"-disease. (You know? This very disease which lets you doubt everything and lets you yell for formalized proof. It's annoying, ...
0
votes
3answers
73 views

Prove by induction that $G(n)=2G(n-1)$ [closed]

I have a task to solve with algorithm, which is writing all the binary numbers. I wrote the recurrence relation below, as I count the few first values: $$G(n) = \begin{cases}1&\qquad n = 0\\ 2G(n ...
1
vote
2answers
49 views

How can I prove that two recursion equations are equivalent?

I have two recursion equations that seem to be equivalent. I need a method to show the equivalence relation between them. The equations calculate number of ones in binary representation of the number. ...
2
votes
1answer
35 views

find a function satisfying the recurrence [closed]

find a function satisfying the recurrence $$F (n) = 2F (\sqrt{n}) + 1$$ replace $n$ by $2^m$ Thus getting the answer as $$F(n)=\frac{1}{2}c \log(n) + \log(n) - 1$$ Is this correct
1
vote
2answers
41 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
29 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
36 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
32 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
37 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
27 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
101 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
22 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
43 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
36 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
176 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
135 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
93 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
44 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
70 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
69 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 ...
0
votes
1answer
34 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
40 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
77 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
41 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
23 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
42 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
27 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
21 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
45 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
24 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
29 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
12 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
45 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
7 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
7 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
60 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
40 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 ...
2
votes
1answer
118 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
16 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
25 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$ ...