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
2,790
questions
1
vote
1
answer
46
views
$A\subset \mathbb{N}$ and $(A+1)=\{x+1\mid x\in A\}$. how many subsets of $\{1,2,3,\dots, n\}$ exists, such that $A\cup(A+1)=\{1,2,3,\dots, n+1\}$.
Let $A\subset \mathbb{N}$ and $(A+1)=\{x+1\mid x\in A\}$. For every
$n$, how many subsets of $\{1,2,3,\dots, n\}$ like $A$ exists, such
that $A\cup(A+1)=\{1,2,3,\dots, n+1\}$.
My try:
As we should ...
- 775
0
votes
0
answers
7
views
Recursion on predicate language
Is it possible to write any expression in the language of first-order predicates that would essentially be a recursion, that is, something similar to iteration in a loop?
0
votes
0
answers
21
views
Solve VAR(2) for the n-step ahead forecast
I'm trying to find for this VARX*(2)
$$x_t=a_0+a_1t+F_1x_{t-1}+F_2x_{t-2}+\Theta_0d_t+\Theta_1d_{t-1}+\Theta_2d_{t-2}+\varepsilon_t$$
an explicit form for $x_{T+n}$, i.e. solve it as an equation for ...
- 25
2
votes
0
answers
33
views
Primitive Recursion Data and Uniqueness
This is an exercise from Lawvere’s Conceptual Mathematics that is stumping me. It relates to constructing a single map from a starting point of primitive recursive data. Any help or tips would be ...
- 63
2
votes
1
answer
44
views
Find a recurrence relation for the number of bit strings of length n that contain consecutive symbols that are the same
Here is my attempt:
First there is $2 \cdot 2^{n-1}$ ways if string ends with $00$ or $11$.
Second there are ways when string end with $10$ or $01$. So it will give us $a(n-1)$ ways to solve ...
- 23
2
votes
0
answers
128
views
Proving $x + \sin x + \sin(x + \sin x) + \sin(x + \sin x + \sin(x + \sin x)) + ... = \pi $ [duplicate]
I was given a very interesting sum of series by a friend. The problem is to prove that if $ x \in (0, 2\pi) $ , then
$$ x + \sin x + \sin(x + \sin x) + \sin(x + \sin x + \sin(x + \sin x)) + ... = \pi $...
- 551
1
vote
1
answer
37
views
Is it possible to get multiple bounds from the Ramsey-like recursion $f(t) \leq f(t-1)^2$?
The motivation for this question comes from recursions found in Ramsey theory. The Ramsey number $R(s,t)$ is equal to the minimum $n$ such that for any red-blue coloring of the edges of some $K_n$, ...
- 385
0
votes
0
answers
19
views
Variance of a random recursive relation
Question
Consider a set $\mathcal{U}$ of $n$ distinct objects.
At each time $t\geq 0$, we denote by $V(t)$ the number of visited objects.
Assume $V(0)=0.2 n$, and for any $t>0$, $V(t)=V(t-1)+0.65\...
- 1,187
12
votes
2
answers
1k
views
Symmetry in Probability (AMC 12A 2023)
Flora the frog starts at $0$ on the number line and makes a sequence of
jumps to the right. In any one jump, independent of previous jumps,
Flora leaps a positive integer distance $m$ with probability ...
- 1,456
2
votes
1
answer
115
views
Binary with digit 2 allowed
How many ordered 11-tuples $(a_0,a_1,a_2,...,a_{10})$ of integers
satisfy the equation $$a_0+2a_1+2^2a_2+...+2^{10}a_{10}=2020$$ where
$0\le a_i\le 2$ for all $0\le i\le10$ AMC Mock
If $f(n)$ is the ...
- 1,456
1
vote
0
answers
82
views
If $f(x)$ = $e^x$ + x, what is $f(x+3)$ in terms of $f(x)$?
As the title suggests, the question is rather simple:
"$f(x)$ = $e^x$ + x. Write $f(x+3)$ in terms of $f(x)$."
I encountered this problem in an precalc textbook, in the chapter regarding ...
1
vote
1
answer
47
views
Associativity on concatenation and removal
Let * be an operation on two ordered lists of numbers, where each list has no duplicates. The operation concatenates them and then removes any adjacent identical values recursively.
I want to know if ...
- 13
1
vote
0
answers
29
views
Derivation of Derangement in Permutations and Combinations [duplicate]
let me start by defining a function $D(n)$ for Derangement of $n$ distinct items.
if there are n distinct items, they can be arranged in $n!$ different ways.
so , $$ D(n) = n! - (\binom{n}{1}D(n-1) + \...
- 11
4
votes
1
answer
98
views
Prove that $a_n\ge 1$ for all $n\ge 1$ with equality iff $n=1,2,4,5$
Let $\alpha, \beta,\gamma \in \mathbb{C}$ be the three roots of $x^3 + x+1$. For any $n\in\mathbb{N}$, let $a_n = \dfrac{(\alpha^n-1)(\beta^n-1)(\gamma^n-1)}{(\alpha-1)(\beta-1)(\gamma-1)}$. Prove ...
- 1,195
0
votes
0
answers
62
views
Using generating functions to simplify a recursive solution
This is a follow-on question to my previous one:
All the different ways to add a set of lengths - need explanation of the answer
I have a problem simplifying a specific recursion relation. I have ...
- 11
0
votes
1
answer
92
views
Find a limit of recursion sequence
I have to find a limit of recursion sequence $a_{n}=-\frac{3}{8}(a_{n-1}+a_{n-2})$ where $a_1=1, a_0=0$. I wrote few of first terms of sequence: $0,1,-\frac38,\frac{15}{64},-\frac{57}{8^3}...$ My idea ...
-2
votes
1
answer
104
views
To find $f'(x)$ when $f(x) = \sqrt{\sin^{-1}x+\sqrt{\cos^{-1}x+\sqrt{\sin^{-1}x+\sqrt{\cos^{-1}x+\cdots\infty}}}}$ [closed]
If
$$
f(x) = \sqrt{\sin^{-1}x + \sqrt{\cos^{-1}x + \sqrt{\sin^{-1}x + \sqrt{\cos^{-1}x + \cdots\infty}}}},
$$
then how to find $\frac{d}{dx}(f(x))$?
I am trying this question by taking $f(x)=y$.
Now
$...
- 1,132
0
votes
0
answers
61
views
What are some practical, non set-theoretic applications of the transfinite recursion theorem
I found some applications of the transfinite recursion theorem within set theory. For example, to prove the following theorem:
A set $A$ is infinite if and only if there exists a one-to-one function $...
- 315
1
vote
2
answers
46
views
How do you set up this recursive system?
Here is the problem:
Emma wants to climb a 12-step staircase. She can climb either 1 or 2 steps at a time. In how many ways can she climb the staircase?
I first set $F_{n}$ as the number of steps it ...
- 25
0
votes
0
answers
40
views
Solution to a first-order rational difference equation [duplicate]
I am interested in the following first-order rational difference equation (recurrence relation):
$$x_{n+1} = x_n + \dfrac{\alpha}{x_n} + \beta \ ; \ x_0 >0$$
for positive $\alpha$ and $\beta$. Is ...
0
votes
1
answer
39
views
Find closed form of real valued function
Let $f:\mathbb{N}\rightarrow\mathbb{R}, h:\mathbb{N}\rightarrow\mathbb{R}$ be two functions satisfying $f(0)=h(0)=1$ and:
$$f(n) = \sum_{i=0}^{n}h(i)h(n-i)$$
Find a closed form for $h(n)$ in terms of $...
2
votes
0
answers
40
views
find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$
We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and
assume $T(1)$ is a constant. Find asymptotically tight bounds
$\Theta(f(n))$ for $T(n)$.
There's something that confuses me. We ...
- 775
1
vote
1
answer
65
views
Prove $T(n)=10T(\dfrac{n}{3})+n\sqrt{n}=\Theta(n^{\log{10}_3})$ using induction
We have recurrence $T(n)=10T(\dfrac{n}{3})+n\sqrt{n}$ and assume $T(1)$ is a constant. With Master Theorem applied, we get $T(n)=\Theta(n^{\log_3{10}})$ as this recurrence is the first case of Master ...
- 775
0
votes
1
answer
49
views
Prove that the sequence$(x_n)=\frac{1}{2}(x_n+\frac{a}{x_n})$ where $x_1=1$ and $a>1$ is convergent [duplicate]
So I have a sequence $(x_n)=\frac{1}{2}(x_n+\frac{a}{x_n})$ where $a>1$ and $x_1=1$.
I have to prove it is convergent.I tried with induction to prove that
$a\le x_n^2$ because from that I can ...
- 135
0
votes
1
answer
117
views
Is it possible to rewrite the B-Spline Basis functions nonrecusively
B-Splines have a recursively-defined basis function $N_{i,j}(t)$ as shown here:
$$
\newcommand{\defeq}{:=}
N_{i,j}(t)\defeq\frac{t-t_i}{t_{i+j}-t_i}N_{i,j-1}(t)\frac{t_{i+j+1}-t}{t_{i+j+1}-t_{i+1}}N_{...
- 101
0
votes
0
answers
42
views
How to solve a recursion to find a closed form solution?
I have the following recursive process:
$f_n(t) = e^{t-1} f_{n-1}(1-(1-p)(1-t))$
The initial condition is that $f_0(t) = 1$
I calculated that $f_1(t) = e^{t-1}$
And then I also calculated $f_2(t), f_3(...
- 157
0
votes
1
answer
53
views
What is this kind of recursion?
Consider the following expression:
For any fixed integer $a$, for real $x_i$
Pick an $x_0$ such that
$ln(ln(a))/ln(ln(a*100*x_0))=x_1$
Then substitute $x_0\mapsto x_1$
$ln(ln(a))/ln(ln(a*100*x_1))=x_2$...
- 583
0
votes
0
answers
27
views
Finding general solution to a nonlinear recursive relation involving sum of products
An interesting recursive relation has originated in the solution to an Oxford MAT paper (2018 paper, Q5 (iv)).
The solution gives the correct recursive relation as $$t_n = \sum_{k=1}^{n-1}t_k t_{n-k},\...
- 76
1
vote
3
answers
83
views
Proving divisibility of a sum $\sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k}$
I have been given $$
\sum_{k=0}^{\lfloor{n/2}\rfloor} (-1)^{k}\binom{n}{2k} 7^{k}
$$. How can I show that it is divisible by $2^{n - 1}$ for any positive integer $n$? I have attempted to write it in ...
- 15
0
votes
1
answer
46
views
Expectation by conditioning on an event (recursions)
My problem goes as follows : Consider $X_n$, where $n\geq1$, as the sequence of independent poisson r.v's with mean 5. Further, we define
$N$ = min{$n\geq3$ : $X_{n-2}=2$, $X_{n-1}=1$, $X_n$=0}
and ...
- 353
2
votes
0
answers
29
views
Recursion theorem in Boolean valued propositional logic [closed]
My question is quite simple: is Boolean valued prop logic a special case of the recursion theorem?
So, we have a finite set of propositional variables, inductive set of formulas constructed by some ...
- 21
0
votes
0
answers
111
views
For the following recurrence, sketch its recursion tree, and guess a good asymptotic upper bound on its solution.
T(n) = 4T(n/3)+n
Use the substitution method to verify the upper bound.
I have gotten this far, but I am unsure on how to proceed.
https://imgur.com/a/enxC2s4
- 1
0
votes
1
answer
102
views
Big-O complexity of a recurrence function $8 \cdot T(\frac{n}{4})+O(n\cdot\sqrt{n})$
An algorithm solves a problem of size $n$ by recursively calling
8 subproblems, with each subproblem of 1/4 the size of the original input.
It then combines their solutions to form the solution of the ...
- 11
7
votes
1
answer
119
views
Infinite series over recursive digit-counts
Given a positive integer $n,$ let $S(n)$ be the number of digits in the decimal expansion of $n,$ and let $$f(n)=n\cdot S(n)\cdot S(S(n))\cdot\ldots$$
Note that this is well-defined, since repeatedly ...
- 73
0
votes
2
answers
130
views
Proving inequality for a recurrence
The Question is as Follows:
Define the sequence of numbers Ai by:
A(0) = 2
$A\left(n+1\right)\ =\ \frac{A\left(n\right)}{2}+\frac{1}{A\left(n\right)}$ (for n≥ 1)
Prove that $A\left(n\right)\ \le\ \...
- 13
5
votes
0
answers
111
views
Given analytic $F(x)$ find $f(x)$ such that $\forall x. F(x) = f(f(x))$
Many years ago, I worked on the following problem. Given a real analytic function $F(x)$, find a continuously differentiable real function $f(x)$ such that $\forall{x}. F(x) = f(f(x))$. I was able to ...
1
vote
0
answers
54
views
Matching problem in a recursive way
Suppose there are $n$ people invited to a party. Seats are assigned and a name card is made for each guest. However, floral arrangements on the table unexpectedly obscure the name cards. When the $n$ ...
- 145
2
votes
1
answer
99
views
Identify $d$ heavy coins where $d$ is unknown.
You are given $N$ coins which look identical (assume $N = 2^k$). But actually some of them are pure gold coins (hence are heavy) and the rest are aluminum coins with thin gold plating (light). You are ...
- 165
0
votes
0
answers
48
views
Alternative characterisation of supremum
Given a sequence $\{b_j\}_{j\in\mathbb{N}}$, can we define $\alpha_k=\sup_{j\geq k} b_j$ for any $k\in\mathbb{N}$ recursively through $\alpha_j=\max\{b_j,\alpha_{j+1}\}$ for all $j\geq k$? I am able ...
- 878
0
votes
0
answers
21
views
How can I represent a decreasing summation which the highest value is the starting value?
I am trying to find the recurrence of
$ T(n) = 2T(n-1) + n^2$ The answer it's $O(2^n n^2)$ but now I'm trying to find the answer using recursion and all good, but trying to find $T(n-k)$ is killing ...
7
votes
2
answers
122
views
All terms of the sequence are "$x^2+(x+1)^2$"
Let $a_1=1$, $a_2=13$, and $a_{n+2}=14a_{n+1}-a_n$ for $n\in\Bbb N$. Prove that for all $a_i$, there exists $x\in\Bbb N$ such that $a_i=x^2+(x+1)^2$.
I listed the first few terms:
$$\begin{aligned}
...
- 841
0
votes
0
answers
28
views
Explicit formula for sequence where each term is the weighted average of adjacent terms
Consider the sequence $a_0, a_1, ..., a_{2n}$, where $a_0=0$, $a_{2n}=1$, and $a_i=wa_{i-1}+(1-w)a_{i+1}$ for all indexes $i\in [1, 2n-1]$. In other words, the first term of the sequence is 0, the ...
2
votes
2
answers
161
views
Showing permutation does not change output of commutative operation (recursion theorem)
(In what follows, NB that $\mathbb{N}^\times$ is the positive natural numbers, and $\mathbb{N}$ includes 0.)
I am working on Exercise 1 of Amann and Escher Analysis I, and the problem is essentially ...
- 1,221
1
vote
1
answer
66
views
Expected number of attemps to succeed
Suppose there are five levels $\{1,2,3,4,5\}$. Let $P_s(i)$ denote the probability of success on level $i$ and $P_f(i) = 1 - P_s(i)$ the probability of failure on level $i$. If you succeed on level $...
- 399
0
votes
0
answers
43
views
How to define multivariable double recursive function
I have a question for those who are familiar with recursion theory.
According to Wikipedia (https://en.wikipedia.org/wiki/Double_recursion),
Raphael M. Robinson called functions of two natural number ...
3
votes
0
answers
86
views
Given the definition of $a_0$ and $a_n$, what is $\lim_{x\to\infty}\frac{a_n}n$?
So I was looking through Youtube to see if there were, yet again, any math equations that I thought that I might like to solve when I came across this video by Michael Penn that was apparently "...
- 2,064
1
vote
1
answer
117
views
Putnam 2009 A4 : $S$ be a set of rational numbers such that if $x$ in $S$, then $x+1$ in $S$ and $x-1$ in $S$
Question
$
\text{Let } S \text{ be a set of rational numbers such that}
$
\begin{align*}
(a) &\ 0 \in S; \\
(b) &\ \text{If } x \in S, \text{ then } x+1 \in S \text{ and } x-1 \in S; \text{ ...
- 1,428
1
vote
1
answer
66
views
What field should I search to solve delay like equations?
I want to solve equations like:
$$
t f(t) + u(t-2) f(t-2) = \sin(t)
$$
It's like delay differential equations but without the derivative.
What field should I search in to solve this kind of equation?
- 1,134
1
vote
1
answer
46
views
Why does this given relation apply in this context?
I'm trying to understand some maths homework, but the meaning of one particular part is not clear to me.
The relevant parts of the task description go as follows (translated from its original language)...
- 177
1
vote
1
answer
49
views
Differentiating/integrating a function infinitely many times
Is there any meaning behind infinitely differentiating or integrating a function? Also, sure, this would cause most functions to either collapse to zero, blow up to infinity, oscillate infinitely (e.g....
