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

Recursive formula for mathematical expression

Assume that $\alpha , n,\lambda \in \mathbb{N}$,and $f$,$g$ two real valued functions defined on $\mathbb{N}$. Function $W$ is given by the following formula. \begin{equation} W(n) = \max_{1 \leq ...
1
vote
0answers
46 views

Solving a polynomial for cyclic roots

For any complex value of c, the following polynomial has 6 complex root values of p: $$1+c+2 c^2+c^3+p+2 c p+c^2 p+p^2+3 c p^2+3 c^2 p^2+p^3+2 c p^3+p^4+3 c p^4+p^5+p^6$$ For a general 6th order ...
1
vote
1answer
45 views

Recursion for strings.

Write a recursive procedure to compute the number of strings from $\{A, C, T, G\}$ of length $n$ that do not have $2$ consecutive $A$’s.
0
votes
4answers
66 views

Explicit formula for $e_k = 4e_{k-1} + 5$

The sequence looks like this: $e_0 = 2$ $e_1 = 4(e_{1-1}) + 5 = 13$ $e_2 = 4(e_{2-1}) + 5 = 57$ $e_3 = 4(e_{3-1}) + 5 = 233$ $e_4 = 4(e_{4-1}) + 5 = 937$ How would I go about finding the ...
0
votes
0answers
9 views

Finding the Primitive Recursive Function for the Rem Function

When trying to show the remainder function is a primitive recursive function as defined to be as below (Copied from Proof Wiki): $\operatorname{rem} \left({n, m}\right) = \begin{cases} 0 & : ...
1
vote
2answers
82 views

Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this ...
1
vote
1answer
37 views

Give a recursion for the number h(n) of strings in S of length n.

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring. Solving this I got: $$ h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14 $. When I did ...
0
votes
0answers
8 views

Gaussian weighted intergal of Product of Gaussians

I'm trying to find a solution to the following function, My understanding is that the resultant function should still be a Gaussian, however I would like to define it as a linear function the ...
1
vote
1answer
39 views

Number of ways to choose $k$ subsets such that $ B_1 \cap B_2 \cap \cdot \cdot \cdot \cap B_k = \emptyset$.

Let $ \space n,k \in \mathbb Z \space $ such that $1 \le k \le n \space$. Let $\space A=\{1,2,...,n\}$. Find the number of ways to choose $k$ subsets $\space B_1,B_2,...,B_k\space $ of $A$ such that $ ...
0
votes
1answer
91 views

Recursion Theorem question

I am trying to prove the following in Enderton's text 'Elements of Set Theory' (exercise 8 of chapter 4): Let $f$ be a one-to-one function from $A$ into $A$, and assume that $c \in A - ran \ f$. ...
5
votes
7answers
151 views

Convergence of the recursive sequence $a_{n+1}=\sqrt{2-a_n}$

I'm attempting to prove the convergence (or divergence, though I strongly suspect it converges) of a sequence defined as $a_{n+1}=\sqrt{2-a_n}$ with $a_1=\sqrt{2}$. I cannot use the monotonic ...
16
votes
4answers
564 views

Find all bijections $\,\,f:[0,1]\rightarrow[0,1],\,$ which satisfy $\,\,f\big(2x-f(x)\big)=x$.

A friend of mine gave me the following problem: Find all functions $f:[0,1]\to[0,1]$, which are one-to-one and onto and satisfy the following functional relation: $$ f\big(2x-f(x)\big)=x, \tag{1} $$ ...
0
votes
0answers
26 views

Solve the Recurrence Relation to Get a Theta Bound

If I have $T(n)=T(n-5)+n$, how would I go about using induction to find a $\Theta$ bound for this. I was able to use a tree method to get that the bounds should be about $\frac{n^2}{5}$, but I am ...
0
votes
2answers
31 views

Recursive formula to 3x3 matrix

I was given a recursive formula and I need to convert it into a $3\times3$ matrix. What is a general formula to do this? My recursion is in the form: $$R_{n+2} = 4R_{n+1} + 5R_n + 2R_{n-1}$$ Just ...
0
votes
0answers
34 views
0
votes
2answers
42 views

solve recursion $T(n) = T(\alpha n)+T(\beta n)+\gamma n$

I need solve this recursion: $$T(n) = T(\alpha n)+T(\beta n)+\gamma n$$ I know that for $\alpha +\beta< 1$ solution is $O(n)$ How is for $\alpha + \beta = 1$ and $\alpha + \beta > 1$?
0
votes
0answers
16 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
0answers
23 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
0
votes
1answer
34 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
1answer
17 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $t_n = 2nt_{n-1}$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
1
vote
1answer
24 views

Recursive formula for word problem.

I'm having problems with this recursion problem: Ann wants to buy along several weeks one dressing item which can be of two kinds: small ones -- hats and scarfs, and big ones -- dresses, suits, gowns ...
1
vote
1answer
47 views

How do you go about solving this recurrence?

How do you make an estimation for the substitution method, when the recursion tree did not help so much? I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence ...
0
votes
1answer
25 views

Can we solve this recurrence relation using recursion tree method

The recurrence relation is given as follows: $T(n) = 2T(\sqrt{n})+1$ $T(1) = 1$ I tried to solve it with recursion tree as follows: But to find the number of levels that may occur, I have to ...
1
vote
1answer
46 views

Recursive definitions in formal logic

A binary tree $T$ is either A single vertex, or A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree. Suppose ...
0
votes
1answer
16 views

String recursive definition corner case

I need your assistance with a corner case of this problem: Find a recursive definition for the strings of odd length that start with "a" and end with "b" over the alphabet $\Sigma$={a,b}. I've ...
0
votes
1answer
401 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
0
votes
0answers
16 views

recursion over $\arg \max$ function

I want to find a recursive/incremental update of the following equation: $\qquad d^{(n)} = \arg \max_{d=0:\,D-1} (s \cdot d + \sum_{i=1}^{N} f(x_i,d))$ where $d^{(n)}$ is the dimension number, $s$ ...
1
vote
2answers
45 views

Can the Recursion Theorem be proved in Peano Arithmetic?

A recursive function on $\mathbb{N}$ can be defined as follows: Given an element $a \in \mathbb{N}$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we can define a function ...
2
votes
0answers
13 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
3
votes
2answers
42 views

How many tilings are there?

In the $n$-cell below, we are to tile it completely with cells of the form $\boxdot$ and $\boxtimes \hspace{-0.45 mm}\boxtimes$. How many tilings are possible for a $12$-cell? Let $H_n$ ...
2
votes
0answers
61 views

Closed form of $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $

Given the sequence $a_1 = 1$ and $a_2 = 1 $ with: $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $ Does there exist a closed form computing $a_n$ ? At the moment I have a problem getting a grip on the ...
0
votes
1answer
38 views

How to solve the recurrence relation $T(n)=aT(n-1)+bn^c$ with $T(1)=1$

How to solve this recurrence relation? $ T(n)=aT(n-1)+bn^c \\T(1)=1,$ where a, b, c are constant. I want to solve it using generating function, but get stuck. Could anybody help me?
4
votes
4answers
379 views

Proving convergence of a sequence

Let the following recursively defined sequence: $a_{n+1}=\frac{1}{2} a_n +2,$ $a_1=\dfrac{1}{2}$. Prove that $a_n$ converges to 4 by subtracting 4 from both sides. When I do that, I get: ...
2
votes
3answers
51 views

How can one solve the tower of hanoi problem if there are discs of similar width in it?

For example a line with '1111' represents a disc with diameter of length 4. Similarly a line with '111' represents a disc with diameter of length 3. Below is the representation of a tower that has 5 ...
1
vote
1answer
104 views

Free Gliders for Everyone?

According to Feynman's Lecture on Computation (Problem 5.1, p. 148 ) you can extract $E=kTN\log 2$ out of two copies of a random $N$ bit random tape. From this we can conclude that it takes the same ...
0
votes
1answer
29 views

Proving that a certain function is not recursive

Consider the set $R_0=\{+,\cdot,I_<\}$, where $I_<$ is the characteristic function of the 2-ary relation $<$, and for every n let $R_{n+1}=\{p^n_1,...,p^n_n\}\cup R_n\cup C_n$, where ...
0
votes
1answer
20 views

Amount of times method is called in recursion

This is kind of a basic question, but its busting my head and I cant seem to grasp it. I know that when a recursive function (e.g: rec(int n)) is called recursively ...
0
votes
0answers
34 views

Rate of Convergence of $x_{k+1} = \frac 14 (x_k^2 +sin(x_k) + 1)$

I have shown that the fix point Iteration $$x_{k+1} = \frac 14 (x_k^2 +\sin(x_k) + 1)$$ has exactly one fix point $x^*\in[0,1]$ for every $x_0 \in [0,1]$ with the Banach theorem. Now I want to find ...
0
votes
0answers
70 views

Upper bound on successive difference inequalities

I would like to know tight upper bounds of the following equations perhaps some might have telescopic sum which can result in very tight bound.In the following equations assume $B\geq a_i \geq ...
1
vote
1answer
24 views

Order of growth of sequence $f_{n} = 2f_{n-1} + f_{n-2}$

I'm currently stuck with the following problem. How do I calculate the order of growth of the following sequence: $f_{n} = 2f_{n-1} + f_{n-2}$ Assuming that $f_{0} =1$ and $f_{1} = 1$ I've got ...
0
votes
0answers
20 views

The graph of Ackermman function is primitive recursive

For a relation $ R ⊆ ℕ^n $, define the characteristic function $ χ :ℕ^n → ℕ $ such that $ χ(x_1, x_2,..., x_n)=1 $, if $ (x_1,...,x_n) ∈R, χ(x_1,...,x_n)=0 $ otherwise. Say a relation is premitive ...
1
vote
1answer
33 views

How to solve this non-homogeneous recurrence?

I've made a few threads recently asking how to solve non-homogeneous recurrences and I think I've gotten the hang of it, but now I want to try a complicated thing like this: $T(n) = 4T(n-1) + 2T(n-2) ...
0
votes
1answer
24 views

How to solve non-homogeneous recurrences?

I am trying to find a way to solve non-homogeneous recurrences by solving the homogeneous and non-homogeneous parts separately. I can use generating functions for the whole thing, but I want to learn ...
3
votes
2answers
104 views

Is it possible to solve such a system?

I have the following two equations: $$P_t = \frac{t-1}{t}P_{t-1} + \frac{1}{t}Q_{t-1}$$ $$Q_t = \frac{1}{t} + \frac{t-1}{t}Q_{t-1} - \frac{1}{t}P_{t-1}$$ with $P_0 = 0$ and $Q_0 = 0$. As time goes ...
3
votes
2answers
129 views

Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ [closed]

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$. Is the attached picture the correct answer?
1
vote
0answers
28 views

How to solve even/odd divide-and-conquer problems?

I am looking into something called the Josephus problem, which seems to be popular, so I am sure there are lots of explanations online, but I want to do the work myself, but I do need a small push to ...
0
votes
1answer
168 views

A function f(n) satisfies the recurrence f(n)=4f(n/2)+n for real numbers. Give an upper bound for f(n)?

A function f(n) satisfies the recurrence f(n)=4*f(n/2)+n for real numbers. Give an upper bound for f(n)? I get somewhere T(n) = Θ(n^2), is that correct?
4
votes
2answers
214 views

HOW do you refactor a recursive function into a single equation

I have an initial equation which is very simple: answer1 = 0*2+2 But it is recursive such that: ...
0
votes
3answers
32 views

Compressing two recurrences

I have two recurrences $a_n = 9a_{n-1} + b_{n-1}$ $b_n = 9b_{n-1} + a_{n-1}$ Is there a way to combine these two so it's only in terms of $a_n$? $a_1 = 9, b_1 = 1$, if this information is needed.
1
vote
3answers
52 views

Show that the sequence $a_0 = 1$, $a_{n+1 }= \sqrt{2+a_n}$ is monotonically increasing

Given the sequence $a_0 = 1$, $a_{n+1}= \sqrt{2+a_n}$, how can I show that it is monotonically increasing? I need it to show, that the sequence converges. I already proved boundedness but I can't ...