Questions tagged [recurrences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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) + \...
macat's user avatar
  • 145
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 ...
Justin Lee's user avatar
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 ...
Notamathematician's user avatar
-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 ...
user3141592's user avatar
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(...
Faoler's user avatar
  • 431
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 ...
Martin Clever's user avatar
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) = ...
Notamathematician's user avatar
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}\...
Notamathematician's user avatar
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}{...
Notamathematician's user avatar
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 $...
joro's user avatar
  • 24.2k
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)...
Notamathematician's user avatar
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 ...
Per Alexandersson's user avatar
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 ...
Sam Hopkins's user avatar
  • 22.5k
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}}\...
Claude Leibovici's user avatar
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}...
Todd Trimble's user avatar
  • 52.3k
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,...
Notamathematician's user avatar
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, ...
Notamathematician's user avatar
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 ...
leonbloy's user avatar
  • 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, ...
Notamathematician's user avatar
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_{\...
tommy1996q's user avatar
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 ...
user675763's user avatar
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)$-...
Notamathematician's user avatar
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$ ...
Simd's user avatar
  • 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 ...
Oleksandr  Kulkov's user avatar
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 ...
Omega's user avatar
  • 31
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(...
mathoverflowUser's user avatar
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 ...
Cye Waldman's user avatar
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&...
Notamathematician's user avatar
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} ...
dmitry's user avatar
  • 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\...
Notamathematician's user avatar
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) $$ ...
Notamathematician's user avatar
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)) ...
Notamathematician's user avatar
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 $\...
Artemy's user avatar
  • 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 ...
Notamathematician's user avatar
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 $...
user512026's user avatar
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)} $$ ...
Notamathematician's user avatar
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 ...
94thomas's user avatar
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 ...
Notamathematician's user avatar
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 ...
Notamathematician's user avatar
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 ...
NotAGhost's user avatar
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}...
Notamathematician's user avatar
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 ...
Notamathematician's user avatar
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, ...
Notamathematician's user avatar
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-...
Notamathematician's user avatar
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\...
Notamathematician's user avatar
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}...
Notamathematician's user avatar
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 ...
Notamathematician's user avatar
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 ...
Notamathematician's user avatar
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-...
Notamathematician's user avatar
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}{...
Notamathematician's user avatar

1
2 3 4 5
8