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

Using Master Theorem to prove a recurrence with f(n) = Θ(n/logn)

I'm trying to use the master theorem to solve the recurrence: $$T(n) = 4T\left(\frac{n}{5}\right) + \Theta\left(\frac{n}{\log n}\right)$$ I'm having trouble understanding how the ...
1
vote
1answer
34 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 ...
0
votes
0answers
22 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
38 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 ...
0
votes
0answers
34 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 ...
5
votes
4answers
4k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
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
38 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
47 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 ...
1
vote
1answer
71 views

Reasoning about a recursive function

First of all, I am a computer science student, not a maths student. So maybe this is a trivial question, I just would like to understand it :) Suppose I have the following (pointless) recursive ...
2
votes
1answer
20 views

Recursion and Time Complexity Concept

The question prompt is as follows: Consider the function $f(n)$ defined as: $$f(n) = \begin{cases}n(n-1)f(n-2) & n > 1\\1 & n=0,\; n=1\end{cases}$$ How may be $g(n)$ be defined ...
2
votes
1answer
38 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: ...
3
votes
2answers
81 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
50 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. ...
15
votes
1answer
333 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
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
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 ...
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
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
30 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. ...
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
28 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, ...
1
vote
3answers
100 views

Proof by induction that recursive function $\text{take}$ satisfies $\text{take}(n) = 100 - 2n$

I'm sick and tired off posting threads about induction... I just can't seem to get it, I need someone to give me a detailed explanation and treat me like a 5 year old, literally. I'm wasting a lot of ...
8
votes
5answers
136 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 ...
2
votes
3answers
177 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 ...
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 ...
1
vote
1answer
37 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) = ...
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 ...
0
votes
4answers
102 views

How do I prove convergence of the recursive sequence $c_n = c_{n-1} + \frac{0.01}{n}$?

I have this sequence: $c_n = c_{n-1} + \frac{0.01}{n}, \ \ c_1 = 0.01$ How do I prove the convergence of this, and what is the limit? Context I was trying to solve the problem of a snail crawling ...
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 ...
6
votes
3answers
303 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: \[ g(1)=\alpha \] \[ g(2n+j)=3g(n)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \] I ...
1
vote
2answers
44 views

Relation between series and equations

There is following quotes from wiki on Plastic number: The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$. And 2nd is that ...
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
2answers
96 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)$ . ...
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}\\ &= ...
10
votes
3answers
800 views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = ...
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
43 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) = ...