Questions tagged [recurrences]
The recurrences tag has no usage guidance.
361
questions
2
votes
0
answers
60
views
Sum of terms in a recurrence relation
Problem: Fix a $T \in \mathbb{N}$ and consider the recurrence $a_{r + 1} = a_{r} + a_{r} ^ {2}$, where $r \in \mathbb{N}_{\ge 0}$ and $a_{0} = \frac{1}{T}$. Prove that $\sum_{r = 0} ^ {T - 1} a_{r} = \...
0
votes
0
answers
38
views
Solving non-linear recursion with linear and exponential terms
I encountered the recursion $$\frac{a[n+2]}{a[n+1]}-e^{-\frac{a[n+1]}{a[n]}}=0$$ when trying to explain why points are apparently arranged along an exponential curve in the scatter plot of an empiric ...
- 12.7k
0
votes
0
answers
56
views
Geometric intuition behind hyper-sphere volume recurrence relation [closed]
There is a recurrence relation for calculating the volume of a hyper-sphere and a logical explanation for why it holds, as well as other explanations here on MO. Is there a geometric intuition behind ...
- 1
2
votes
1
answer
101
views
Recursion for the Chebyshev transform of $m^n$
Let
$$
R(n, q, m) = R(n-1, q+1, m) + \sum\limits_{j=0}^{q} (-1)^{q-j}R(n-1, j, m), \\
R(0, q, m) = (m-1)^q
$$
I conjecture that $R(n, 0, m)$ is a Chebyshev transform of $m^n$.
Examples of Chebyshev ...
- 3,474
1
vote
1
answer
71
views
Closed form for a linear recurrence relation of varying order
In my research I have come across a recurrence relation that is of varying order. The relation is as follows:
$$
\begin{cases}
f_0=f_1=0,\\
f_2=1,\\
\bigg(f_{2\rho}=\displaystyle \sum_{i=0}^{\rho}...
1
vote
1
answer
126
views
Bound on a two-dimensional recursive series
For $n,k\in\mathbb{N}$, let $f(n,k)$ be defined as follows.
If $n \geq k$ and $n > 2$, then
$$
f(n,k) = \frac{k(n-k)}{n(n-1)}f(n-2,k-1) + \frac{k(k-1)}{n(n-1)}f(n-2,k-2) + \frac{n-k}{n}f(n-1,k) + \...
- 145
0
votes
0
answers
13
views
Understanding relation of 2 dependent, integral equations which are nested in a Bayesian Expectation
I'm trying hard to try understand the recursive nature between two equations in a recent macroeconomics paper, but my question mainly relates to how mathematically such recursive equations can depend ...
1
vote
0
answers
63
views
On a numbers $k$ with specific $2$-adic valuation
Let $a(n)$ be A002326 (i.e., multiplicative order of $2 \operatorname{mod} 2n+1$).
Let $b(n)$ be A179382 (i.e., the smallest period of pseudo-arithmetic progression with initial term $1$ and ...
- 3,474
5
votes
3
answers
847
views
How to find the coefficient of $x^k$ in the expression $\prod_{p=1}^n (x^p+1)^p$?
I tried to find the indefinite integral
$$ f_n(x)=\int \prod_{k=1}^n \cos^k(kx) \, dx$$
by using Euler's formula and put $x=\frac{\ln y}{2i}$ I got
$$ f_n(x)=-i2^{-\frac{n(n+1)}{2}-1}\int y^{-\frac{n(...
- 431
1
vote
1
answer
92
views
Recurrence relation quicksort median-of-three
I am looking for a recurrence relation that describes the average number of comparisons of the quicksort algorithm considering an input array of size $n$. If the pivot element is picked randomly, the ...
- 125
0
votes
0
answers
45
views
$R$-recursion for the A007165
Let $a(n)$ be A007165 i.e. number of $P$-graphs with $2n$ edges. Here ordinary generating function $A(x)$ satisfies
$$
A(x) = \frac{(1 + xA(x))(1 + 2xA(x))}{1 + 2xA(x) - (xA(x))^2}
$$
Let
$$
R(n, q) = ...
- 3,474
1
vote
0
answers
48
views
$R$-recursion for the A036765
Let $a(n)$ be A036765 i.e. number of ordered rooted trees with $n$ non-root nodes and all outdegrees $\leqslant 3$. Here
$$
a(n) = \frac{1}{n+1}\sum\limits_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\...
- 3,474
2
votes
1
answer
156
views
$R$-recursion for the A143017
Let $a(n)$ be A143017 i.e. number of $\{2-1-3, 2'^e-31\}$-avoiding permutations of size $n$ (see definition in the Elizalde paper). Here
$$
a(n) = \frac{1}{n}\sum\limits_{k=0}^{\left\lfloor\frac{n}{...
- 3,474
0
votes
0
answers
58
views
Linear recurrences in coefficients of powers of quotients of polynomial rings
It is known that linear recurrences with constant coefficients
can be computed via powers in $\mathbb{Z}[x]/f(x)$.
We believe that this generalizes to quotients of multivariate polynomial
rings.
Let $...
- 24.2k
1
vote
1
answer
91
views
General case of the some $R$-recursions
Let $f(n)$ be an arbitrary function.
Let $a(n)$ be an integer sequence such that its ordinary generating function satisfies
$$
A(x)=\sum\limits_{i=0}^{\infty}\frac{x^i}{\prod\limits_{j=0}^{i}(1-f(j)x)...
- 3,474
2
votes
0
answers
66
views
Set partitions with big blocks - real-rooted polynomials?
The polynomials
$$
T_n(t) := \sum_{\pi \in \text{Set Partitions}(n)} t^{\text{blocks}(\pi)} = \sum_{k=1}^n S(n,k)t^k
$$
with $S(n,k)$ being the Stirling numbers of the second kind, are well-known to ...
- 15.6k
6
votes
0
answers
193
views
Filling in some missing squares for classes of power series
This question concerns various important classes of formal power series. For concreteness and convenience, let us work with power series $F(x) = \sum_{n\geq 0}c_n x^n \in \mathbb{C}[[x]]$, i.e., with ...
- 22.9k
6
votes
1
answer
158
views
About the high-order derivatives of Lambert function
In the mid seventies, in my former research group, we found that the $n^{\text{th}}$ derivative of $W_0(x)$ could write
$$\frac {d^n\,W_0(x)}{dx^n}=(-1)^{n+1}\,\,\frac{\,P_n(w)}{ e^{nw}\,(1+w)^{2n-1}}\...
- 1,422
1
vote
1
answer
85
views
$R$-recursion for the A307389
Let $a(n)$ be A307389 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x)=\exp\left(\frac{\exp(2x)-2\exp(x)+2x+1}{2}\right)
$$
The sequence begins with
$$
1,...
- 3,474
3
votes
0
answers
69
views
$R$-recursion for the A249833 (similar to A235129)
Let $a(n)$ be A249833 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x) = 1 + \int A(x) + (A(x))^2\log A(x)\,dx
$$
The sequence begins with
$$
1, 1, 2, 7, ...
- 3,474
0
votes
0
answers
70
views
Urn model and recursion
We have an urn with $n$ white balls. In each iteration we pick a ball at random. If it's white, we paint it red and return it to the urn. If it's already red, we discard it. We lose the game if (after ...
- 298
2
votes
0
answers
102
views
$R$-recursion for the A235129
Let $a(n)$ be A235129 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A'(x) = 1 + A(x)\exp(A(x))
$$
The sequence begins with
$$
1, 1, 3, 12, 64, 424, 3358, ...
- 3,474
5
votes
1
answer
248
views
Precise asymptotic estimate of a recurrence sequence involving a square root
Consider a recurrence sequence defined like this:
$$ \begin{cases} x_0 = \varepsilon \\
x_{n+1} = x_n + \varepsilon \sqrt{x_n}.
\end{cases}$$
I am interested in estimating the value of $x_{\...
- 631
1
vote
2
answers
249
views
Recurrence relation with two variables
I am stuck on a recurrence relation with two variables. I'm familiar with techniques to solve recurrence relations with one variable and looked into ways to solve recurrence relations with multiple ...
- 43
2
votes
0
answers
62
views
Elementary recursion for the A258173
Let $a(n)$ be A258173 i.e. sum over all Dyck paths of semilength $n$ of products over all peaks $p$ of $y_p$, where $y_p$ is the $y$-coordinate of peak $p$.
A Dyck path of semilength $n$ is a $(x,y)$-...
- 3,474
27
votes
5
answers
3k
views
How to show a function converges to 1
Consider the following recurrence relation in two variables:
$$f(a, b) = \frac{a}{a+b} f(a-1,b)+ \frac{b}{a+b}f(a+1,b-1) $$
for positive integers $a$ and $b$,
with the boundary conditions $f(0,b)=0$ ...
- 3,195
1
vote
1
answer
81
views
Formulas for partial composed product
Let $A(x) = \prod\limits_i (x-\lambda_i)$ and $B(x) = \prod\limits_j (x-\mu_j)$. Then, their composed product is defined as
$$
(A*B)(x) = \prod\limits_{i,j} (x-\lambda_i \mu_j).
$$
Generally, we can ...
- 1,141
0
votes
1
answer
142
views
Diophantine equations involving recurrence sequences
I am working on a Diophantine equation by using transcendental and reduction methods given by Baker and Davenport. However, when I read some papers i don't understand the reduction step, for example ...
- 31
1
vote
2
answers
375
views
Solving a recurrence relation for the prime counting function?
I have found some number sequence $c_n = 1+b_n$ for $n \ge 0$, where $b_n = $ A307977(n).
I am trying to solve the following recurrence relation for the prime counting function:
$$\forall n \ge 3: \pi(...
- 2,462
0
votes
0
answers
104
views
A surprising result with the Riccati difference equation
I was looking at the Riccati difference equation with positive and negative indices
$$
R_n=\frac{aR_{n-1}+b}{cR_{n-1}+d}\quad n\in[0,N]\\
R_n=\frac{-dR_{n+1}+b}{cR_{n+1}-a}\quad n\in[-N,0]\\
$$
along ...
- 119
0
votes
0
answers
138
views
Dark side of the self-inverse permutation
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
f(n) = 2^{\ell(n)}
$$
Let $p_1(n)$ be an arbitrary self-inverse permutation of the non-negative integers such that $p_1(n)<2^k$ iff $n&...
- 3,474
2
votes
0
answers
128
views
Asymptotics of a "non-constant order" quadratic recurrence relation in two variables
Consider the following recurrence relation defined for two integer variables $H,n \geq 0$:
\begin{equation}
\gamma(H,n) = \sum_{K=0}^{\lfloor H/2 \rfloor} \gamma(K,n-1) \gamma(H-K,n-1)
\end{equation}
...
- 133
0
votes
0
answers
68
views
Recursions for the A111528
Let $T(n,k)$ be A111528 i.e. square table, read by antidiagonals, where the g.f. for row $n+1$ is generated by
$$
xg_{n+1}(x) = \frac{1}{n+1}\left(1+nx - \frac{1}{g_n(x)}\right), \\
g_0(x) = \sum\...
- 3,474
2
votes
0
answers
89
views
Unexpected recursion for the A193231 (blue code of $n$)
Let $a(n)$ be A193231, blue code of $n$ i.e. self-inverse permutation of non-negative integers such that $a(n)<2^k$ iff $n<2^k$ and
$$
a(n\operatorname{XOR}k) = a(n) \operatorname{XOR} a(k)
$$
...
- 3,474
1
vote
1
answer
105
views
Property of some permutations of non-negative integers such that $a(n)<2^k$ iff $n<2^k$
Let
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
f(n) = 2^{\ell(n)}
$$
Let $q_1(n)$ and $q_2(n)$ be an arbitrary self-inverse permutations of non-negative integers (that is, $q_i(q_i(n)) ...
- 3,474
1
vote
0
answers
116
views
Inequality concerning the imaginary parts of a recurrent sequence, Laplacian eigenvectors
Let $u=(u_1,\dots,x_n)\in\mathbb{C}^n$ be a sequence that satisfies the cyclic recurrence
$$
\lambda+1 =a_{i-1}\frac {u_{i-1}}{u_i} + (1-a_{i+1})\frac{ u_{i+1} }{u_i }
$$
with $a_i \in (0,1)$ and $\...
- 650
2
votes
0
answers
88
views
Closed form from a slightly modified recursion for transposed Catalan triangle
Let $a_1(n)$ be A000108, i.e. Catalan numbers. Here
$$
a_1(n)=\frac{1}{n+1}\binom{2n}{n}
$$
Let $a_2(n)$ be A059715, i.e. number of multi-directed animals on the triangular lattice. From OEIS page we ...
- 3,474
1
vote
0
answers
68
views
gcd of elements of associated binary recurrence sequences
On page 55 of the 3rd edition of Ribenboim's ``The New Book of Prime Number Records'', he defines two associated sequences, $U_n(P,Q)=\left( \alpha^n-\beta^n \right)/\left( \alpha-\beta \right)$ and $...
- 43
3
votes
0
answers
67
views
Sequence that sum up to A343685
Let $a(n)$ be A343685 i.e.
$$
a(n)=2na(n-1)+\sum\limits_{j=0}^{n-1}\binom{n}{j}(n-j-1)!a(j), \\
a(0)=1
$$
Here the exponential generating function $A(x)$ satisfy
$$
A(x)=\frac{1}{1-2x+\log(1-x)}
$$
...
- 3,474
1
vote
0
answers
22
views
One-step vectorial recurrence into multi-step scalar recurrence on commutative rings with boundary conditions
Introduction over unbounded domain
Consider the forward time shift $\mathsf{z}$ acting on a discrete function of time (sequence) $f=(f^n)_{n\in\mathbb{N}}$ as $(\mathsf{z} f)^{n} = f^{n+1}$. Also ...
- 11
1
vote
0
answers
67
views
Simplification of computing $f(n,z)$
Let
$$
s(n,z)=\sum\limits_{j=0}^{n}L(n,j,z)
$$
where
$$
L(n,j,z)=\sum\limits_{p=0}^{n-j-1}f(p,z)L(n-j-1,p,z), \\
L(n,n,z)=1
$$
Now let $s(n,z)$ be an arbitrary function such that $s(0, z)=1$. It means ...
- 3,474
0
votes
0
answers
95
views
Useful recursion for A059715
Let
$$
R(n,q,m,k,z)=R(n-1,q+1,m,k,z)+\sum\limits_{j=0}^{q}\binom{q+m}{j+k}z^{q-j}[z^j]R(n-1,j,m,k,z), \\
R(0, q, m, k,z)=1
$$
Let
$$
R(n,0,m,k,z)=\sum\limits_{j=0}^{n}T(n,j,m,k)z^j
$$
I conjecture ...
- 3,474
0
votes
1
answer
220
views
Finding a strictly increasing Collatz sequence of arbitrary length [closed]
Is there a formula to construct a Collatz (3x + 1) sequence of arbitrary length that is strictly increasing? Obviously one can do this with a strictly decreasing sequence by just taking $2^n$ but I ...
1
vote
0
answers
100
views
Mysterious recursion for the A005225
Let $a(n)$ be A005225 i.e. number of permutations of length $n$ with equal cycles. Here
$$
a(n)=n!\sum\limits_{d|n}\frac{1}{d!(\frac{n}{d})^d}
$$
Let
$$
R(n,q,z)=(q+1)R(n-1,q+1,z)+\sum\limits_{j=0}^{q}...
- 3,474
0
votes
0
answers
51
views
Equivalence of recursions for A145879
Let $R_1(n,z)$ be row polynomials of A145879 i.e. of triangle read by rows: $T(n,k)$ is the number of permutations of $\left\lbrace 1,2,\cdots,n \right\rbrace$ having exactly $k$ entries that are ...
- 3,474
1
vote
0
answers
85
views
Suitable recursion for the A234289
Let $a(n)$ be A234289 i.e. integer sequence with exponential generating function
$$
A(x)=1+A(x)^2\int \frac{1}{A(x)}\,dx
$$
The sequence begins with
$$
1, 1, 3, 17, 147, 1729, 25827, 468593, 10012083, ...
- 3,474
1
vote
0
answers
95
views
Pretty simple recursion for the A290383
Let $a(n)$ be A290383 i.e. number of set partitions of $[n]$ such that the smallest element of each block is odd. Here
$$
a(n)=b(n,0,0)
$$
where
$$
b(n,m,t)=\sum\limits_{j=1}^{m-t+1}b(n-1,\max(m,j),1-...
- 3,474
1
vote
0
answers
77
views
Recursion for the A006014 using difference of binomial coefficients
Let $a(n)$ be A006014 i.e.
$$
a(n)=na(n-1)+\sum\limits_{j=1}^{n-2}a(j)a(n-j-1), \\
a(1)=1
$$
Also generating function $A(x)$ satisfies
$$
A(x) = x(1 + A(x) + A(x)^2 + xA'(x))
$$
Let
$$
R(n,q)=\sum\...
- 3,474
0
votes
0
answers
69
views
Recursion for a given series reversion
Define the operator $\operatorname{SR}$, which is associated with the series reversion.
Let $a(n,m,k)$ be an integer sequence with generating function
$$
\frac{1}{x}\operatorname{SR}(x\frac{1-mx}{1-kx}...
- 3,474
4
votes
0
answers
118
views
Something (which might be called multi-continued fraction) for the A112487
Let $a(n)$ be A112487 i.e. an integer sequence with exponential generating function
$$
A(x)=\exp\left(\int (A(x)+A(x)^2)\,dx\right), \\
A(0)=1
$$
However, the definition in the name of the sequence is
...
- 3,474