Skip to main content

Questions tagged [recurrences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
TiredGradStudent's user avatar
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,...
Notamathematician's user avatar
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 ...
Notamathematician's user avatar
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,...
Manfred Weis's user avatar
  • 12.7k
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$...
Notamathematician's user avatar
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-...
Notamathematician's user avatar
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} = \...
Guest_User_101's user avatar
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 ...
Manfred Weis's user avatar
  • 12.7k
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 ...
Notamathematician's user avatar
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}...
the_village_kid's user avatar
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) + \...
macat's user avatar
  • 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 ...
Justin Lee's user avatar
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 ...
Notamathematician's user avatar
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(...
Faoler's user avatar
  • 431
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 ...
Martin Clever's user avatar
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) = ...
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
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}{...
Notamathematician's user avatar
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 $...
joro's user avatar
  • 24.3k
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)...
Notamathematician's user avatar
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 ...
Per Alexandersson's user avatar
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 ...
Sam Hopkins's user avatar
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}}\...
Claude Leibovici's user avatar
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,...
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
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 ...
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
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_{\...
tommy1996q's user avatar
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 ...
user675763's user avatar
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)$-...
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,205
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
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 ...
Omega's user avatar
  • 31
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(...
mathoverflowUser's user avatar
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 ...
Cye Waldman's user avatar
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&...
Notamathematician's user avatar
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} ...
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
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) $$ ...
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
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 $\...
Artemy's user avatar
  • 650
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 ...
Notamathematician's user avatar
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 $...
user512026's user avatar
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)} $$ ...
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
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 ...
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
2 3 4 5
8