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 ...
robin pemantle's user avatar
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^...
Terry Tao's user avatar
  • 108k
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 ...
Carlo Beenakker's user avatar
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) - ...
Sean Eberhard's user avatar
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 ...
Max Alekseyev's user avatar
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$ ...
Gjergji Zaimi's user avatar
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 ...
Gerald Edgar's user avatar
  • 40.2k
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 ...
GH from MO's user avatar
  • 98.2k
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 ...
Joe Silverman's user avatar
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 ...
Joe Silverman's user avatar
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 ...
Joe Silverman's user avatar
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 ...
Sidney Raffer's user avatar
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 ...
Henri Cohen's user avatar
  • 11.5k
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 ...
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 $$\...
Pietro Majer's user avatar
  • 56.5k
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_{...
Thomas Browning's user avatar
11 votes
Accepted

About a Ramanujan-Sato formula of level 10, a recurrence, and $\zeta(5)$?

Maple found this recurrence: ...
Gerald Edgar's user avatar
  • 40.2k
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}$, $...
Vlad Matei's user avatar
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, ...
Robert Israel's user avatar
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 ...
Yuval Peres's user avatar
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 ...
Hugh Denoncourt's user avatar
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 ...
Max Alekseyev's user avatar
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....
Gerry Myerson's user avatar
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{...
Iosif Pinelis's user avatar
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 ...
Terry Tao's user avatar
  • 108k
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$, ...
Christian Remling's user avatar
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: ...
Henri Cohen's user avatar
  • 11.5k
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}{...
Zhou's user avatar
  • 967
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, ...
Timothy Budd's user avatar
  • 3,545

Only top scored, non community-wiki answers of a minimum length are eligible