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

1
vote
1answer
45 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
2answers
37 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 ...
4
votes
7answers
204 views

Convergence of $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
2answers
57 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
21 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 < 1$. ...
0
votes
0answers
32 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
67 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
2answers
26 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 = 2n~t_{n-1}$$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
2
votes
1answer
59 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 ...
2
votes
1answer
54 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
62 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
18 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
40 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
15 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
48 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
65 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 series:...
0
votes
1answer
41 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
17 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
77 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 $g:\mathbb{N}\...
1
vote
1answer
108 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
30 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 $p^n_k:\...
0
votes
1answer
22 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
35 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
75 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 0$,$\...
1
vote
1answer
29 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
49 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
37 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
30 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
110 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
vote
0answers
55 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
399 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
170 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
237 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
60 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
113 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 | \text{Dom}(\phi_i)...
2
votes
2answers
139 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
23 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 $k\in\{\...
2
votes
2answers
57 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
44 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
48 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 $l$...
10
votes
2answers
656 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
97 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
99 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 : http:/...
0
votes
1answer
72 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 (...
4
votes
2answers
95 views

Mathematically, how does one find the value of the Ackermann function in terms of n for a given m?

Looking at the Wikipedia page, there's the table of values for small function inputs. I understand how the values are calculated by looking at the table, and how it's easy to see that 5,13,29,61,125 ...
1
vote
2answers
54 views

Does an infinite iteration of a function still have my solution and why does it work?

I found the other day that you could find some solutions to an equation in the form $$f[f(x)]=x$$As a matter of fact, I found some solutions to$$f[f(f(\cdots f(x)\cdots))]=x$$ The solution, if one ...
3
votes
1answer
85 views

A little question about convergence of sequence

It's known that: $$\begin{cases}x_n=\sqrt[3]{6+x_{n-1}}\\x_1 = \sqrt[3]{6}\end{cases}$$ $$x_n\to2,\space x_n\uparrow,\space x_n\in(0, 2)$$ $$a_n=\frac{x_n^2+2x_n+4}{12}\space, a_n\to1,\space a_n\...
0
votes
2answers
117 views

Solve the functional equation $f (2x)=f (x)\cos x$

Find all $f: \mathbb R\longrightarrow \mathbb R $ such that $f $ is a continuous function at $0$ and satisfies $$\;\forall \:x \in \mathbb R,\; f\left(2x\right) = f\left(x\right)\cos x $$ My try: ...