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
22 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
29 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 ...
5
votes
7answers
141 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 ...
0
votes
0answers
32 views

Consider the recursion given by $f(n) = f(n-1) + f(n - 2)$ for $ n \ge 3$ with $f(1) = f(2) = 1$. [on hold]

Show that $f(n)$ is divisible by $3$ if and only if $n$ is divisible by $4$.
0
votes
2answers
41 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
13 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
20 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
29 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 ...
-3
votes
0answers
28 views

Recurrence / recursion [closed]

How to solve: A function F(n) satisfies the recurrence F(n) ≤ 4F(bn/2c) + n for all n ∈ N. Give an upper bound for F(n).
1
vote
1answer
45 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 ...
1
vote
1answer
43 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
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$ ...
0
votes
1answer
24 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 ...
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$ ...
0
votes
2answers
29 views

Proving with series $a_{n+1} = 3n + 1 - a_n$. [closed]

With series $a_{n+1} = 3n +1 - a_n$, prove that for any any natural $n$, $a_{n+2} = a_n + 3$. Any hints, clues? I don't have any idea how to begin.
2
votes
0answers
60 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?
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 ...
1
vote
2answers
43 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 ...
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
19 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
23 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
18 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
32 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 ...
-1
votes
0answers
24 views

Single element of nth power of a Matrix

I was recently solving a computational problem which had a recursive structure. With some help from the internet and a paper I found, I used mathematica to find a transformation matrix for the ...
1
vote
0answers
27 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
160 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?
3
votes
2answers
127 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?
4
votes
2answers
213 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 ...
1
vote
1answer
93 views

How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable. the set $A = \{ i | ...
2
votes
2answers
120 views

How to define $f(x) = 2x$ as a recursive and lamba function?

How can I exhibit a recursive function and a $\lambda$-term simulating the function $f : \mathbb{N} \rightarrow \mathbb{N}$, such that $f(x) = 2x$? For $\lambda$ part, I thought to create a mult ...
0
votes
0answers
18 views

Is the maximum value of this recursively defined function bounded?

If we define $$f_1(x)=x^\frac{1}{x}$$ $$f_{n+1}(x)=x^\frac{1}{f_n(x)}$$ Then what is the value of the following $$\lim_{k\to\infty} f_k \left( [f_k^\prime]^{-1}\left( 0\right)\right)$$ where ...
2
votes
2answers
45 views

number of ternary trees: finding a recurrent relationship

If $t_n$ is the number of ternary trees with n nodes, with $t_0=0$, what would be the convenient manner for finding a recurrent relationship for $t_n$? It is given that $t_1=1, t_2=3, t_3=12$. A ...
-1
votes
4answers
40 views

Can someone clarify step-by-step how to solve such Recursion & Induction question?

I've a discrete math exam coming up in two weeks and the only thing I've problem with is induction and recursion. I do know how to check the base case of a certain induction i.e. check and compare if ...
2
votes
0answers
43 views

Asymptotics of recursion

suppose we have the following two sequences $$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$ $$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$ where ...
10
votes
2answers
632 views

The set that only contains itself

Ignoring the axiom of regularity (and therefore the implication of "no set can contain itself"), would it be correct to state that the set that contains only itself is unique? My argument is that if ...
0
votes
2answers
91 views

Perplexing integral

First and foremost, is it possible to get the integral you are trying to solve as the solution? I just got the same integral twice. I have also tried MATLAB but it gives the same result. Below is the ...
0
votes
0answers
37 views

A particular recursion

Given $s_0=2^r>0$ let $s_i=\frac{s_{i-1}}{2^{\log^c{r_{i-1}}}}$ where $c\geq1$ and $r_{i+1}=\log_2(s_{i+1})=r_i-(\log_2(r_{i}))^c\leq r_{i}$. What is the value of smallest $i$ at which $s_i<1$ ...
0
votes
1answer
92 views

Formula to calculate directly $ 1 + 2 \cdot 3 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 \cdot 6 \cdot 7 + \dots + n \cdot (n+1) \cdot \dots \ (2n-1)$

Is it some formula to calculate $$ 1 + 2 \cdot 3 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 \cdot 6 \cdot 7 + \dots + n \cdot (n+1) \cdot \dots \ (2n-1)$$ for a given $n$ without iteration? comes from : ...
0
votes
1answer
67 views

How do I find a recurrence relation?

Let n1, n2, . . . , n100 be a sequence of integers. Initially, n1 = 1, n2 = −1 and all the other numbers are 0. After every second, we replace the kth term of the sequence with the sum of the kth and ...