Questions tagged [recursion]

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 a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory

Filter by
Sorted by
Tagged with
12
votes
4answers
18k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
21
votes
4answers
9k views

Ackermann Function primitive recursive

I am reading the wikipedia page on ackermann's function, http://en.wikipedia.org/wiki/Ackermann_function And I am having trouble understanding WHY ackermann's function is an example of a function ...
19
votes
3answers
1k views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = 2\int_{-1}^x(f_{n-1}(2t+1)-f_{n-1}(2t-1))\...
9
votes
3answers
6k views

How many permutations of $\{1,2,3,…,n\}$ there are with no 2 consecutive numbers?

How many permutations of $\{1,2,3,...,n\}$ are there with no 2 consecutive numbers? For example: $n=4$, $2143$, $3214$, $1324$ are the permutations we look for and $1234$, $1243$, $2134$ are what we ...
567
votes
8answers
39k views

Why is $1 - \frac{1}{1 - \frac{1}{1 - \ldots}}$ not real?

So we all know that the continued fraction containing all $1$s... $$ x = 1 + \frac{1}{1 + \frac{1}{1 + \ldots}} $$ yields the golden ratio $x = \phi$, which can easily be proven by rewriting it as $...
2
votes
1answer
724 views

Establishing formula from recurrence

Can anyone tell me how do we establish a formula from a given recurrence relation? Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$ When I write out the first few values, it ...
7
votes
4answers
8k views

solve $T(n)=T(n-1)+T(\frac{n}{2})+n$

Using the recursion tree i tried solving this: $T(n)=T(n-1)+T(\frac{n}{2})+n$; the tree has two parts (branches) one that of $T(n-1)$ and other branch is of $T(\frac{n}{2})$. But as the term T(n-1) ...
2
votes
3answers
2k views

Finding a closed form for a recurrence relation $a_n=3a_{n-1}+4a_{n-2}$

Consider the sequence defined by $$ \begin{cases} a_0=1\\ a_1=2\\ a_n=3a_{n-1}+4a_{n-2} & \text{if }n\ge 2 \end{cases} .$$ Find a closed form for $a_n$. I tried listing out examples, but I don't ...
47
votes
1answer
1k views

Limit associated with a recursion

Update: a full solution to the recursion below has now been found, and it is discussed here. If $z_n < 2y_n$ then $y_{n+1} = 4y_n - 2z_n$ $z_{n+1} = 2z_n + 3$ Else $y_{n+1} = 4y_n$ $z_{n+1} = ...
1
vote
1answer
140 views

Can't find the demonstration of a theorem about recursion [closed]

Here's the theorem : Let $E$ be a set, $g$ a function from $E$ into $E$, and $a$ an element of $E$. There exists a unique function $f$ defined from $\mathbb{N}$ into $E$ such that $f(0)=a$ and $f(n+...
1
vote
1answer
196 views

Define a countably infinite subset of $X$

Suppose $X$ is infinite and $f_n: \{1,\cdots,n\} \to X$ is injective for all $n \in \mathbb N$. Define an injective mapping $G:\mathbb N \to X$. I re-formulate Asaf Karagila's sketch into a proof in ...
0
votes
1answer
133 views

Let $A$ be a subset of $\Bbb N$ without a greatest element. Then there exists a unique, strictly increasing, and surjective mapping $f:\Bbb N \to A$

Let $A$ be a nonempty subset of $\Bbb N$ without a greatest element. Then there exists a unique, strictly increasing, and surjective mapping $f:\Bbb N \to A$. In my textbook, the author said that ...
16
votes
1answer
660 views

Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
7
votes
5answers
3k views

How to get nth derivative of $e^{x^2/2}$

