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

Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0)

Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0) which of the following is true? fib(n) is : Select one or more: a. O(n) b. O(n^2) c. O(2^n) d. ...
1
vote
3answers
42 views

Given that $f(n)=3f(n-1)-2f(n-2)$ for $n>1$ and given that $f(0)=0$, $f(1)=1$, what is $f(10)$?

I understand how to work out this question using brute force (manually substituting the numbers in) was just wondering if there was a faster and less tedious way of doing this question.
-2
votes
1answer
77 views

2010 local contest questions on recurrence relation?

How we can solve this recurrence relation: $T(n)= 2^{log_{2}3} T(n/2)+ n \sqrt {n} $ anyone could help me this difficult question, that mentioned in 2010 local contest?
-1
votes
2answers
209 views

one recurrence relation with generating function

what is generating function for {$a_n$}$_{n \geq 0} $ sequence that defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ $(n \geq 1)$. ...
0
votes
2answers
59 views

recurrence formula for number of decimal numbers with some restrictions

I ran into a Olympiad Question that so difficult, if $a_n$ be the number of decimal numbers with length $n$ that has no $0$ in the digits and also has not any combinations $11,12,21$, I want to find ...
0
votes
1answer
51 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
0
votes
0answers
19 views

Is this recursive?

I came across this formula in a neuroscience journal: $x = [sigma(y - z)] - w$ where: $z = a + \max(x)$ My question is, can you solve for $x$ if $x$ is a constituent of $z$?
3
votes
0answers
46 views

Conway's Game OF Life maximum periods on a set x by x game board.

I have taken interest in Conway's Game of Life and want to know if you guys can help me with a mathematical problem :) That is what this website is for right? You need to be familiar with the rules ...
0
votes
2answers
42 views

Recursion, Truncation, and “coding.”

The example is "left to the reader", but I am having trouble approaching this problem. There is a primitive recursive function $tr$ such that if $s$ codes a sequence $(a_{0},...,a_{n-1})$, and $m\le ...
0
votes
2answers
53 views

How to prove what amounts of postage can be formed with normal mathematical induction?

This is similar to my other question Strong induction but it addresses standard mathematical induction. Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 ...
3
votes
1answer
87 views

Does every positive rational number appear once and exactly once in the sequence $\{f^n(0)\}$ , where $f(x):=\frac1{2 \lfloor x \rfloor -x+1} $

Consider the map $f:\mathbb Q^+ \to \mathbb Q^+$ defined as $f(x):=\dfrac1{2 \lfloor x \rfloor -x+1} , \forall x \in \mathbb Q^+$ ; then is the function $g:\mathbb Z^+ \to \mathbb Q^+$ defined as ...
0
votes
0answers
11 views

Closed form of chained Stationary Functions

Consider the following operator $$D_{(a-1)x,x}\left[ f \right] = \frac{f(ax) - f(x)}{(a-1)x} $$ It's pretty easy to see that a nontrival function $g(x)$ such that $$D_{(a-1)x,x}[g] = g$$ Is given ...
1
vote
0answers
133 views

Proving a recursive algorithm as correct using induction

My objective is to give a recursive algorithm for finding the maximum of a finite set of integers, "making use of the fact that the maximum of n integers is the larger of the last integer in the list ...
1
vote
2answers
76 views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
0
votes
1answer
40 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 ...
2
votes
3answers
47 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
72 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
37 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
32 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
33 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?
0
votes
1answer
35 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
48 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
33 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
102 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
28 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
2answers
59 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
28 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
25 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
54 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
48 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
70 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
90 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
59 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
22 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
91 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
133 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
253 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
49 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
41 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
41 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
42 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
51 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
71 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
19 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
33 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
77 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
48 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 ...