37
votes
What is the limit of $a (n + 1) / a (n)$?
The value is close to $e$ but not. It's actually the positive real root of $p(t) := t^3 - 2t^2 + t - 8$. This is solvable via ACSV (see book by Pemantle and Wilson 2013). To summarize, the ...
37
votes
Accepted
Elegant recursion for A301897
Here is an expanded version of the generating function argument I sketched in a comment.
For $i=1,2,3$, define the generating functions $F_i(x,y) := \sum_{n=0}^\infty \sum_{q=0}^\infty R(n,3q+i) x^n y^...
31
votes
Function that produces primes
For the record (not an answer), the function $a(n-1,n)$ for $n$ up to $10^4$ contains 2264 distinct primes, the largest being equal to 20369. I checked that no primes are missing. The growth rate of ...
27
votes
Function that produces primes
Extended comment, generalizing @IlyaBogdanov's comment about $2n-1$. Fix $n$ and let $$x_m = a(m, n) + n - m - 1.$$ Then $(x_m)$ obeys the similar recurrence
$$
x_m = x_{m-1} + \gcd(x_{m-1}, n-m) - ...
24
votes
Accepted
Simple recurrence that fails to be integer for the first time at the 44th term
Copying my explanation from https://mathoverflow.net/a/217894/25028
The recurrence formula can be rewritten as
$$a_2=2,\qquad a_{n+1}=\frac{a_n\cdot (a_n+n-1)}n,\quad n\geq 2,$$
which somewhat ...
17
votes
Accepted
Possible behaviors of integer sequences that arise from powering nonnegative integer matrices
The answer is "no" for both questions.
The rational functions $a_0+a_1x+a_2x^2+\cdots$ with non-negative integer entries which can be obtained by $a_n=u^{T}A^nv$ for some nonnegative vectors $u,v$ ...
17
votes
Accepted
"Laurent phenomenon"?
In fact,
$$
u_n(x) =
{2}^{n-1}\prod _{k=0}^{n-1}(2x+2k+1)
-{2\,n-1\choose n-1}\prod _{k=0}^{n-1}(x+k) ,
\tag1$$
which is a polynomial with integer coefficients.
P.S. the proof rests on a routine ...
16
votes
Accepted
A recursive formula
For $n\geq 1$, let $p_n$ be the $(n+1)$-th term of A000262, and let $q_n$ be $n$-th term of A002720. Then, according to the description of these two sequences (more precisely by the contributions of ...
16
votes
Accepted
Counterpart of cyclotomic polynomials for elliptic divisibility sequences
The counterpart of the cyclotomic polynomials are elliptic division polynomials, which can be defined recursively by a non-linear recursion (usually presented as a pair of recursions, one for odd ...
15
votes
Find a formula for the recurrent sequence $q_{n+1}=q_n(q_n+1)+1$
I'm not quite sure what you mean by an "analytic formula." As Fedor Petrov indicated, there is unlikely to be a closed formula. However, there is a convergent power series. More precisely, consider ...
14
votes
Find a formula for the recurrent sequence $q_{n+1}=q_n(q_n+1)+1$
This is a second answer with a somewhat different viewpoint from my other answer. It is an expansion, in some sense, of Gerry Myerson's answer. There is a general theory for estimating these sorts of ...
13
votes
Accepted
Are the terms of a linear recurrence integral?
The problem is effectively decidable. To test whether $u_n$ is eventually integral, first use the recurrence relation for $u_n$ to construct relatively prime polynomials $A,B\in \mathbb{Z}[x]$ such ...
13
votes
Accepted
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"
We have $$C_2(-17,-6,-72)=-(5/8)L(\chi_{-3},2)$$ and
$$C_2(10,3,-9)=(1/2)L(\chi_{-3},2)$$ so both are proportional to what you
call Gieseking's constant but which is simply the value at 2 of the
L ...
12
votes
Do these polynomials have alternating coefficients?
To illustrate the suggestion of Richard Stanley about positivity of real parts of zeroes, here are the zeroes of $Q_{20}$. The pattern seems to be the same for all of them.
Another empirical ...
Community wiki
12
votes
Limit associated with complementary sequences
Let $\alpha_*$, $\alpha^*$ denote the lower, respectively upper asymptotic density of the set $A$, and $\beta_*$, $\beta^*$ the lower and upper asymptotic density of the set $B$. Note that $$\...
12
votes
Accepted
Why $\lim_{n\rightarrow \infty}\frac{F(n,n)}{F(n-1,n-1)} =\frac{9}{8}$?
We will compute the generating function, and use the method described in section 2 of this paper.
Let $F_{m,n}=F(m,n)$. Consider the generating function
$$G(x,y)=\sum_{m=0}^\infty\sum_{n=0}^\infty F_{...
11
votes
Accepted
About a Ramanujan-Sato formula of level 10, a recurrence, and $\zeta(5)$?
Maple found this recurrence:
...
11
votes
Accepted
$p_n(x,y)=\sum_{i=0}^{n-1}x^{n-1-i}y^{i}$ is always an integer
I will do the rational case and assume $a,b\neq 0$ otherwise the problem is trivial. You just need four consecutive values. Note that $p_n(a,b)=\cfrac{a^n-b^n}{a-b}$.
Say you have $p_k$, $p_{k+1}$, $...
11
votes
Supremum of $ a_n = a_{n-1}^3 - a_{n-2} $
The question is really about the iteration behaviour of the maps $(x,y) \mapsto (y, y^3-x)$ with various starting points. We have a fixed point $(0,0)$ and a $6$-cycle $$(1,0),(0, -1), (-1, -1), (-1, ...
11
votes
Accepted
Recursive random number generator based on irrational numbers
Of course the $X_k$ are not independent as random variables. So I assume you are referring to some notion of asymptotic independence, and it would help if you state your conjecture more precisely. One ...
11
votes
Accepted
Explicit expression for recursive sums
Claim: The iterated sum $f_k(t_1,\ldots,t_k)$ counts the number of elements the interval $[\emptyset,\lambda]$ of Young's lattice, where $\lambda = (\lambda_1,\lambda_2,\ldots,\lambda_k)$ is the ...
11
votes
Accepted
Is there a recurrence for the coefficients of the Laurent series expansion of $\frac{1}{1-e^{e^x - 1}}$?
$e^{e^x-1}$ is the exponential generating function for Bell numbers ${\cal B}_n$:
$$e^{e^x-1} = \sum_{n\geq 0} {\cal B}_n \frac{x^n}{n!}.$$
Then
$$g(x) := \frac{e^{e^x-1}-1}{x} = \sum_{n\geq 0} {\cal ...
10
votes
Find a formula for the recurrent sequence $q_{n+1}=q_n(q_n+1)+1$
The sequence (at any rate, the case $q_0=1$) has been studied, and references are given at OEIS. The closest thing to a formula given there is $a(n) = [c^{2^n}]$ for $n > 0$, where $c = 1....
10
votes
Accepted
Growth of sequence generated by recurrence relation
$\newcommand{\fl}[1]{\lfloor #1\rfloor}
\newcommand{\Fl}[1]{\Big\lfloor #1\Big\rfloor}$For natural $n\ge2$, we have
\begin{equation*}
T(n)=T(n-1)+T(\lfloor n/2\rfloor). \tag{1}\label{1}
\end{...
10
votes
Accepted
Remarkable recursions for the A204262
I can show the first identity $R(n,0) = f_{n+1,n+1}(0)$, as a consequence of the more general identity
$$ R(n,q) = \frac{1}{(q+1)!} f_{n+q+1,n}(n+1)\tag{1}\label{1}$$
for $n,q \geq 0$. Indeed, note ...
9
votes
Possible behaviors of integer sequences that arise from powering nonnegative integer matrices
Such sequences are linear combinations of (complex) exponentials times polynomials $p(n)e^{\lambda n}$ (bring $A$ to Jordan normal form to see this, or use the fact you mentioned). So for large $n$, ...
9
votes
Accepted
Second order recurrence relation for third order polynomial root
This is sequence A244038 in OEIS after scaling by $3^n$, so $f_n=(4/3)^n\binom{3n/2}n$. The fact that it satisfies a cubic equation
is certainly a well-known result in hypergeometric functions.
EDIT: ...
9
votes
Find a formula for the recurrent sequence $q_{n+1}=q_n(q_n+1)+1$
If we denote $A_n=q_n+1/2$, then
$$A_n=A_{n-1}^2+5/4$$
with $A_0=q_0+1/2\ge 3/2$ by $q_0\in\mathbb{N}$.
Further,
$$\log A_n=2\log A_{n-1}+\log\left(1+\frac{5}{4A_{n-1}^2}\right),$$
namely
$$\frac{1}{...
9
votes
Accepted
Enumeration of lattice paths of a specific type
It seems the first solution to this problem appeared in Theorem 4 of
Raschel, Kilian, Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc. (JEMS) 14, No. 3, ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
recurrences × 357co.combinatorics × 140
sequences-and-series × 140
nt.number-theory × 139
generating-functions × 43
polynomials × 33
integer-sequences × 32
pr.probability × 20
asymptotics × 20
closed-form-expressions × 19
reference-request × 17
linear-algebra × 16
limits-and-convergence × 14
real-analysis × 10
binomial-coefficients × 10
difference-equations × 10
ca.classical-analysis-and-odes × 9
prime-numbers × 9
differential-equations × 8
cv.complex-variables × 7
ds.dynamical-systems × 7
special-functions × 7
orthogonal-polynomials × 7
matrices × 6
stochastic-processes × 6