Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...

1
vote
1answer
30 views

The use and meaning of the “tilde-equal-symbol” for partial (recursive) functions in Girards monograph 'proof theory and logical complexity, volume 1'

English is not my native language, so please forgive if I do not express myself properly. I am working with the book named above on proof theory, and I have a little problem with the authors use of ...
1
vote
1answer
23 views

Completely lost on using strong induction for this proof regarding a recursive algorithm.

T(n) = 1 when n $\le$ 10 T(n) = T($\lfloor\frac{n}{5}\rfloor$) + 7 T($\lfloor\frac{n}{10}\rfloor$) + n when n $\gt$ 10 Prove by strong induction that, for all n ≥ 1, we have T (n) ≤ 10n. ...
1
vote
2answers
83 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)$. ...
0
votes
0answers
24 views

Closed form for a class of recursive functions

Suppose we define a class of functions $f_n$ (with domain $\mathbb{N}^n$ without $0$) as follows: $$ f_n(x_1,x_2,\ldots,x_n)=\begin{cases} 1, & x_1=1\\ x_1, & x_2=1\\ \,\vdots & \,\vdots\\ ...
2
votes
2answers
142 views

A constructivist reading of the Church-Turing thesis

I recently asked myself a question concerning a constructivist reading of the Church-Turing thesis. Let us give the latter in the following formulation: put $EC(f)$ for "$f$ is effectively computable" ...
2
votes
0answers
35 views

Limit of a recursive sequences involving the AM, GM, and HM (arithmetic-geometric-harmonic mean)

