Questions tagged [recurrences]
The recurrences tag has no usage guidance.
358
questions
1
vote
0
answers
36
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) + \...
0
votes
0
answers
12
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
59
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 ...
-1
votes
0
answers
45
views
Recurrence involving a convolution-like sum
During a research we are finding several sequences $g_n$ which are defined by recurrences of the form:
$$g_n=\sum_{k=1}^{n-1} a_{k,n} g_k g_{n-k}$$
For some sequence $a_{n,k}$ (usually defined by a ...
5
votes
3
answers
843
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(...
1
vote
0
answers
37
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 ...
0
votes
0
answers
44
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) = ...
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}\...
2
votes
1
answer
139
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}{...
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 $...
1
vote
1
answer
89
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)...
2
votes
0
answers
65
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 ...
6
votes
0
answers
192
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 ...
6
votes
1
answer
157
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}}\...
4
votes
0
answers
163
views
Growth rate of a recursively defined sequence
For a side project with a friend (having to do with fractional iterates of the exponential function), we're looking at a sequence $a_n$ defined recursively by equations $a_1 = 1$ and
$$a_n = \sum_{k=1}...
1
vote
1
answer
84
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
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, ...
0
votes
0
answers
67
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 ...
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, ...
5
votes
1
answer
243
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_{\...
1
vote
2
answers
233
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 ...
2
votes
0
answers
61
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)$-...
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$ ...
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 ...
0
votes
1
answer
139
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 ...
1
vote
2
answers
374
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(...
0
votes
0
answers
103
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 ...
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&...
2
votes
0
answers
122
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}
...
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\...
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)
$$
...
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)) ...
1
vote
0
answers
115
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 $\...
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 ...
1
vote
0
answers
67
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 $...
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)}
$$
...
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 ...
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 ...
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 ...
0
votes
1
answer
217
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}...
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 ...
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, ...
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-...
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\...
0
votes
0
answers
67
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}...
4
votes
0
answers
117
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
...
0
votes
0
answers
100
views
Recursion for the A266328 by analogy with non-standard recursion for factorials
Let $a(n)$ be A266328 i.e. an integer sequence with exponential generating function
$$
A(x)=\exp\int B(x) \,dx
$$
such that
$$
B(x)=\exp(-x)\exp\int A(x) \,dx
$$
where the constant of integration is ...
7
votes
1
answer
746
views
Remarkable recursions for the A204262
Let $a(n)$ be A204262 i.e. permanent of the matrix $n\times n$ with elements $\min(i,j)$.
Let
$$
f_{n,\ell}(x)=g_{n,\ell}(x)+f_{n,\ell-1}(\ell)-g_{n,\ell}(\ell), \\
g_{n,\ell}(x)=\int (n-\ell)^2 f_{n-...
1
vote
0
answers
104
views
Recursion for the Bessel polynomial $y_n(x)$
Let $a(n)$ be A001515 i.e. the Bessel polynomial $y_n(x)$ evaluated at $x=1$. Here
$$
a(n) = (2n-1)a(n-1) + a(n-2), \\
a(0) = 1, a(1) = 2
$$
The closed form is
$$
a(n)=\sum\limits_{k=0}^{n}\binom{n+k}{...