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

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
143 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
288 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
54 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
53 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
45 views

Recursive Definition Math question [closed]

I am stuck on a math question: Let $A_n$ be the number of strings of length $n$ that have no two consecutive zeros. Thus $A_1 = 2$ and $A_2 = 3$ (strings 01, 10 and 11). Give recursive definitions ...
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
56 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
27 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
34 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
96 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
54 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
65 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
82 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
63 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
119 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
62 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
45 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
59 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
53 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
37 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
31 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
57 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
51 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
241 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
147 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
82 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
79 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
80 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
59 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
74 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
54 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
36 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 ...