# Questions tagged [recurrences]

The recurrences tag has no usage guidance.

362
questions

5
votes

1
answer

295
views

### Reference for "trick" on guessing solutions to quadratic recurrences with differential equations

Consider the recurrence
$$g(h) = g(h-1) - \frac{1}{4}g(h-1)^2,$$
for $h \geq 0$ and $g(0)=1$. This recurrence occurs in many applications (For example fast minimum cut algorithms, the Galton-Watson ...

1
vote

0
answers

62
views

### Alternating sum of integer coefficients of the triangles related to Eulerian numbers and binomial transforms

Let $W(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n \leqslant 0$ or $k \leqslant 0$ such that
$$
W(n, k, m) = (k+m-1)W(n-1,...

6
votes

0
answers

224
views

### Searching for a proof of the pattern and identification of integer coefficients for the A329369

Please see the update given below. Everything you need to know from the old version of the question are the functions $a(n), \ell(n), s(n), t(n), r(n)$.
Let $a(n)$ be A329369 (i.e, number of ...

0
votes

0
answers

10
views

### Finding parameters of best approximating recursion

Question:
how can the initial values $\left(a[0],\,\dots,\,a[k-1]\right)$ and the coefficients $\left(c_k,\,\dots,\,c_0\right)$ be determined that solve
$\min\limits_{a[0],\dots,a[k-1]\\ c_k,\dots,...

6
votes

1
answer

357
views

### On A057985 and A287066

Let $a(n)$ be A057985 (i.e., start with $0$ and repeatedly substitute: $0 \to 01$, $1 \to 12$, $2 \to 0$).
Let $b(n)$ be A287066 (i.e., start with $1$ and repeatedly substitute: $0 \to 01$, $1 \to 12$...

2
votes

1
answer

244
views

### On a A089039 and pair of sequences with simple recursion

Let $a(n)$ be A089039 (i.e., number of circular permutations of $2n$ letters that are free of jealousy). Here
$$
a(n) = \sum\limits_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!(n-k-1)!^2}{(k-...

2
votes

0
answers

75
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

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

2
votes

1
answer

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

1
vote

1
answer

77
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

139
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

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

5
votes

3
answers

861
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

1
answer

101
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

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

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

159
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

61
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

92
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

67
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

196
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

165
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
vote

1
answer

86
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

71
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

254
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

265
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

63
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

145
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

378
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

106
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

140
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

131
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

90
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

117
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 $\...

3
votes

0
answers

117
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

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

3
votes

0
answers

68
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

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