Questions tagged [recurrences]
The recurrences tag has no usage guidance.
357
questions
1
vote
0
answers
57
views
Convergence of stochastic linear recurrences
Suppose that $\zeta_t$ is a univariate, stationary stochastic process ($t\in\mathbb{N}^+$).
Let $x_0\in\mathbb{R}^n$, and let $f:\mathbb{R}\rightarrow\mathbb{R}^{n\times n}$ be a continuously ...
2
votes
0
answers
70
views
Recursion for the number of partitions of $m^n-1$ into powers of $m$
Let $a(n,m)$ be the number of partitions of $m^n-1$ into powers of $m$. In other words,
$$a(n,m)=[z^{m^n-1}] \prod\limits_{k\geqslant 0} \frac{1}{1-z^{m^k}}$$
Let
$$
R(n,m,q)=\sum\limits_{j=0}^{m(q+1)-...
0
votes
0
answers
59
views
A recurrence relation with two variables
How to solve the following recurrence relation?
$$f(i,j) = 2 f(i,j-1) + (\alpha^j+\beta^j) f(i-1,j), 0<\alpha,\beta < 1$$
With the boundary condition
$$ f(0,0) = f(1,0) = f(0,1) = 1 $$
A special ...
1
vote
0
answers
89
views
Combinatorial interpretation for the more general case of $R(n,0)$
Let $f(n), g(n,m), h(n)$ be an arbitrary functions which equal to the non-negative integers.
Let
$$
R(n,q) = \sum\limits_{j=0}^{f(q)}g(q,j)R(n-1,j),\\
R(0,q) = h(q)
$$
In the comment to the one of ...
0
votes
0
answers
169
views
Expansion of continued fraction using recursion
Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.
Let $a(n)$ be an integer sequence with generating function $\frac{1}{G(0)}$ where
$$
G(j)=1-\frac{f(j)x}{G(j+1)}
$$
Here we have
$$
G(...
26
votes
1
answer
7k
views
Elegant recursion for A301897
Let $a(n)$ be A301897, i.e., number of permutations $b$ of length $n$ that satisfy the Diaconis-Graham inequality $I_n(b) + EX_n(b) \leqslant D_n(b)$ with equality. Here
$$a(n)=\frac{1}{n+1}\binom{2n}{...
2
votes
0
answers
124
views
Recurrence for A004208
Let $a(n)$ be A004208. Here
$$a(n)=n\prod\limits_{j=1}^{n}(2j-1)-\sum\limits_{i=1}^{n-1}a(i)\prod\limits_{j=1}^{n-i}(2j-1)$$
I conjecture that
$$a(n)=R(n-1,0)$$
where
$$R(n,q)=2(q+2)R(n-1,q+1)+\sum\...
0
votes
0
answers
63
views
General patterns for partial sums of generalized A341392, A284005 and A329369
Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
$$f(n)=n-2^{\ell(n)}$$
$$\operatorname{wt}(2n+1)=\operatorname{wt}(n)+1, \operatorname{wt}(2n)=\operatorname{wt}(n), \operatorname{wt}(0)=0$$
$$T(n,k)=...
0
votes
0
answers
71
views
Sequences that sum up to possible generalization of Euler or up/down numbers (A000111)
Let $a(n,m,k)$ be an integer sequence with e.g.f.
$$A(x)=\operatorname{exp}\left(x + m\int\int (A(x))^k \, dx \, dx\right)$$
I don't know much about integrals, so here's a concrete example:
$a(n,1,3)$...
3
votes
0
answers
204
views
Using Ramanujan-type "Legendrian" sequences to find new formulas for $\frac1{\pi}$?
I. Recurrences
(Continued from this post.) In Cooper's 2012 paper, "Sporadic sequences, modular forms and new series for 1/π", he did a computer search for the recurrence relation,
$$(n+1)^3 ...
5
votes
1
answer
174
views
On four Ramanujan-type "Legendrian" sequences with a 3-term recurrence?
I. Recurrences
In a previous post, it was mentioned how Almkvist-Zudilin did a computer search for solutions to the recurrence relation,
$$(n+1)^3s_{n+1}=(2n+1)(an^2+an+b)s_n+c\,n^3s_{n-1}$$
within a ...
1
vote
0
answers
88
views
Application of the series reversion
Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.
Let $a(n)$ be an arbitrary integer sequence such that $a(0)=1$.
Let $b(n)$ be an integer sequence such that
$$b(2^m(2n+1))=\sum\...
7
votes
0
answers
419
views
On H. Cohen's four continued fractions for $\zeta(3), \zeta(5), \zeta(7)$?
After 6 years from this old MO post, I finally find in the literature polynomials of deg-$5$ for the continued fraction of $\zeta(5)$.
I. Recurrences involving $\zeta(5)$
In Cohen's 2022 paper, ...
0
votes
0
answers
98
views
Simplification of summation and reverse search
Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.
Let $b(n)$ be an integer sequence such that
$$b(2^m(2n+1))=\sum\limits_{k=0}^{m}f(m-k)b(2^kn), b(0)=1$$
Let $s(n,m)$ be an integer ...
10
votes
2
answers
648
views
On 12 cfracs: for Catalan's $K$, Gieseking's $\kappa$, and $\pi^2$, $\pi^3$, plus three for $\zeta(3)$ using Zagier's "six sporadic sequences"
I. Some functions
As these will be used in the continued fraction evaluations below, recall the Riemann zeta function $\zeta(s),$ and Dirichlet beta function $\beta(s),$
$$\beta(s) = \sum_{n=1}^\infty\...
1
vote
0
answers
36
views
Sequences that sum up to $\frac{m^{n+1}}{n+1}\binom{2n}{n}{}_2F_1(1,n+\frac{1}{2}; n+2; -4m(m-1))$
Let $a(n,m)$ be an integer sequence such that
$$a(n,m)=\frac{m^{n+1}}{n+1}\binom{2n}{n}{}_2F_1(1,n+\frac{1}{2}; n+2; -4m(m-1))$$
Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
$$f(n)=n-2^{\ell(n)}$$...
2
votes
2
answers
352
views
Finding a new level-$7$ pi formula using the relation $j_{7A}(\tau) = \left(\sqrt{j_{7B}(\tau)}+\frac{7}{\sqrt{j_{7B}(\tau)}}\right)^2$
(Note: This third method continues from this post.)
There are level-$7$ pi formulas based on the McKay-Thompson series $T_{7A}$ and Cooper's $s_7$ sequence in this paper. This third method, among ...
0
votes
0
answers
34
views
$\frac{m(m+k+1)^n+k}{m+k}$ as closed form for subsequence of the partial sums
Let $a(n,m,k)$ be an integer sequence such that
$$a(n,m,k)=\frac{m(m+k+1)^n+k}{m+k}$$
There are many sequences in the OEIS that are special cases of a given sequence family:
$a(n,1,1)$ - A007051
$a(n,...
1
vote
0
answers
57
views
Counting problem, tiling rectangle with two types right isosceles triangle
How many ways are there to tile a rectangle of size $m\times n$ with two types of isosceles triangle, type 1 having area $\frac{1}{2}$ and type 2 having area 1?
I know with only type 1 there are $2^{...
0
votes
0
answers
59
views
Existence of integer sequence under simultaneous constraints
Does there exist a function $f:\Bbb N\to\Bbb N$ such that \begin{align}a_{n+1}&=f(a_n)\\a_{f(n)+1}&=a_n\end{align} implies $\{a_n\}_{n\ge0}$ is a non-constant, positive integer sequence? ...
0
votes
0
answers
35
views
Representation theorem for multivariate homogeneous linear recurrences on Z^d?
Let $f:\mathbb{Z}^d \to \mathbb{C}$ satisfy a homogeneous linear recurrence for some coefficients $a_\Delta \in \mathbb{C}$,
$$\forall x \in \mathbb{Z}^d. \quad \sum_{\Delta \in B_k(0)}a_\Delta f(x+\...
2
votes
0
answers
169
views
Solve the recurrence relation with 2 variables
We have the following recurrence relation:
\begin{equation}
f(n,m) = f(n-1,m) g_{\alpha, \gamma}(n,m) + f(n,m-1) g_{\beta, \gamma}(n,m) \\
g_{\alpha, \gamma}(n,m)= \sum^{n}_{i = 0} \sum^{m}_{j = 0} \...
0
votes
0
answers
40
views
Product as closed form for subsequence of the partial sums
Let $a(n,m,k)$ be an integer sequence such that
$$a(n,m,k)=\prod\limits_{q=0}^{n-1}\sum\limits_{i=0}^{m-1}\sum\limits_{j=0}^{m-i-1}\binom{i+j-1}{j}k^{i+j}q^i$$
Let
$$\ell(n,m)=\left\lfloor\log_m n\...
7
votes
0
answers
79
views
Generalization of Lucas sequences to order 3 (and above)
For fixed integer parameters $(P,Q)$, Lucas sequences represent a pair of complimentary integer sequences satisfying the same recurrence with the characteristic polynomial $f(x):=x^2 - Px + Q$. The ...
0
votes
0
answers
67
views
On a generalization of A113227 as a subsequence of the partial sums
This question is just a generalization of the one of my previous questions.
Let
$$a(n,m,k)=\sum\limits_{i=1}^{n}u(n,m,k,i)$$
where
$$u(n,m,k,i)=u(n-1,m,k,i-1)+(m-1)(i+k-1)\sum\limits_{j=i}^{n-1}u(n-1,...
6
votes
1
answer
426
views
How to solve recurrence relation with 2 variables?
I have the following recurrence relation and boundary condition?
$$
f(n,m) = \frac{\alpha n}{n+m} f(n-1,m) + \frac{\beta m}{n+m} f(n,m-1) + 1
$$
$$
f(n,0) = \frac{1-\alpha^{n+1}}{1-\alpha}, f(0,m) = \...
2
votes
0
answers
47
views
Coefficient growth upper bound of a recurrence relation
Consider the recurrence relation one can obtain from the radial Schrödinger equation for the hydrogen atom, where $\psi(r)=\sum_{n=0}^{\infty} a_nr^n$:
$$(n+3)(n+2)a_{n+2}+2a_{n+1}=2|E|a_n, n\geq0$$
...
4
votes
0
answers
85
views
Closed form for subsequence of the partial sums of generalized A329369
Let $a(n,m,k)$ be an integer sequence such that
$$a(n,m,k)=\sum\limits_{i=0}^{n}{n\brace i}(m-k)^{n-i}\prod\limits_{j=0}^{i-1}(kj+1)$$
Here ${n\brace k}$ is the Stirling number of the second kind.
...
3
votes
1
answer
130
views
Sequences that sum up to Dowling numbers
Let $a(n,k)$ be the sequence of $k$-Dowling numbers (for more information see A007405 and its CROSSREFS section) with e.g.f.
$$\operatorname{exp}\left(x + \frac{\operatorname{exp}(kx) - 1}{k}\right)$$
...
2
votes
0
answers
102
views
Sequences that sum up to the many sequences in the OEIS
Let
$$a(n,m,k)=\frac{1}{n}\sum\limits_{j=0}^{n}[n+kj\geqslant 0]\binom{n}{j}\binom{n+kj}{j-1}(m-1)^{j-1}$$
Here square brackets denote Iverson brackets.
There are many sequences in the OEIS that are ...
6
votes
1
answer
254
views
Sequence that sums up to the number of permutations avoiding the pattern $1-23-4$
Let $a(n)$ be A113227, i.e., the number of permutations on $[n]\equiv \{1, \ldots, n\}$ avoiding the pattern $1-23-4$.
The sequence begins with
$$1, 1, 2, 6, 23, 105, 549, 3207, 20577, 143239, 1071704,...
1
vote
0
answers
53
views
Recurrence for the number of permutations with a given excedance set
Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
$$f(n)=n-2^{\ell(n)}$$
$$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2$$
$$\operatorname{wt}(2n+1)=\operatorname{wt}(n)+1, \...
1
vote
0
answers
132
views
Recurrence for the A284005
Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
$$f(n)=n-2^{\ell(n)}$$
$$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2$$
$$\operatorname{wt}(2n+1)=\operatorname{wt}(n)+1, \...
5
votes
1
answer
210
views
Polynomial solutions to a difference equation
This question may look unmotivated, but is connected with continued fractions for $\pi^2$.
Let $n$ be a nonnegative integer, and consider the difference equation
$$(x+2n+4)(x+n+1)P(x+1)-(x-1)(x+n-1)P(...
1
vote
0
answers
76
views
Urn model with delayed replacement
Suppose I have x red and y blue balls. At each timestep I draw a ball with probability $$P(\text{red ball}) = (x/(x+y))^z, P(\text{blue ball}) = 1-P(\text{red ball})$$ where z is fixed.
Each ball is ...
1
vote
0
answers
83
views
Permutation to get Stolarsky representation from lazy Fibonacci (dual Zeckendorf) representation
Let $a_1(n)$ be A200714, i.e., Stolarsky representation interpreted as binary to decimal integers. The sequence begins with
$$0, 1, 3, 2, 7, 5, 6, 15, 4, 11, 13, 14, 31, 10, 9, 23, 12, 27, 29$$
Let $...
2
votes
0
answers
67
views
Methods for holonomic recurrences
I wanted to ask if anyone knows of good texts/resources on methods for solving holonomic recurrence relations (if there are any general analytical approaches):
$$p_1(n)a(n)+p_2(n)a(n-1)+\dotsb+p_k(n)a(...
1
vote
0
answers
35
views
The limit set of consecutive applications of linear transforms to the single segment
Problem. Consider $n$ positive integers $1 < a_1\le \ldots \le a_n$ and $I = \left[\frac{1}{a_n - 1}, \frac{1}{a_1 - 1}\right]$. For each $a_k$ define the linear transform $\phi_k\colon x\mapsto \...
-4
votes
1
answer
286
views
Limit of recursion relation
Consider the sequence of functions $\{F_n\}_{n\in \mathbb{N}}$, where each $F_n$ is defined on $\{0,...,n\}$ by recurrence of the following form: $$ F_n(0)=3 \textrm{
and }F_n(k)=\frac{1}{k^2}+\frac{\...
3
votes
1
answer
210
views
Powers of $2$ up to $2^{m-1}$ from a polynomial of degree $m-1$
Let $T(n,k)$ be a triangle of coefficients such that $T(n,k)\geqslant0$ for $n>0$, $0<k\leqslant n$, $0$ otherwise. Also
$$T(2n+1,1)=\frac{1}{2n+1}, T(2n,1)=0$$
$$T(n,k)=\frac{1}{n}(T(n-1,k-1)+(...
2
votes
0
answers
93
views
Identifying terms of a linear recurrence sequence using a congruence
Let $(n_i)_{i=0}^\infty$ be a sequence of integers satisfying a linear recurrence with integer coefficients,
$$ n_{i+\ell} = \sum_{k=0}^{\ell-1} a_k n_{i+k},$$
and for simplicity assume that $a_0 = \...
2
votes
0
answers
115
views
Closed form for coefficients related to excedance set of permutation
Working on suitable closed form for A329369, I discovered very useful coefficients, which have the following recurrence relation:
$$T(0,1)=T(0,2)=1$$
$$T(n,1)=1, n>0$$
$$T(0,k)=0, k>2$$
$$T(2n+1,...
0
votes
1
answer
94
views
Recurrence for the number of steps required to get one ball in each box
Given $n$ balls, all of which are initially in the first of $n$ numbered boxes, $a(n)$ is the number of steps required to get one ball in each box when a step consists of moving to the next box every ...
0
votes
0
answers
129
views
How many steps does this subtractive recurrence take?
Given $\alpha\in(0,1)$ and $c\geq1$.
$n$ here is in naturals $\mathbb N$.
$$T_0=n$$
$$T_i=T_{i-1}-\frac{\lfloor{T_{i-1}}^\alpha\rfloor}c\mbox{ at every }i\in\mathbb N$$
is the recursion.
At what $i$ ...
1
vote
1
answer
107
views
Number of steps required to get one ball in each box for $n=2^k$
Given $n$ balls, all of which are initially in the first of $n$ numbered boxes, $a(n)$ is the number of steps required to get one ball in each box when a step consists of moving to the next box every ...
4
votes
2
answers
388
views
Is there a recurrence for the coefficients of the Laurent series expansion of $\frac{1}{1-e^{e^x - 1}}$?
So there's an elementary (but in my opinion quite interesting!) result which is that the Laurent series expansion of
$$\frac{1}{1-e^x} = -\frac{1}{x} + \frac{1}{2} - \frac{1}{12}x - \frac{1}{720}x^3 \...
1
vote
0
answers
66
views
Recurrence for permutation of A007306 (denominators of Farey tree fractions)
Let $a(n)$ be A071585, i.e., numerator of the continued fraction expansion whose terms are the first-order differences of exponents in the binary representation of $4n$, with the exponents of $2$ ...
3
votes
1
answer
209
views
Using generating functions to construct or solve differential equations
I know that $T_n(x)$ is the solution of the differential equation $(1-x^2)y''-xy'+n^2y=0$, where
$$
T_n(x)=\begin{cases}
T_n(x)=1 & \text{if $n=0$}\\
T_n(x)=x & \text{if $n=1$}\\
T_{n}(x)=...
0
votes
1
answer
65
views
Vector recurrences (asymptotic property)
Fix $m\in \mathbb{N}.$
For each $n\in \mathbb{N},$ let $A_n\in \mathbb{M}_{m}(\mathbb{C}),$ $X_n\in \mathbb{C}^m,$ and $B_n\in \mathbb{C}^m.$ Suppose that
$$X_{n+1}=A_n X_n+B_n,$$
$$\lim_{n\rightarrow ...
6
votes
0
answers
170
views
3-term recurrence relation including integral or differential operator for polynomials
Sequences of polynomials with a 3-term recurrence relations are well known for orthogonal polynomials. Do recurrence relations using differential or integral operators also appear in some theories?
I ...