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
38 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
73 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
107 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
48 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
106 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
53 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
398 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
230 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
59 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
138 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
96 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
87 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: ...
3
votes
1answer
43 views

Prove $A(x,y)= 2[x](y+3)-3$. Where A is the Ackermann-Peter function and [x] is x-th hyperoperator.

I've successfully proven $A(x,y)$ for some fixed x and any y with induction but I'm having a hard time proving this for any x and y. I think the next useful step would be proving $A(x,0)= 2[x]3-3 $ ...
0
votes
1answer
33 views

being explicit with recursion in a basic proof

related: induction (vs recursion) in proof I want to be explicit with this principle (PCR): Principle of Countable Recursion. Let $T$ be a set, and let $p$ be some map­ping from $\{$finite ...
2
votes
2answers
41 views

Find out $n$-th term of monotonic functions increasing and decreasing

I have a series whose max and min values are defined. the values in the series have an increase monotonically by $x\%$ and decrease once the maximum is reached. For example, this series has a min ...
0
votes
1answer
50 views

Use geometric progression formula to expand generating function into a power series?

I am a software engineer and I am studying combinatorics on my own to enhance my learning. I have been finally starting to get the hang of generating functions, but the following problem below has me ...
0
votes
1answer
34 views

Recursive Definition

Consider the following informal definition for a function calc(x,y) = (0*y) + (1*y) + … + (x*y) For example, we have that calc(2,5) = (0*5) + (1*5) + (2*5) Give a recursive definition for the ...
0
votes
1answer
51 views

Recursive Enumeration of Total Recursive Functions vs Partial Recursive Functions

We have: Primitive Recursive $\subseteq$ Total Recursive Functions $\subseteq$ Partial Recursive Functions There are three points that appear at odds with eachother: 1) The primitive recursive ...
2
votes
2answers
41 views

How to use recurrence to define generating function? How to write generating function as power series?

I am a software engineer teaching myself combinatorics. This problem is destroying me, but I am following what I thought was the appropriate strategy to solve a recurrence. I am also confused as to ...
0
votes
4answers
47 views

Finding the $S_n$ of a recursion

$$\sum_{k=0}^{n} (1+2k+4(k(k+1)))=?$$ In order to find the $S_n$ what methods are best fitted for such problem? Is it possible to use the lemma $\sum_{i=0}^{n} i= {n(n+1)}/2$ and plug in? I tried but ...
2
votes
1answer
19 views

How to prove the recurrence relation for this generating function problem?

I am a software engineer and I am learning combinatorics theory on my own. I recently got stumped by the following problem. Problem Let $a_{0} = 2$ where $a_{n} = 3a_{n-1} - 2$ with $n>0$. ...
0
votes
2answers
35 views

Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
2
votes
3answers
58 views

Finding the sum of n terms $S_n$ starting from sigma $k=0$

$$\sum_{k=0}^{n} ((4k-3)\cdot 2^k)+4=(2^{n+3}+4)n-7\cdot2^{n+1}+15$$ How? I've tried everything but i don't see it. Any equivalent solutions are also welcome, thanks.
0
votes
2answers
88 views

Finding the nth term of 1, 6, 24, 76,212,…

What different methods of recursion can I use to find the nth term of this recursion? This should be simple but I don't know what I'm missing. Could you demonstrate the method? $n(0)= 1$, $n(1)= 6$, ...