Let $x,y,z$ be positive real numbers. And let $\text{AM}$, $\text{GM}$, $\text{HM}$ respectively be the arithmetic mean, geometric mean, and harmonic mean. Define $$a_n=\text{AM}(a_{n-1},g_{n-1},h_{...
1
vote
3answers
50 views

How do i compute $f_n = 3f_{n-1} + 2\sqrt{2f_{n-1}^2 - 2}$ for $n$ around $10^{18}$?

So I have the recurrence $$f_n = \begin{cases} 3f_{n-1} + 2\sqrt{2f_{n-1}^2 - 2}, &n > 1\\ 3, &n = 1\\ \end{cases}$$ and I need to compute it in $O(\lg n)$, for $n$ as big as $10^{18}$. I ...
0
votes
2answers
38 views

Weird recurrence [closed]

Find an explicit formula of the function E defined on natural numbers such that $E(1) = 1$ and $E(N) = 1 + \frac{E(1) + ... + E(N-1)}{N}$ for $N > 1$.
0
votes
0answers
12 views

Strange Recursion with non-constant coefficient

I try to analyze the following recursion but I do not really now the tools for analyzing recursions with non-constant coefficients. Can anyone give me a hint? $c$ is a constant between $0$ and $1$. ...
1
vote
0answers
15 views

Recursive Signal Processing

I am messing around with signal processing, and I figured out the equation of a delay feedback loop, but I want to write it out in linear algebra. The problem is that I'm not quite sure how to format ...
2
votes
1answer
36 views

Recursive algorithm probability

I'm trying to find the probability of obtaining a six on a dice roll following these rules: You roll a dice and if you roll $6$, then you win. However, if it is not $6$, you roll another dice....
2
votes
1answer
44 views

Structural induction in haskell

Notation in this question derives from Haskell as follows. Let $[A]$ denote the collection of lists whose elements are drawn from the set $A$, so e.g. $[\mathbb{Z}]$ is the set of integer lists. ...
1
vote
1answer
24 views

Time Complexity Of Binary Tree Subtree Algorithm

Given two binary trees, check whether one is a subtree of another one. This is my algorithm. Basically, it says: For two binary trees A and B, A is a subtree of B if they are the same tree. If ...
1
vote
1answer
24 views

Find a recursion formula for a combinatoric problem

I have a combinatoric problem: find the number of positive integer solutions $x_i$ s.t. $$ \begin{cases} x_1+...+x_n = a\\ px_1 \geq x_2\\ px_2 \geq x_3\\ \vdots \\ px_n\geq x_1 \end{cases} $$ in ...
1
vote
3answers
54 views

Mathematical function $f(n)$ for number of solutions to $3a+4b+5c=n$

What is the explicit function that given an $n$ outputs how many ordered tuples $(a,b,c) \in \mathbb{N}^3$ are a solution to the equation $3a+4b+5c = n$. I'm really stuck with this but I have a strong ...
2
votes
1answer
42 views

Developing a recurrence relation involving combinations that sum up to $a$

I'd like to find a recurrence relation/recursive definition that can count the total number of combinations s.t. $3x+4y+5z=a$ In other words, given a value $a$, how many sets of $x,y,z \in \mathbb{N}$...
2
votes
1answer
48 views

From infinite product to infinite sum and a needed expression

We have some function $f_n$ where $f_{\infty}=0$. Now we have a recursive function $t$ where $$t_{n+1}=\Big(1-f_n\Big)t_n$$ Does this converge? Determine $t_{\infty}$
2
votes
1answer
20 views

How to use recursion to build a 1:1 correspondence.

Let $\gamma$ be a binary relation with $V$ the departure set and $W$ the destination set. Suppose the following are true: $\tag 1 x \gamma y \land x \gamma z \text{ then } y = z$ $\tag 2 y \gamma x \...
-1
votes
3answers
73 views

Recursion $f(n) = 3f(n-1) - 4f(n-3)$ with $f(0) = 1$ , $f(1) = -3$ , $f(2) = 2$

How can one solve the recursion $$f(n) = 3f(n-1) - 4f(n-3)$$ The start values are $f(0) = 1$ $f(1) = -3$ $f(2) = 2$ I tried to find a general pattern to prove it with induction, but I can't ...
0
votes
0answers
23 views

Tetration induction proof

Problem picture Picture of given ackermann function So far, I have $$A(3,n) = A(2,A(3,n-1))$$ and then using $$A(2,n) = 2 \uparrow \uparrow n$$ I arrive at. $$A(3,n) = 2 \uparrow \uparrow A(3,n-1)$$ ...
0
votes
0answers
12 views

Conditional densities and known past values

Let there be a random variable with the following properties $Y_{t} = \mu + \beta Y_{t-1} + \epsilon_{t} \quad\text{such that} \quad \epsilon_{t}\sim \mathcal{N}(0,\sigma^{2})$ Estimate the ...
0
votes
1answer
33 views

About $\in$-Recursion and Mostowski Collapse

The principle of $\in$-Recursion is a consequence of the regularity axiom. The formulation I know is: $\in$-Recursion: Let $G: V \to V$ be a class function, defined everywhere. Then there is a ...
0
votes
0answers
31 views

Memoization Confusion

Imagine the following game: There is a bank of numbers, and a target number. Players take turns selecting (and thereby removing) a number from the bank, and subtracting it from the target. The ...
0
votes
1answer
37 views

The intuition behind recursive math formula's

I am working on a problem case to try gaining more intuition behind recursion and mathematical formula's. I understand how to solve the case by using code and recursion. However, I find the ...
3
votes
2answers
41 views

Proof by induction in inequalities

$$\sum^n_{k=1} \frac1{k^3} \le \frac 5 4 - \frac 1 {2n^2}$$ For all $n\ge 2$ Now this really a tough one for me. The base case holds at $n = 2$ Then i replaced it with $p$ and then $p+1$ I got an ...
0
votes
0answers
16 views

Definition of computable double sequence

I am a beginner to computability theory and curently readhing Pour-El and Richard Computability in Analysis and Physics, Chapter $1$. At page $18,$ the authors provided the following definition for ...
-1
votes
0answers
26 views

Definition of recursive function and recursively enumerable nonrecursive set

I am a beginner to computability theory and curently readhing Pour-El and Richard Computability in Analysis and Physics, Chapter $1$. At page $15,$ they stated the following waiting lemma. (...
0
votes
1answer
21 views

Defining a recurrence relation for number of words of length $n$ formed from the alphabet $\{x, y, z\}$ that do not contain the string $xxx$

$a_{n}$ describes the number of words that can be composed of this particular set $\{x,y,z\}$. The sequence $xxx$ must not appear in the word. Example: $a_{1}=3$, $a_{2}=9$, $a_{3}=26$ The answer ...
0
votes
0answers
26 views

Explain recurrence and Dynamic Programming methods

Well during competitive programming, Dynamic Programming and Recursion is one of the most favorite topics. It kind of draws the line between an average and a good coder. Now my question is, is there ...
0
votes
0answers
9 views

Relationship between the initial value of the recurrecne relation to the limit

Let $a_1$ be the first term of of sequence. Now define $$a_{n+1}=R(a_n)$$ where R is any recurrence relation. Assuming that $\lim_{n\rightarrow }a_n$ exists , I am looking for a relationship between ...
0
votes
1answer
19 views

The differences between two versions of Recursion Theorem

Version 1: For any set $A$, any $a\in A$, and any function $g:A\times \Bbb N\to A$, there exists a unique infinite sequence $f:\Bbb N\to A$ such that (1) $f_0=a$; (2) $f_{n+1}=g(f_n,n)$ ...
1
vote
1answer
28 views

Complex Recursion

Consider the recursive function $C_n = C_{n-1} + iC_{n-2}$, where $C_1 = 1, C_2 = 1.$ If $C_{10}$ is written in the form $a+bi,$ find $b$. I solved this problem through brute force with a ...
0
votes
0answers
24 views

Recursive algorithm for planar graph

I have this pseudo-code and I need to understand what it does. It takes some planar graph as input and returns a subset of V (that are the vertexes of the graph). It is clearly recursive, but I don't ...
1
vote
3answers
43 views

Derive explicit formula for sequence $x_{n+1}=3x_n+2$

Define a sequence $(x_n)_{n=1}^\infty$ by $$\begin{cases} x_1 = 2 \\ x_{n+1} = 3x_n + 2 & n\ge1 \end{cases}$$ Determine an explicit formula for $x_n$ (i.e., an explicit expression for $x_n$ in ...
0
votes
1answer
33 views

Proving recursive inequality with strong induction

Suppose $h_0, h_1, h_2, \dots$ is a sequence defined: $\qquad h_0=1, h_1=2, h_2=3$ $\qquad h_k=h_{k-1}+h_{k-2}+h_{k-3}, \forall k \in \mathbb{Z}\wedge k\ge 3$ Prove that $h_n \le 3^n,\forall n \in \...
1
vote
1answer
43 views

Prove by induction that $W_n = F_{2n+2}$

My problem relies on an earlier recursive definition that we solved in class: $W_n = 3W_{n-1}- W_{n-2}$ if $n \ge 2, W_0=1$, and $W_1=3.$ It also recalls the Fibonacci recursive definition of $F_n = ...
-2
votes
1answer
69 views

For any integer n >=1, let Fn be the number of aa-free strings of length n. Determine F1, F2, F3 [closed]

Question: We consider strings of characters, where each character is an element of {a; b; c}. Such a string is called aa-free, if it does not contain two consecutive a's. For any integer n > = 1, let ...
3
votes
0answers
49 views

What part of arithmetic can be founded on recursive functions and without unbounded quantification?

Reading Skolem's 1923 Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlicher mit unendlichem Ausdehnungsbereich (Foundation of elementary ...
0
votes
0answers
9 views

Reference for type-2 Turing machines and does the limit lemma hold?

I am looking for a good reference on the theory of type-2 Turing machines (infinite input tape, finite output tape say). In particular, whether the Shoenfield Limit Lemma holds in this case and ...
1
vote
2answers
46 views

Help with induction on a recursive sequence.

I'm currently working on this problem: At first, this looked like a pretty straightforward induction problem. But, once I started working on (b), I ran into an issue. I can show that my base case ...
0
votes
1answer
32 views

Method for solution to a recurrence

Is there a closed form solution or tight bound to recurrence $T[n]=k\cdot T[n^{1/c}] + (\log n)^{r}$ with $k,c,r\geq1$ and $T[n]=O(1)$ if $n\leq2$?
-1
votes
1answer
43 views

Inductive proof for recursive formula with multiple recursive references

This one is hard for me due to multiple recursive statements in the definition, and I have difficulty with inequalities. $a_1=1$ $a_2=1$ $a_3=1$ $a_{n+3} = a_{n+2}+a_{n+1}+a_n$ Prove that for ...
0
votes
1answer
41 views

How many ways to place A's and B's.

The problem: You are given a n*n grid. In how many ways can you place A's and B's in the grid so that there is exactly one 'A' and one 'B' on each row and each column? There may be 0 or 1 letters in ...
0
votes
1answer
27 views

'Transforming' a function $T(m,n)$ into $a(n)$ in an inductive proof

I'm trying to perform an inductive proof for a homework question but am stuck at a scenario I've never encountered before. I am trying to prove inductively that $$ T(m,n) = (m + 1 + n)\cdot a(n) - n!...
0
votes
3answers
214 views

Showing that $a_1=2$ and $a_n=\frac{1}{2}(a_{n-1}+\frac{2}{a_{n-1}})$ define a decreasing bounded sequence [closed]

I need to show that the sequence given by $$a_1=2$$ $$a_n=\frac{1}{2}\Bigg(a_{n-1}+\frac{2}{a_{n-1}}\Bigg)$$ is monotonically decreasing and bounded. But every time I try, I can't make the bounds ...
0
votes
1answer
28 views

Supremum in context of Dynamic Programming

In Bellman's Dynamic Programming (1957), regarding the equation, $$ f(x) = \max_{0 \leq y \leq x} \left[ g(y) + h(x-y) + f(ay+b(x-y)) \right]$$ He writes [about extending this to an infinite ...
0
votes
1answer
25 views

Non-recursive formula for discrete function that follows a recursive pattern

$f$ is a sequence of numbers and $v$ is the sequence of the difference between the consecutive terms of $f$. For example, if $f = 1, 3, 4, 7, 5$, then $v = 2, 1, 3, {-2}$. $f$ is $0\...
0
votes
3answers
44 views

Proof by induction (Recursion)

Am really having a hard-time cracking this one. And no, its not homework. Am jst doing more examples in the textbook to see if i get the concept well It says, we define the polynomial $P_n (x)$ for n ...
1
vote
1answer
48 views

Structural induction - Unsure of which direction to go.

So I'm supposed to use the recursive definition of #c(s) -- the number of occurrences of the character c in A in a string s. I'm tasked with proving the lemma: c(s * t) = #c(s) + #c(t). I was also ...