I want to calculate the nth derivative of $e^{x^2/2}$. It is as follow: $$ \frac{d}{dx} e^{x^2/2} = x e^{x^2/2} = P_1(x) e^{x^2/2} $$ $$ \frac{d^n}{dx^n} e^{x^2/2} = \frac{d}{dx} (P_{n-1}(x) e^{x^2/...
3
votes
5answers
698 views

How many lattice paths are there from $(0,0)$ to $(2n,2n)$ that avoids odd points

How many lattice paths are there from $(0,0)$ to $(2n,2n)$ that do not go through one of the points $(2i-1,2i-1)$ for $i=1,\dots,n$? My idea is to count the number of total lattice paths one can take ...
5
votes
8answers
448 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 ...
1
vote
1answer
302 views

Proof of a proposition about recursion definition (Terence Tao's Analysis I)

Exercise 3.5.12. Let $ f: \mathbb N \times \mathbb N \to \mathbb N$ be a function, and let c be a natural number. Show that there exists a function $a:\mathbb N\to \mathbb N$ such that $$a(0)=c$$ and $...
17
votes
6answers
2k views

Definition of General Associativity for binary operations

Let's say we are talking about addition defined in the real numbers. Then, by induction we define $\sum_{i=0}^{0}a_i=a_0$ and $\sum_{i=0}^{n}a_i=\sum_{i=0}^{n-1}a_i+a_n$ for $n> 1.\:$ Now, how do ...
8
votes
0answers
251 views

Modified AGM: $a_{n+1}=\frac{a_n+b_n}{2}, \quad b_{n+1}=a_n+b_n-\sqrt{a_n b_n}$

The idea is as follows: generate a sequence from two numbers by subtracting their means from their sum, for example arithmetic and geometric means: $$a_{n+1}=a_n+b_n-\frac{a_n+b_n}{2}=\frac{a_n+b_n}{2}...
7
votes
2answers
313 views

A known closed form for Borchardt mean (generalization of AGM) - why doesn't it work?

There is a curious four parameter iteration introduced by Borchardt: $$a_{n+1}=\frac{a_n+b_n+c_n+d_n}{4} \\ b_{n+1}=\frac{\sqrt{a_n b_n}+\sqrt{c_n d_n}}{2} \\ c_{n+1}=\frac{\sqrt{a_n c_n}+\sqrt{b_n ...
3
votes
3answers
23k views

Asymptotic bounds of $T(n) = T(n/2) + T(n/4) + T(n/8) + n$

This problem is given in "Introduction to Algorithms", by Thomas H. Cormen. I have the answer to it, but I don't understand it. The answer is, $T(n) = \Theta(n)$. It would be really good if you ...
12
votes
2answers
822 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 $...
5
votes
1answer
324 views

A nice pattern for the regularized beta function $I(\alpha^2,\frac{1}{4},\frac{1}{2})=\frac{1}{2^n}\ $?

In this post, the problem was given integer/rational $N$, to solve for algebraic number $z$ in the equation, $$\begin{aligned}\frac{1}{N} &=I\left(z^2;\ a,b\right)\\[1.5mm] &= \frac{B\left(z^2;...
4
votes
1answer
61 views

Find $cot\space x_n$ if $sin(x_{n+1}-x_n)+2^{-(n+1)}sin\space x_nsin \space x_{n+1}=0$ for $n\ge1$

Also Given Suppose $x_1=tan^{-1}2>x_2>x_3>......$ are positive real numbers I cannot understand as to how I should approach but I have a hunch which is a bit hand-wavy way to prove it but ...
3
votes
2answers
523 views

Find a formula for a sequence $\{\sqrt{3},\sqrt{3\sqrt{3}},\sqrt{3\sqrt{3\sqrt{3}}},…\}$

I'm trying to find a formula for the following sequence: $\{\sqrt{3},\sqrt{3\sqrt{3}},\sqrt{3\sqrt{3\sqrt{3}}},...\}$ I thought of solving it recursively and I got this formula: $a_{n}=\sqrt{3*a_{n-...
4
votes
1answer
111 views

Any advantages of using Gödel universal functions in proving unsolvability?

Let $U$ be a universal function for the class of computable functions of one variable. This means that $U:N\times N\to N$ is a computable (partial) function and for every computable (partial) function ...
4
votes
3answers
5k views

How many ways to reach $Nth$ number from starting point using any number steps between $1$ to $6$

In a board game, dice can roll either $1, 2, 3, 4, 5$ or $6$. The board has $N$ number of space. Every time of dice roll randomly, pawn moves forward exactly to dice rolled a number. Now the problem ...
4
votes
1answer
133 views

Does every positive rational number appear once and exactly once in the sequence $\{f^n(0)\}$ , where $f(x):=\frac1{2 \lfloor x \rfloor -x+1} $

Consider the map $f:\mathbb Q^+ \to \mathbb Q^+$ defined as $f(x):=\dfrac1{2 \lfloor x \rfloor -x+1} , \forall x \in \mathbb Q^+$ ; then is the function $g:\mathbb Z^+ \to \mathbb Q^+$ defined as $g(...
3
votes
3answers
113 views

What is the number of strings at size $n$ that is constructed from ${a,b,c,d}$ and there is an even num of $a$

What is the number of strings at size $n$ that is constructed from ${a,b,c,d}$ and there is an even num of $a$? I have tried to answer it as recursion formula in the following logic: In order to ...
1
vote
1answer
3k views

Prove that a recursive sequence is monotonically increasing

$a _{1} = \frac{1}{2}, a _{2} = 1, a _{n}= \frac{1}{2} a_{n-1} + \sqrt{a _{n-2} }$ Show by the induction that it's $\le 4$ and also by the induction that $a_{n+1}-a_n \ge 0$ If it comes to first I ...
1
vote
2answers
264 views

Recursion: putting people into groups of 1 or 2

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
0
votes
1answer
563 views

$n$ Lines in the Plane

How am I to "[u]se induction to show that $n$ straight lines in the plane divide the plane into $\frac{n^2+n+2}{2}$ regions"? It is assumed here that no two lines are parallel and that no three lines ...
0
votes
1answer
174 views

Confusion with Recursion Theorem

I am confused with certain aspects of the proof given in Hrbacek and Jech. The following link gives a similar proof to that in the book: Prove the Recursion Theorem 1) Firstly, why do we need to ...
5
votes
4answers
306 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

Find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$, $\ T(n)=c$. I didn't manage ...
4
votes
2answers
479 views

Proving a recurrence relation for strings of characters containing an even number of $a$'s

We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings. Prove ...
4
votes
2answers
1k views

$T(n)=T(cn) + T((1-c)n)+1$ while $0<c<1$

Question: $T(n)=T(cn) + T((1-c)n)+1$ $0<c<1$ and $T(1)$ is constant. My thoughts: I'm trying to solve this recursion using Induction, but I think I got it all wrong. My guess is that $T(n) = ...
3
votes
2answers
2k views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
3
votes
4answers
2k views

Need to find the recurrence equation for coloring a 1 by n chessboard

So the question asks me to find the number of ways H[n] to color a 1 by n chessboard with 3 colors - red, blue and white such that the number of red squares is even and number of blue squares is at ...
2
votes
5answers
135 views

Find recursive formula for sequence $a_n = \left(\frac23\right)^n + n$

So I start with: $$a_n = \left(\frac23\right)^n + n$$ I know $a_1=\frac53, a_2=\frac{22}9, a_3=\frac{340}{81}, a_4=\frac{1247}{243} $ Then I do: $$a_{n-1} = \left(\frac23\right)^{n-1} + (n-1)$$ Do ...
2
votes
1answer
129 views

Recursive integration by parts general formula.

Let $f$ be a smooth function and $g$ integrable. Denote the $n$-th derivade of $f$ by $f^{(n)}$ and the $n$-th integral of $g$ by $g^{(-n)}$. Integration by parts stands $$\int fg \ = \ f \int g - \...
1
vote
1answer
124 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
1
vote
1answer
47 views

induction with 2 recursive sequnces

I'm having trouble solving this problem. I have relation for two sequences of natural numbers. $$a(n)+\sqrt3\cdot b(n)=\left(1+\sqrt3\right)^n$$ and I have to prove that recursions: $$\begin{align*...
1
vote
3answers
141 views

Proof by induction that recursive function $\text{take}$ satisfies $\text{take}(n) = 100 - 2n$

I'm sick and tired off posting threads about induction... I just can't seem to get it, I need someone to give me a detailed explanation and treat me like a 5 year old, literally. I'm wasting a lot of ...
1
vote
1answer
94 views

Recursion $y_n = ky_{n-1}+ry_{n-2}, y_0 = 2, y_1 = k$ and Fermat Theorem

I was looking for the $$y_n = ky_{n-1}+ry_{n-2},\\ y_0 = 2,\\ y_1 = k$$ recursive relation and according Diophantine equations $y_n=z^2$. Then I saw that for the $$k=A+B\\ r=-AB \\ y_n=A^n+B^n$$ ...
1
vote
1answer
268 views

Example of a recursive set $S$ and a total recursive function $f$ such that $f(S)$ is not recursive?

Browsing wikipedia, I stumbled on the following: "The image of a computable set under a total computable bijection is computable." Given the form of the theorem, there must be some example of a ...
1
vote
3answers
109 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
2answers
189 views

Using the recursion theorem to implement the Sieve of Eratosthenes.

Update: I provided an answer here that shows how to define a mathematical function using the recursion theorem. This function can be reconfigured to compute the prime-counting function, $\pi(x)$. ...
1
vote
3answers
2k views

Show convergence of recursive sequence and find limit value

Let $(a_n)_{n \in \mathbb N}$ be a recursive sequence. It is defined as $a_1=1, \quad a_{n + 1} = \frac{4a_n}{3a_n+3}$. I have to show that the sequences converges and find a limit value. To show ...
1
vote
1answer
530 views

Recursive formulas and integration [duplicate]

Using integration by parts find a recursive formula of $\int cos^n(x) dx$ and use it to find $\int cos^5 x dx$ I have no idea how to do this and my knowledge does include integration by parts etc. I ...
0
votes
2answers
174 views

Possible distinct binary tree structures at depth d

I'm trying to figure out a recursive formula for the number of possible distinct binary trees at any depth d. I haven't been able to find any sort of sources on this. basically, at depth 0, the only ...