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
10 views

Showing that a set is primitive recursive.

I've been having a lot of difficulty even beginning this problem. I believe that I would have to use the min and max functions, but I'm not entirely sure how to actually write this down rigorously, or ...
-1
votes
1answer
17 views

Recursive function for derangements

The principle of inclusion-exclusion is not the only approach available for counting derangements. We know that $d_1 = 0$ and $d_2 = > 1$. Using this initial information, it is possible to ...
2
votes
3answers
36 views

Turn iterative function into polynomial.

So, I have an iterative function that looks something like this. $$f(x_n) = (x_n + 0.08) \cdot 0.98$$ e.g. So if $n = 2$ and $x$ started at $0$, then the equation would be equal to $(((0 + 0.8) ...
1
vote
0answers
44 views

Probability of rolling n dice to match another set of dice, d, given r rolls (like yahtzee)

(Note: I will eventually code this, but i'm primarily interested in the math behind it) I'm trying to create a function in Java to calculate the probability of getting a desired outcome from n rolled ...
1
vote
0answers
33 views

Need clarification on recursive functions.

Given any function $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ and a recursive $h:\mathbb{N}_0 \rightarrow \mathbb{N}_0$ , I know that to prove $h\circ f$ is recursive I only need to prove that $f$ is ...
0
votes
0answers
28 views

Derive the recursion relation

Consider the nonhomogeneous linear equation $y' = 2y/(1-x) + f(x)$. It is singular at $x=1$, of course, but it is regular at $x=0$ if (the known function) $f(x)$ is analytic there. Assume $y(x) = ...
-1
votes
2answers
29 views

Solve this recursion [duplicate]

\begin{cases} T(1) = 1 \\ T(n) = 2T(n-1)-4 \end{cases} Solve this recursion using summation factor method or iterative method. Could someone solve for me this recursion and explain all steps?
3
votes
1answer
21 views

Iterative Logarithm in Recurrence Relation?

Anyone Could describe me How we can solve this recurrence relation? $T(n) = T(\log n) + O(1)$ $T(1) = 1$ a) $O(\log n)$ b) $ O (\log^* n) $ c) $ O (\log^2 n) $ d) $ O (n / \log n) $ Our TA ...
1
vote
1answer
24 views

Growth Rates of F(n) vs. F(n) + F(n-1) + … F(1)

I am trying to understand growth rates between a function and its sum recursively. For example I understand that if: $F(n) = n$ Then the sum $n + (n - 1) + ... 2 + 1 = \frac{n(n-1)}{2}$ which is ...
1
vote
1answer
45 views

What does Gödel mean by “constant” relating godel definition of recursion to the modern def.

In "On formally undecidable propositions..." he writes a function is recursive if "... it is a constant or the successor function" is he referring to the constant function c(x)=k, and if so, is this ...
0
votes
1answer
32 views

recursion relations, pattern finding

I have the following recursive relations: $$ \left \{ \begin{array}{ccc} x_{t+1} &=& x_t \cdot (1-2c) + 0.5 v_t\\ v_{t+1}&=& 0.5v_t - 2c\cdot x_t \end{array} \right. $$ $c$ is just ...
1
vote
1answer
89 views

Nested recursion theorem (problem 5.21, “Notes on set theory”, Y. Moschovakis)

I found this problem in the book "Notes on set theory" by Yiannis Moschovakis; it's the x5.21 from the fifth chapter. You have to prove the following theorem: for any three functions g: ...
0
votes
1answer
17 views

Motion of a particle; direction of motion depends on location

I'm wrestling with a problem involving motion of a particle. The direction of the particle's motion is defined everywhere by a function $\mathbf G(\mathbf X)$. I keep coming down to a recursive ...
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
3answers
55 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
26 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
24 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
45 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
41 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
62 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. ...
7
votes
2answers
74 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
53 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 ...
1
vote
1answer
17 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
85 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
123 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
221 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
26 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
35 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
33 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 ...
2
votes
1answer
33 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
41 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
42 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
65 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
12 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
28 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
58 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
43 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
56 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
27 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
60 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
46 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
87 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
52 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
41 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
42 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
32 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
49 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
41 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
32 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, ...