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
12 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
24 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
48 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
34 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
59 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
17 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 ...
3
votes
1answer
44 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
34 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
33 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
96 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
87 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
15 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
53 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
239 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
36 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
25 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
27 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
52 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
44 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
54 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 ...
1
vote
3answers
66 views

A recursive sequence is defined by…

A sequence is defined recursively by $a_1=1$ and $a_{n+1} = 1 + \frac{1}{1+a_{n}}$. Find the first eight terms of the sequence $a_n$. What do you notice about the odd terms and the even terms? By ...
3
votes
0answers
103 views

uniform convergence in recursive function

Let $\varphi:[0,+\infty)\to \mathbb{R}$ an increasing continuous function that satisfies that $1/2\leq \varphi(x) <1$ for all $x>0$. Let $f_0:[0,+\infty)\to \mathbb{R}$ an increasing function ...
1
vote
1answer
85 views

Finding the limit of a recursively defined sequence (recurrence relation). Specifically and generally

Whilst reading Goldrei's Classic Set Theory, I have come across a recursively defined sequence $a_0=0, a_1=1, a_n=\frac{1}{2}\left(a_{n-1} + a_{n-2} \right) $ The first few terms of which are: $0, ...
1
vote
2answers
43 views

A non-homogeneous recurrence of Fibonacci sequence

I am working on Fibonacci sequence (recursively) But the hack is that I have the following non-homogeneous version: $$F_n =F_{n-1} +F_{n-2} +g(n)$$ Where: $F_1=g(1)$ $F_0=g(0)$ I have to use: ...
2
votes
3answers
88 views

Is there official notation to represent “perform an operation n times”?

I would like to know if you can represent the idea of say, $$n^n$$ n amount of times without defining a function. For example: $$1$$ $$2^2$$ $$3^{3^3}$$ $$4^{4^{4^4}}$$ $$5^{5^{5^{5^5}}}$$ and so ...
2
votes
1answer
42 views

How do I find an analytic solution to this recursive function?

I was playing with some recurrence relations, and I ended up with this a long nested function. How can I generalize the following relationship: $$ f_n = a + \frac{b}{f_{n-1}} $$ $$ f_1 = a + ...
1
vote
1answer
37 views

Reference for a proof of the recursion theorem, for a general case.

Herbert Enderton in his A Mathematical Introduction to Logic 2nd edition, proves a theorem (a "recursion theorem") in section 1.4, p. 39. Using his example, the idea is the following: We have some ...
1
vote
1answer
61 views

Universal languages are primitive recursive.

First of all, this are the definitions I am working with. Definitions: A language $L$ is $universal$ if it is countable, has infinitely many constants, and for each $n$, $1 \leq n$ has infinitely ...
0
votes
0answers
17 views

Name of this function

Is there a name for the following function? $f(x,y) = \begin{cases} y+1, & \text{if $x=0$} \\ f(x-1,1), & \text{if $y=0$} \\ f(x-1, f(x-1,y-1)), & \text{otherwise} \end{cases}$
1
vote
2answers
44 views

Prove that the following formula is true for $n \geq 1$ by induction

Prove that the following formula is true for $n \geq 1$ by induction. $a_{n} = a_{n-1} + 4n - 3 \\ a_{n} = 2n^{2} - n + 1 \\ a_{1} = 2$ My attempt follows below. I almost succeed in proving the ...
0
votes
2answers
31 views

Linear Recurrences

I was working on linear recurrence... But I am having trouble with it. $a_0 = 1; a_1 = 2; a_k = 4a_{k-1} - 2a_{k-2}$ I found $a_2$ which is $$4a_1 - 2 a_0=4\cdot2 - 2\cdot 1 = 6$$ I found $a_3$ ...
0
votes
2answers
61 views

A series with the recursive formula.

A sequence $\lbrace a_{n}\rbrace_{n\geq 0}$ is constructed by choosing a value of $a_{n}$, and then the following elements are determined from the equation $a_{n}=2-\frac{1}{2}a_{n-1}$ for ...
0
votes
0answers
44 views

Fourier transform and recursion

Starting with the first derivative of a continuous general function $u(x)$, say $\frac {du}{dx}$ and I take the Fourier Transform of it, I know the solution is $i\cdot k\cdot U$, where $ U$ is the ...
0
votes
2answers
29 views

How do I compute this recursive function efficiently? [closed]

Let $f(x,y) = xy + f(x-1,y-1) $ where $f$ equals $0$ if either $x$ or $y$ is $0$. Also $x,y$ belong to $\mathbb{N}$. Describe an efficient (less then $O(n)$) algorithm for computing $f(x,y)$.
0
votes
3answers
50 views

First order difference equation. Solve $u_{n+1}=3u_n+2$.

First order difference equation. Solve $u_{n+1}=3u_n+2$ with $u_0=0$ My notes are very sparse on this topic, so I need some help solving what should be an easy question. I would really appreciate ...
2
votes
1answer
45 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...