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

2
votes
3answers
60 views

Proving that all terms in sequence are positive integers (Recursive)

I am preparing for Putnam and working through practice-like questions and I am boggled. I've got the sequence defined by $a_1 = 1$ and $a_{n+1}$ = $2a_n+\sqrt{3a_n^2-2}$ for any $n\in\mathbb{N}$ and ...
-1
votes
2answers
56 views

Prove by induction and recursion that $n!=n(n-1)(n-2)…(3)(2)(1). $

Prove by induction and recursion that $n!=n(n-1)(n-2)...(3)(2)(1). $ We can start with the definition of factorial with recursion: $$n!= \left\{\begin{align}1\quad \text{for}\quad ...
1
vote
2answers
54 views

Explicit formula for recursive sequence.

Consider the series defined by $$P_n=(P_{n-1}-a)b\ .$$ $$P_0=c$$ Basically the number sequence $P_n$ represents the current Principal balance of a debt and constants $a$ and $b$ are constants or ...
1
vote
1answer
24 views

How to prove numerical formula about strings in context-free language?

Consider the the alphabet $\{0,1\}$ and the grammar $S\to 10,\, S\to 1SS0$. Define $P$ to be the set of all those strings and $P_n$ be the set of all strings in $P$ in which the substring $10$ occur ...
5
votes
1answer
49 views

From Primitive Recursive to Recursive by Iterating over more than one Argument?

Is the only way a function can be recursive and not primitive recursive by growing faster than primitive recursion allows (as with Ackerman's function)? If so, then consider the following. Primitive ...
0
votes
0answers
9 views

Solving systems of reccurence equations to get number of recursions to reach a stationarity point?

I'm tring to solve a system of recurrence equations to then formalize a formula depending on the number of recursions to calculate this number of recursions to reach the stationarity of the system ...
1
vote
1answer
31 views

Proof involving recursive enumerability

Consider the set $S = \{x : \phi^1_x(x) \ \ \text{is undefined/does not converge\} }$ This is supposed to be a set that is not recursively enumerable. How do we prove this? My thoughts so far: ...
3
votes
4answers
136 views

A set of certain lists - does it exist?

Define a placeholder to be either an empty list $()$ or a list $(p q)$ of two placeholders $p$ and $q$. Does it exist a set of all placeholders? Of all finite placeholders? My intention with ...
0
votes
0answers
46 views

Generalization to: n children at a round table swap places with their neighbors

$ n > 3 $ children occupy the places $ 0,..., n-1 $ mod $ (n) $ , so that every place is occupied by exactly 1 child. The original problem states: Now the children are allowed to swap places, ...
3
votes
1answer
43 views

Limit of recursive sequence involving factorial in sequence definition

I'm trying to calculate limit to this function and but I've not been able to figure out how to approach this. The definition of sequence $S$ is $S(1) = 3 $ And $ \forall \geq 2, S(n) = S(n-1) + ...
2
votes
1answer
25 views

Problem with Soare's book on re sets.

On page 16 of his "RE sets and degrees" he introduces the notion of a (Turing) computable function indexed by e with input x and output y taking fewer than s steps to complete, WHERE s has to be ...
0
votes
0answers
31 views

Recursion formula

I'm working on an exercise problem out of Algebra with Galois Theory by Emil Artin. I've arrived at the following recursion formula, $$ a_n = \sum_{i=1}^{n-1} a_ia_{n-i} $$ The hint in the book says ...
0
votes
2answers
39 views

Proving that this algorithm distributes a quantity as expected

Background (non-essential) Let $Q$ be an integer quantity (of say, marbles) to be distributed into $n$ buckets ($B_1$ ... $B_n$) according to weights. Let $w_1$ ... $w_n$ be the non-negative weights, ...
0
votes
0answers
16 views

probabilistic rbotics

we will apply Bayes rule to Gaussians. Suppose we are a mobile robot who lives on a long straight road. Our location x will simply be the position along this road. Now suppose that initially, we ...
1
vote
1answer
15 views

Generative method for reducing trigonometric argument coefficients to unity

Suppose I have a term $$f(\beta x) = C$$ where $\beta \in \mathbb{Z}^{+},\ f \in \{\sin,\cos\}$. And I want to find an algebraically equivalent sum $$\begin{align*}\sum_{i=1}^{n} K_i ...
1
vote
2answers
36 views

Give recursive definition of sequence $a_n = 2^n, n=2,3, 4… where $ $a_1 = 2$

Give recursive definition of sequence $a_n = 2^n, n = 2, 3, 4... where $ $a_1 = 2$ I'm just not sure how to approach these problems. Then it asks to give a def for: $a_n = n^2-3n, n = 0, 1, 2...$ ...
0
votes
1answer
19 views

Simple closed functional form for summed recurrence relation

I'm struggling to obtain a simple closed form for a summed recurrence relation. I have an overall form $y=A\left(n-\sum_i^n\frac{e^{-x_i}}{B}\right)$ where $x_{i+1}=kx_i+m$ with $A,B,m >1$ and ...
0
votes
2answers
27 views

Recurrence Relation solution

How do I solve the following recurrence relation and what kind is it ? $ a_n = a_{n-1} + c $ ? where c is constant Can this relation be considered non-homogenous as $ F(n) = c.n^0 $ ?
0
votes
1answer
55 views

A vessel contains $x$ amount of milk out of which $y$ amount is taken out and replaced with water $n$ times.

There is a formula in my book for questions of type, A vessel contains $x$ amount of milk out of which $y$ amount is taken out and replaced with water. After $n$ such operations what will be the ...
1
vote
1answer
36 views

How to come up with this recurrence relation for putting p rooks in a m×n chessboard?

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position. (Two rooks attack each other if they are in the same row or same column) How many ways ...
2
votes
3answers
63 views

How to solve recursive equations $F_{n+1} = F_{n} \cdot g + h$

Sorry if this is a duplicate or easy (a lot of the other 'how do i solve recursive equation' questions were for more complex equations). How can I solve this for arbitrary $F_n$ with arbitrary ...
2
votes
1answer
27 views

Minimum number of leaves in balanced binary tree

A balanced binary tree is a binary tree for which the difference in height between any node's two sub-trees is at most 1. (Such a tree is known as an AVL tree.) What is the minimum number of leaves ...
4
votes
1answer
51 views

Finding period of a recursive sequence defined by modular operator?

If $f(x)$ is defined as : $f(x)=i$ ,if $x\equiv i$ (mod n), $0\leq i< n$ How can I prove whether the following recursive sequences are periodic or not? ...
-2
votes
1answer
35 views

What does θ(1) means in this equation?

Hello I am trying to understand this recurrence equation with no success. $ T(n) = T(n / 2) + θ(1)$ Base case : $T(1) = θ(1)$ and the solution is $θ(log_2 n)$. ...
0
votes
1answer
34 views

Is there an algorithm to generate these specific sequences of numbers?

f(1) = [1] f(2) = [2,1,1] f(3) = [3,2,1,1,2,1,1] f(4) = [4,3,2,1,1,2,1,1,3,2,1,1,2,1,1] ... f(n) = ... The lengths of the lists f(n) are $2^n - 1$ (Mersenne ...
0
votes
1answer
15 views

Recursive definition of natural numbers

I'm doing the exercises in Algorithms and Data Structures in Java, Second Edition, by Adam Drozdek. One question is: The set of natural numbers $\mathbb{N}$ defined at the beginning of this ...
1
vote
1answer
20 views

More detailed explanation of how $2N_{h-2}$ becomes $2^{h/2}$?

I'm trying to learn the proof of the minimum number of nodes in an AVL tree of height h and I'm stumped on how $2N_{h-2}$ becomes $2^{h/2}$. I've read this [answer](How does $2N_{h-2}$ become ...
2
votes
0answers
52 views

What is the maximum amount of solutions to $f(x+1)f(x)= ax^2+bx+c$.

$f(x)$ is going to be in the form $mx+h$ thus, $(mx+m+h)(mx+h) = ax^2+bx+c$. With basic algebra $m= \pm \sqrt{a}$. Also $(m+h)(h)=c$. I would guess that because $(m+h)h=c$ has two solutions max if $m$ ...
1
vote
4answers
97 views

How do I solve following recursion

I have been trying to solve this $f(n) = 2 \cdot f(n-1) - f(n-2) + 2 \cdot k$ and failed , can anybody help ? $n>4$ The values of $ f(1) = a,\,f(2) = b,\, f(3) = c$ and $f(4) =d $ where $ ...
0
votes
1answer
38 views

Does the solution to $C_n = 2C_1 C_{n-1} - C_{n-2}$ can only be solved with $A = B = \frac{1}{2}$?

I was trying to solve the following recurrence in closed form (in terms of the initial conditions/base cases): $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ with base cases: $$ C_1 = C_1 $$ $$ C_2 = 2 C^2_1 ...
2
votes
1answer
88 views

How to calculate the $n$-th member of sequence $a_{n+1}=\sqrt{y+a_{n}}$

I was searching for a smooth continuous concave function $$f:R^{+}\times R^{+}\to R^{+}$$ so that $$f(x+1,y)=\sqrt{y+f(x,y)}\quad\text{and}\quad f(0,y)=0.$$ But I couldn't find a general function, ...
0
votes
1answer
16 views

Understanding recursive function for finding GCF of 2 numbers

So I get how this code works, but I don't understanding why it works. The function assumes input num1 > num2. Algorithms are hard for me to grasp, so please explain to me like I'm five. Heres the ...
1
vote
1answer
56 views

Find recursive formula - Question from exam, check my answer

We want to demolish and move a bridge from one location to another. The bridge is made out of $m$ road segments all connected $[0,1]$, $[1,2]$, $[2,3]$...$[m-1,m]$ We have a given function $f$ which ...
3
votes
2answers
242 views

Can the recurrence $C_n = 2 C_1 C_{n-1} - C_{n-2}$ be expressed in a closed expression?

I was wondering if the expression: $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ could be expressed as a closed expression in terms of (hopefully polynomials of) $C_1$ (or $C_2$). The bases cases for this ...
0
votes
1answer
12 views

Recursive formula for minimal editing distance - check my answer

Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are: 1) ...
2
votes
1answer
33 views

Find recursive formula for special function

Kind of a strange question I know, but here goes: We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid ...
2
votes
1answer
38 views

Why is $f(x)=x^{2}+1$ a primitive recursive function?

I'm trying to find out why $f:\mathbb{N}\rightarrow\mathbb{N},f(x)=x^{2}+1$ is a primitive recursive function. For $f(S(y))$ I can't seem to get it to fit the axioms known to me about primitive ...
0
votes
0answers
25 views

De-recursifyng a recursive sequence

I'm working on a recursive function for my IB Maths exploration, of the form $f(x)=f((x+a)^{-b})$ I've worked out a general formula for the n-th term of the sequence when $b = 1$, but whenever I'm ...
2
votes
4answers
48 views

Solve recurcion using generating function

I have got a problem with solving this equation using generating functions. $$ P_{n}=2nP_{n-1}-10n+5 $$ $$ P_{0}=5 $$ I started like that: $$ ...
0
votes
1answer
19 views

Solving a problem using the master theorem?

How can I solve this problem with master theorem. Giving asymptotic upper and lower bounds If $T(n)=4T(n/3)+ n log(n)$ a=4 b=3 k=1 for the formula $aT(n/b)+n^k log^b(n)$ if $a>b^k$ then ...
1
vote
1answer
26 views

Eliminating a summation

I need to approach the new position $(x_t,y_t)$ at moment $t$ of a moving object at $(x_0,y_0)$ given its horizontal velocity $vx_0$, its vertical velocity $vy_0$ and some constant resistance $r$ that ...
0
votes
2answers
31 views

Recursive equation in graph theory

How many vertex-colorings with 3 colors has the cycle $C_n$? How to build a recursive equation for the number of colorings over n? I know that a cycle has either 2 or 3 colors. 2 when n is even and ...
0
votes
0answers
13 views

Question about the effect of the basic primitive recursive projection function.

Projections are said to allow us to use "any argument in any order", and the function below can be proved to be a PR function by projections and the composition rule. Let $ i_0,\cdots,i_{m-1} \in n = ...
1
vote
1answer
58 views

What is the meaning of 'recursive' in Boolos, Burgess and Jeffreys? (Computability and Logic)

In the book Computability and Logic by Boolos, Burgess and Jeffrey (page 71 - 5th edition) it defines a recursive function as follows: The functions that can be obtained from the basic functions ...
2
votes
2answers
46 views

Solution to Fibonacci Recursion Equations

Let the sequence $(a_n)_{n\geq0}$ of the fibonacci numbers: $a_0 = a_1 = 1, a_{n+2} = a_{n+1} + a_n, n \geq 0$ Show that: i) $$a^2_n - a_{n+1}a_{n-1} = (-1)^n \text{ for }n\geq1$$ I try to show ...
0
votes
1answer
55 views

The result of substituting recursive total functions in a recursive relation.

In the book Computability and Logic by Boolos, Burgess and Jeffrey it defines a recursive function as follows: The functions that can be obtained from the basic functions $z, s, id^i_n$ by the ...
2
votes
1answer
32 views

How to calculate the limit of a recursively defined sequence?

My attempt: (i) For r=1, $x_n$ = n+1 $\iff$ $\frac{n+1}{1+1/n}$ = $x_{n-1}$ $\iff$ $\frac{n(n+1)}{n+1}$ = $x_{n-1}$ $\iff$ n = $x_{n-1}$ But I don't know how to use what I have shown so far to ...
2
votes
1answer
27 views

Can a polynomial equation always be manipulated to give a recurrence formula?

Let $p(x)$ be a real (or maybe complex) polynomial. Suppose we wish to (numerically) solve $p(x) = 0$. This can be done for example with Newton's method of course, but I was thinking about if you ...
0
votes
0answers
9 views

Upper bound for recursive formula

I have the following recursive formula: $F(n,m) = F(n-1,m) + (n-1) F(n-1,m-1)$ $F(n,1) = 2$ $F(2,m) = 2$ When $m \geq n-1$, then $F(n,m) = n!$ My question: Is there any simple (non-asymptotic) ...
1
vote
1answer
42 views

A linear recursion with power coefficient

In my research, I encounter a linear recursion of the form: $$a_n = (AB^n+C)a_{n-1}-AB^na_{n-2},$$ where $A,B,C$ are all positive (arbitrary) constants such that $B,C>1$. Is it possible to get a ...