Skip to main content

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
1 vote
1 answer
46 views

Proving that a recursive sequence is bounded and monotone

Let $a_0=2\sqrt3$ and $b_0=3$, and define two sequences recursively by $$a_n=\frac{2a_{n-1}b_{n-1}}{a_{n-1}+b_{n-1}}\quad\text{and}\quad b_n=\sqrt{a_nb_{n-1}}.$$ This is an exercise in Jay Cummings (...
Ahmed's user avatar
  • 21
-1 votes
1 answer
49 views

Applying $\mu$ -Operator for Unbounded minimization

I'm learning how to use the $\mu$-Operator for unbounded minimization and trying to define a partial recursive function $g(y,z)$ from the primitive recursive function $f$ defined as: $$ f(x, y, z) = \...
Sami B.'s user avatar
1 vote
2 answers
51 views

place letters(A B C D) in N places, with repetition such that the letter A doesnt appear K consecutive times

i need find a recursive function for : place letters(A B C D) in N places, with repetition such that the letter A doesnt appear K consecutive times. K is given and known to be K>=2. example for n=4 ...
user25778822's user avatar
1 vote
1 answer
49 views

Number of vector of length $n$ over ${A,C,T,G}$ that do not have $k$ consecutive $A$'s [duplicate]

In this problem, $k$ is a constant, and we need to find a recursive function that depends only on $n$, i,e $f(n)$. Here is my (wrong) solution: Say there's a valid vector of length $n$. Let's separate ...
natitati's user avatar
  • 429
-1 votes
1 answer
67 views

Number of ways to write n as a sum of k different nonnegative integers

I need find a recursive function ( Withdrawal formula ) $\operatorname{f}\left(n,k\right)$ for the problem: What is the number of ways to write $n$ as a sum of $...
user25778822's user avatar
3 votes
1 answer
65 views

Is there a function $f :A^{<\mathbb{N}}\to E$ such that $f (s{}^\frown a)=h(f(s),a,|s|)$ for any $s\in A^{<\mathbb{N}}$ and $a\in A$?

Given a set $A$, define $A^{<\mathbb{N}}:=\cup _{n\in\mathbb{N}}A^n$ with $A^0:=\{\emptyset\} $ and $A^n$ being the $n$-fold cartesian product of $A$. For any $s:=(s_0,\cdots,s_{n-1})\in A^n\...
rfloc's user avatar
  • 1,209
2 votes
2 answers
94 views

Number of ways to arrange $n$ people in circles

First I want to point out that this is NOT the problem of arranging $n$ in ONE circle, for those who are rushing to close my question. Now for the problem: in how many ways can $n$ people be arranged ...
natitati's user avatar
  • 429
1 vote
1 answer
93 views

A property of $\lt$ in Primitive recursive arithmetic

In Primitive recursive arithmetic (PRA), we can introduce $\lt$ by introducing its representing function $K_{\lt}$, where $K_{\lt}(x,y) =sg(x+1-y)$. Here "sg" and "-" are the ...
nilpotent's user avatar
2 votes
1 answer
139 views

Order between the solutions of linear recursions [closed]

We consider the following 4 linear recursions: $$ \begin{array}{llll} u_{n+3}& = \frac 12 u_{n+2} & + \frac 14 u_{n+1} & + \frac 18 u_n \\ v_{n+3} & = \frac 12 v_{n+2} &+ \frac ...
Olivier's user avatar
  • 1,365
4 votes
2 answers
84 views

Getting explicit formula from non-homogenous recursive sequence

I am wondering whether there is an efficient way to find explicit formulas for non-homogenous recursive sequences. While writing out the first few terms and ...
CharComplexity's user avatar
0 votes
0 answers
64 views

Counting "perfect a:b" sequences

I was given this question : a sequence of black and white balls is "$a:b$ perfect" if it starts and ends with a white ball, and in between every $2$ consecutive white balls there are at ...
Johann Carl Friedrich Gauß's user avatar
14 votes
5 answers
3k views

How do we define addition?

I've been trying to learn naive set theory through a YouTube series by 'The Bright Side of Mathematics'. So far, I've been able to understand successor maps and the definition of $\mathbb{N}_{0}$. I ...
Spyridon Manolidis's user avatar
0 votes
1 answer
78 views

Number of possible circles with at least two people

I was given this question: In how many possible ways can we arrange $n$ people in circles such that the order between the circles does not matter, but the order ...
Johann Carl Friedrich Gauß's user avatar
4 votes
2 answers
212 views

An alternative way to solve a classic problem of combinatorics

The problem is to count how many permutations in $S_n$ have no fixed points. Let call this number $f(n)$, and define the set $N=\{1,\ldots,n\}$. The 'classic' solution is using the exclusion-inclusion ...
ajotatxe's user avatar
  • 65.9k
3 votes
2 answers
98 views

Proving the shortlex ordering is a well-ordering

Let $(A,<)$ be a nonempty linearly ordered set, and let $\operatorname{Seq}(A)$ denote the set of finite sequences of elements of $A$. That is, $f\in\operatorname{Seq}(A)$ is a function $f:n\to A$, ...
John's user avatar
  • 4,442
3 votes
1 answer
103 views

Transform a recursive sequence to a iterative sequence

Consider the sequence $x_n=\sum_{j=0}^{n-1}y_{n-j}x_j$ with $x_0=1$ and $(y_n)_{n\in\mathbb N\backslash 0}$ is any arbitrary sequence. Show that \begin{align*} x_n=\sum_{j=0}^n a_{nj} \end{align*} ...
marc's user avatar
  • 242
-2 votes
0 answers
42 views

What class of function does the recursive function $f_n(x)=(b+ax+x\partial_x)f_{n-1}(x)$ belongs to?

I derived a recursive relationship with respect to a function $$f_n(x)=(b+ax+x\partial_x)f_{n-1}(x)$$ where $$f_0(x)=1$$ The notation here is similar to the generating function of the combinatorics, ...
ShoutOutAndCalculate's user avatar
1 vote
1 answer
109 views

Is there a formal algebraic theory for recursive/inductive operators (lookup question: couldn't find after searching)

I'm aware of recursive functions in computer programming. Surprisingly I was having trouble finding similar books and articles on recursive or inductive mathematical structures (that is, in situations ...
Nate's user avatar
  • 894
-2 votes
0 answers
53 views

How to prove the recursively defined set L' is equal to L?

In the book https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/resources/mit6_042js15_textbook/ Page 199,there is an excercise on recursive sets and structural induction ...
Jery Lazman's user avatar
1 vote
1 answer
99 views

Defining rigorously a sequence such that $y\in f(x_0,\cdots,x_n)$ for all $n\in\mathbb{N}$

Let $A,Y$ be two sets, $\sigma \in A$ and $y\in Y$. Define $A^{<\mathbb{N}}:=\cup _{n\in\mathbb{N}}A^n$ with $A^0:=\emptyset $ and $A^n$ being the $n$-fold cartesian product of $A$. Suppose that $f:...
rfloc's user avatar
  • 1,209
0 votes
1 answer
61 views

Maximum function recursive property

In an old book by Richard Bellman, I found a proof of the initial Bellman equation: $$ f_n(x)=\max_{0\le x_N\le x}\left[g_N(x_N)+f_{N-1}(x-x_N)\right] $$ where $x_i\ge 0$ and $\sum_{i=1}^Nx_i=x$. ...
TheKwiatek666's user avatar
7 votes
3 answers
1k views

Prove that the numbers 2008 and 2106 are not terms of this sequence.

The sequence $(x_n)$ is given recursively with $x_1 = 188$, and $x_{n+1}$ is obtained from $x_n$ by adding twice the sum of the digits of the number $x_n$. Prove that the numbers 2008 and 2106 are not ...
user avatar
0 votes
1 answer
74 views

How to define the reverse of a string recursively and then prove that : $Reverse(s*t)=Reverse(t)*Reverse(s)$?

I was doing the excercises of section 6.5 of the book Mathematics for Computer Science revised Monday 18th May, 2015, of the MIT opencourseware(https://ocw.mit.edu/courses/6-042j-mathematics-for-...
Javier Lázaro's user avatar
2 votes
2 answers
166 views

Transform recursive formula to iterative formula

Let $(a_i)_{i \in \mathbb{N}\ }$ be some real series, $\gamma > 0$ and $$ b_{i} = \gamma \sum_{j=0}^{i - 1}a_{i - j}\,b_{j} \quad\mbox{with}\ b_{0} = \gamma $$ Is there a way to calculate $b_i$ ...
Robert's user avatar
  • 386
0 votes
0 answers
40 views

When to use a simple formula vs an iterative solution?

I have this well known formula for calculating the investment sum f(x) = s*(1+i)^x s = starting sum i = interest X (variable) = number of periods. What does this function look like if I add an amount ...
Igor's user avatar
  • 91
0 votes
0 answers
32 views

Finding the general term of a given P-recursive sequence

I managed to prove that a certain sequence of rational numbers $(c_n)_n$ satisfies the following P-recursive equation: $$3(n-1)(n+2)c_{n+2}=(3n^2-3n+2)c_{n+1}+6nc_n$$ with "initial conditions&...
Kolakoski54's user avatar
0 votes
1 answer
47 views

Find a $2$-dimmension recursive sequence.

Let $P(k,n)~(k,n\ge 0)$ be a $2$-dimmension recursive sequence satisfying \begin{cases} P(0,0)&=1,\\[5pt]P(0,n)&=0,&n\ne 0,\\[5pt]P(k,0)&=\frac{1}{6}\left(1-\left(-\frac{1}{2}\right)^...
mengdie1982's user avatar
  • 13.9k
2 votes
2 answers
86 views

Closed form of the recursion $D_{n+1} = n(D_n + D_{n-1})$

I got this problem from chapter five of Titu Andreescu A path to combinatorics for undergraduates. I'm asked to give a closed form to the given recursion given that $D_1 = 0$ and $D_2 = 1$. And I know ...
H4z3's user avatar
  • 802
0 votes
0 answers
68 views

What is the "procedure" mentioned here by Tao in Analysis I regarding recursive sequences?

I have 2 questions about a passage from Tao's Analysis I in which he defines recursive sequences. Questions have been asked about this passage here, here, here, and here; but I have different ...
Princess Mia's user avatar
  • 3,029
1 vote
0 answers
30 views

Finding and classifying Hénon map bifurcations and periodic points

I am stumped on how to answer the following question: Consider the Hénon map given by $$\textbf{H}(x, y) = (a-x^2+by, x)$$ Assume $0<b<1$. Classify the bifurcations that occur at $a = -\frac{1}{...
JOlv's user avatar
  • 99
-1 votes
2 answers
160 views

How to justify why succession and addition cannot be circularly defined like this?

I am reading Tao's Analysis I, in which he states: One may be tempted to [define the successor of $n$ as] $n + 1$. . . but this would introduce a circularity in our foundations, since the notion of ...
Princess Mia's user avatar
  • 3,029
0 votes
0 answers
42 views

the number of ways to realize the multiplication in $x_1 \times x_2 \times ... \times x_n \times x_{n+1}$ as a multiplication of 2 factors

let $a_n$ be the number of ways to realize the product $x_1 \cdot x_2 \cdot ... \cdot x_n \cdot x_{n+1}$ as a product of 2 factors (no change in the placing of the variables, so $x \cdot y$ is $y \...
user avatar
2 votes
0 answers
53 views

Is there a notion of a "smooth approximation" of a fractal?

The motivating example that comes to mind is the koch snowflake fractal. Given that the recursive structure of the fractal comes from injecting triangles into triangles, it seems like one could ...
Makogan's user avatar
  • 3,439
1 vote
1 answer
78 views

Since corollaries of ZFC are r.e.,why there are Turing degrees that are not r.e.?

for any Turing degree a and A∈a,and a fixed x,we can just put the formula “x∈A” into the Turing machine which examines whether a formula is a corollary of ZFC.It halts iff ZFC proves “x∈A”.So we got ...
jtxsxlm's user avatar
  • 11
0 votes
2 answers
70 views

Solving the recursion $ \kappa_n=\frac{2 \pi}{n} \kappa_{n-2} $, with $\kappa_1=2, \kappa_2=\pi$

For the recursion $$ \kappa_n=\frac{2 \pi}{n} \kappa_{n-2} $$ with $\kappa_1=2, \kappa_2=\pi$, the solution should be $$ \kappa_n=\frac{\pi^{n / 2}}{\Gamma\left(\frac{n}{2}+1\right)} \quad(n \geq 1) $$...
nathan's user avatar
  • 39
0 votes
1 answer
44 views

Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
Bob Marley's user avatar
2 votes
1 answer
443 views

How can we prove that a number is not happy number?

def : a positive number is called happy if repetative square sum of its digits ends in 1, otherwise not. Upon checking some numbers, I found that a number that is not happy will result in some ...
Yanjan. Kaf.'s user avatar
0 votes
0 answers
43 views

Solving a recursive equation with a sum-product

I'm dealing with a recursive equation at work and struggling to solve it. The expression is: $$a_j = \sum_{i=1}^j b_i + \sum_{i=1}^j a_{i-1}c_{i-1},$$ where $a_0=c_0=0$. I've tried solving this for ...
jjet's user avatar
  • 480
2 votes
1 answer
161 views

How to prove the following recursion converges to 1/e?

I was trying to solve another problem when I came across the following recursion. For $n,k\in\mathbb{N}$, define $f(0,k)=1$ if $k=0$ else $0$, $f(n,k)=\frac{1}{k+2}\sum_{i=0}^{k+1} f(n-1,i).$ ...
John Ao's user avatar
  • 71
0 votes
3 answers
116 views

Functions or formulas for Base-10 to Base-n (1<n<10)

Trying to find an answer to this question I was able to find a formula for the conversion of decimal numbers to their binary representations in Base-10 $D(x)$: $$ D(x) = C_0 $$ $$ C_o = (C_{o+1} \cdot ...
PageSteiner's user avatar
2 votes
0 answers
76 views

the Ackermann function must be total and unique based on one specific list of rules

This is one following question based on one question I asked before. In mcs.pdf, it has Problem 7.25 in p251(#259). One version of the the Ackermann function $A:\mathbb{N}^2 \to \mathbb{N}$ is ...
An5Drama's user avatar
  • 416
0 votes
1 answer
34 views

Card Stopping Problem - Issue with alternate solution

I'm trying to solve the problem here (Stopping Problem Question) using a similar, but slightly different method from the solution provided. Here's what I did: Let $p_B(r,b)$ be the probability that ...
mk0219's user avatar
  • 178
2 votes
2 answers
140 views

Game of Pigeons - Probability Puzzle

The Problem: Alice and Bob take turns drawing a pigeon from a sack which initially contains $W$ white and $B$ black pigeons. The first person to draw a white pigeon wins. After each pigeon drawn by ...
Devansh Agarwal's user avatar
1 vote
1 answer
29 views

Lemma 6.2. in Scaling Algorithms for the Shortest Path Problem

I have a question regarding the proof of Lemma 6.2. in this paper: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/scaling%20algorithm%20for%20the%20shortest.pdf. The simplified ...
Botanicus's user avatar
  • 102
2 votes
0 answers
99 views

The recursion Theorem: Bottom-up vs top-down proof

The Recursion Theorem (for $\mathbb{N}$) states that for any set $A$, any $a\in A$, and any function $g:\mathbb{N}\times A\to A$, there exists a unique function $f:\mathbb{N}\to A$ such that $f(0)=a$,...
John's user avatar
  • 4,442
2 votes
1 answer
57 views

Linear coupled recursive relations and finding the limit of the ratio

Let $a_0,b_0$ be any two positive integers. Define $a_n,b_n$ using the relations: $$a_n=a_{n-1}+2b_{n-1}, b_n=a_{n-1}+b_{n-1} \forall n \in N$$ Find: $$\lim_{n \to ∞} \dfrac{a_n}{b_n}$$ My attempt: I'...
Cognoscenti's user avatar
5 votes
2 answers
87 views

Similarity between Combinatorial Series and Recursions

I was evaluating the sum $$a_n = \sum_{k=0}^{n} {2n+1 \choose 2k+1} 2^{3k}$$ The method I went about was treating $$a_n = \frac{1}{2\sqrt{2}} \sum_{k=0}^{n} {2n+1 \choose 2k+1} (2\sqrt{2})^{2k+1} \\ ...
omega's user avatar
  • 53
-1 votes
1 answer
36 views

Let $h:\{0,1,\ldots,10\} \rightarrow \mathbb{R}$ such that $h(0)=0, h(10) = 10$. Find $h(1)$ if $2[h(i)-h(i-1)]=h(i+1)-h(i)$ [duplicate]

The question: Let $h:\{0,1,\ldots,10\} \rightarrow \mathbb{R}$ such that $h(0)=0, h(10) = 10$. Find $h(1)$ if $2[h(i)-h(i-1)]=h(i+1)-h(i)$ My attempt: \begin{align*} 3h(10) &= 30 \\ 3h(9) &= h(...
Debu's user avatar
  • 1
0 votes
2 answers
42 views

Counting functions such that $f(a_i) \neq f(a_{i+1})$ cyclically

Find the number of functions $f:\{a_1,a_2...a_n\} \to \{b_1,b_2,...b_m\}$ where $n>m>3$ such that $f(a_i) \neq f(a_{i+1}), \forall i=1,2,3...(n-1)$ and $f(a_n) \neq f(a_1)$. Attempt: It is ...
Cognoscenti's user avatar
0 votes
1 answer
84 views

partial function version of the Ackermann function must be total

In mcs.pdf, it has Problem 7.25. (I only solve somewhat important problems referred to in the chapter contents because I have learnt one Discrete Mathematics book before and read mcs to ensure no ...
An5Drama's user avatar
  • 416

1
2 3 4 5
58