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
1answer
24 views

Proofs related to counting the nodes of a recursive tree

Define Fibonacci numbers by $\text {Fib(n)} = \begin{cases} 0 & \text{if $n = 0$} \\[2ex] 1 & \text{if $n = 1$} \\[2ex] \text {Fib(n - 1) + Fib(n - 2)} & \text {otherwise} \end{cases}$ ...
0
votes
2answers
93 views

Finding the formula for nth term of a sequence

I have the following recursive sequence an i want to find the general formula for the nth term of a sequence: $$a_{n+2}=4a_{n+1}+4a_n,a_1=1,a_2=2$$ I have the following characteristic equation: ...
0
votes
2answers
33 views

Recursive sequences general term

Find general term for nth term of the sequence $$a_{n+2}=a_{n+1}+a_n+n^2, a_1=1, a_2=2$$ How to approach this type of questions? I am looking for a specific answer but also more general insight about ...
1
vote
3answers
39 views

Recursive relationships for ternary strings

If one were to have a ternary string with no repetition of consecutive $0$'s or $1$'s how would you define the recursive relation? The first way I tried to solve was to assume $2$ was the last digit ...
1
vote
1answer
73 views

Define recursive function prefix.

I need to define a recursive function, over strings, prefix in that way $\mathrm{prefix}(x,y) = \mathrm{true}$ if $x$ is prefix of $y$. This is my approach so far: $\mathrm{prefix}([ ],y) = ...
1
vote
2answers
59 views

Help proving a recursive formula involving planes and lines

Suppose that $n$ lines are drawn on a plane in such a way that no lines are parallel and no three of them intersect at a point. Let $r_n$ be the number of regions in the plane is divided into after ...
1
vote
1answer
73 views

Counting Regions when cutting a circle (recursion)

Let m≥1 and n≥1 be integers. Consider m horizontal lines and n non-horizontal lines such that no two of the non-horizontal lines are parallel, no three of the m+n lines intersect in one single point. ...
3
votes
2answers
103 views

$ T(n)= T(\log n)+ \mathcal O(1) $ Recurrence Relation

what is the solution of following recurrence relation? $$\begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end{align}$$ a) $O(log n)$ b) $ O (log^* n) $ c) $ O (log^2 n) $ d) $ ...
0
votes
1answer
64 views

How to prove a recurrence with multiple terms?

I have to prove that the recursion: $$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n $$ is $$ T(n) = Θ(n*\log n)$$ As you can see, the reccurence has two different terms that ...
0
votes
1answer
24 views

Computation Operation in one Recurrence Relation

We want to calculate $T(n)$ from recurrence relation $ T(n)= \Sigma_{i=1}^{n-1} T(i) \times T(i-1)$` and we know $T(0)=T(1)=2$. How many computation operation, an Efficient Algorithm needs for ...
5
votes
2answers
92 views

Prove function is Fibonacci sequence

Stuck on how to finish a question I'm working on. Have to find the number of bitstrings of length n with no odd length maximal runs of ones. For example, when n=3 there are three such bitsrings: 011, ...
-1
votes
2answers
146 views

Derive a recursive form of the function f(n) = 2n(n-6).

The Function f: N -> Z is defined by f(n) = 2n(n-6) , for each integer n >= 0. Derive a recursive form of this function f. Please help :[
2
votes
3answers
294 views

Recursive sequence. Need help finding limit.

This is my recursive sequence: $a_1=\frac{1}{4};\space a_{n+1}=a_n^2+\frac{1}{4}$ for $n\ge 1$ In order to check if this converges I think I have to show that 1) The sequence is monotone ...
0
votes
1answer
28 views

Recursive function with p=2/3 to call itself and 1/3 to return always ends?

So I was reading Godel, Escher, Bach and this problem came up: Let f(t) { 1)Generate random number k 2) if( k mod 3 = 0 or k mod 3 = 1 ) call f(t) //so 2/3's of the time, a new recursion level ...
1
vote
1answer
58 views

Proof of x-intersection of the Mandelbrot Set?

I'm trying to prove that the Mandelbrot set intersects the X-axis on the interval [-2,.25]. I understand and have proven that the Mandelbrot set lies in a radius of 2. Mostly, I'm wondering how to ...
1
vote
1answer
55 views

Discrete Math Recursive Definition

I am just unsure if I did this question right and would just like to check. Question: A bit-string is simply a finite sequence of zeroes and ones. For the purposes of this problem, strings will ...
1
vote
1answer
44 views

Sequences that can only be specified by recursion

As the title says, I wonder whether there are sequences that can only be specified by recursion. In other words, are there any sequences $a_k$ where there is no other way to calculate $a_n$ than ...
2
votes
1answer
59 views

Recursive Alegbraic Equation for binary trees? [duplicate]

Consider the number $b_h$ of binary trees of height $h$, where height is being measured by the number of levels. An empty tree has height $0$, a single node binary tree has height $1$, and there ...
0
votes
2answers
78 views

Possible distinct binary tree structures at depth d

I'm trying to figure out a recursive formula for the number of possible distinct binary trees at any depth d. I haven't been able to find any sort of sources on this. basically, at depth 0, the only ...
0
votes
0answers
28 views

Eliminating left recursion 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
38 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
1answer
102 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
55 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
66 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 ...
0
votes
1answer
28 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
86 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
68 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
123 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, ...
1
vote
2answers
65 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
60 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
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
46 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
62 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 ...
4
votes
0answers
56 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
38 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
34 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
59 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
55 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
248 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
149 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
110 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
86 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
80 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
58 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
82 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. ...