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
1answer
30 views

Equation involving recursive n:th-roots.

Inspired by this question, replacing square roots with $n$-roots: $$\sqrt[n]{X+\sqrt[n]{X+\sqrt[n]{X+ \dots}}} =\sqrt[n]{X\sqrt[n]{X\sqrt[n]{X \dots}}}$$ Then find the $X$ value?
0
votes
0answers
28 views

Prove using structural induction that every member of the following recursively defined set $𝑆$ has a remainder of $1$ when divided by $5$

I am stuck, trying to prove using structural induction that every member of the following set has a remainder of $1$ when divided by $5$ $$1∈S$$ $$n∈S \to 5 + 1 \in S$$ $$n∈S \to n^2 \in S$$ Base ...
0
votes
2answers
34 views

Prove by induction of recursive sequence

My classmates and I were working on this question on our discrete mathematics homework, but we can't figure it out. We are asked to consider the following recurrence: \begin{equation*} G_0 = 0; G_1 = ...
0
votes
2answers
43 views

Closed-form representation of the following recursively defined sequence [closed]

Trying to find a closed-form representation of the following recursively defined sequence: $a_{0}=1, a_{1}=2, a_{n+2}= a_{n+1} +2a_{n}$. Afraid that I am a little out of my depth here, i know i can ...
0
votes
1answer
13 views

Linear Algebra Algorithm for Large Scale Equations

I was wondering how the following solution was proposed for the following system of equations: $x_1$ = 1, $x_i$ = 1 - $(4x_{i-1})^{-1}$ For the following system of equations: $x_1$ + $0.5x_2$ = ...
0
votes
0answers
49 views

Help unrolling a recursive function

I want to calculate a recursive function $$f : \Bbb{Z} \times \Bbb{Z} \rightarrow \Bbb{Z}$$ $$f(n, m) = f(n,m-1) + f(\lfloor n/m \rfloor,\lfloor n/m \rfloor - 1) + \textrm{other non-recursive stuff}$$ ...
1
vote
2answers
45 views

Recursive algorithms for string operations

I am trying to write recursive algorithms for the following string operations: 1) An algorithm to reverse a string. 2) An algorithm to test if two strings are equal to each other. 3) An algorithm ...
1
vote
2answers
54 views

Generalization of recursive formula

Ok, here is the problem, I have formula: $a_n=a_{n-1}+2^{n-4}-a_{n-4}$ with initial variables $a_0=0$, $a_1=0$,$a_2=0$ and $a_3=1$ If not for $2^{n-4}$ member in recursion, I probably would manage to ...
3
votes
1answer
36 views

Proving the gcd of two integers expressed as recursive statements

I have the following problem: Let $a$, $b$ be positive integers and $(x_{n})_{n\geq 0}$ be a sequence of integers defined by the following formulas: $x_{0}=0$, $x_{1}=a$, $x_{n}=x_{n-2}+bx_{n-1}$ ...
0
votes
0answers
30 views

Closed form for a recursive equation that include the ceiling function

Can someone help me with finding the closed form of g(n) in terms of n, A, and B? g(n<0)=0 ; g(0)=0 ; g(1)=0 ; g(n) = A + g(n-1) - ceiling[g(n-1)/B] , n>=2 , A and B are Natural numbers, ...
1
vote
2answers
96 views

How can I solve this recursive function $f(n) = f(f(n+1))$?

I am trying to solve this: $$ f(n) = \begin{cases} n - 1,& n > 5\\ f(f(n+1)),& n\leqslant 5 \end{cases} $$ What is the technical name of this kind of function ? --> ...
0
votes
0answers
50 views

How do I Convert a Recursive Formula with a quadratic into a Explicit Equation?

I have this recursive formula $U_0=2$ $U_n=U_{n-1}^2+1$ How do I convert it into an explicit one?
2
votes
1answer
41 views

Solving recurrence relation using unrolling

I'm having a lot of trouble trying to solve a basic recurrence relation. $T(n) = 3T(n-5)$ T(x)= 1 for x<= 5 I feel like this problem could be solved by simply plugging in for T(n-5) in terms of ...
1
vote
0answers
43 views

Proving that for $F_k = F_{k-1} + F_{k-2}$, $F_k$ is even iff $3|k$

Consider the recursion $F_k = F_{k-1} + F_{k-2},$ $ k\geq 2,$ $F_0 = 0$ and $F_1 = 1$, then show that $F_k$ is even iff $3|k$ I tried to do a proof by induction: The statement is true for base ...
1
vote
1answer
35 views

Finding permutations recursively.See constraints below

Problem: Let $P(n)$ be the number of permutations of $m$ letters taken $n$ at a time with repetitions but no $3$ consecutive letters being the same. Find a recurrence relation connecting $P(n)$, ...
7
votes
1answer
84 views

Functional equation: Show $0\le f(n+1)-f(n)\le 1$ and find all $n$ such that $f(n)=1025$.

The function $f:\mathbb{N}\to \mathbb{R}$ satisfies all of $$\begin{align}f(1)&=1, \\ f(2)&=2,\\ f(n + 2) &= f(n + 2 − f(n + 1)) + f(n + 1 − f(n)) \tag{1} \end{align}$$ Show ...
4
votes
4answers
145 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 I'm ...
-1
votes
2answers
102 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
65 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
31 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
129 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 ...
1
vote
0answers
18 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
35 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
151 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
48 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
81 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) + ...
3
votes
1answer
39 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
57 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
43 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
25 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
21 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
56 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
29 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
33 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
63 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
63 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 ...
3
votes
3answers
67 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 ...
3
votes
1answer
124 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
99 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? ...
-1
votes
1answer
63 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
42 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
55 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
26 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 ...
3
votes
0answers
57 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
99 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
42 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 ...
3
votes
1answer
96 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
27 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
67 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
259 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 ...