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 ...
29 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
Accepted

For a linear recurrence sequence $(u_n)_{n\geq 0}$, can $\{i \mid u_i > 0\}$ be the set of Fibonacci numbers?

Solutions to (complex) linear recurrences are of the form $$\sum_i c_i n^{e_i} \alpha_i^n.$$ To build such a function that is positive only on Fibonacci numbers, take $n^2(\alpha^n + \bar{\alpha}^n-...
  • 27.5k
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 ...
23 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) - ...
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

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$ ...
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 ...
15 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 ...
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 ...
12 votes
Accepted

Faster formula to compute sum over partitions

The identity $np(n) = \sum_{m=1}^n p(n-m)\sigma(m)$, where $\sigma(m)$ is the sum of divisors of $n$ generalizes to this setting. The proof I sketched here shows that $$ nF(n) = \sum_{r=1}^n F(n-r) g(...
  • 10.4k
12 votes
Accepted

Polynomial recurrence relation covering the integers (and then Gaussian integers)

For the first question, let $f_1=0$, $f_2=1$, $f_3=-1$, and $f_i=-f_{i-1}+f_{i-2}+f_{i-3}$.
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 $$\...
  • 51.9k
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 ...
  • 12.9k
11 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

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 ...
10 votes
Accepted

Product of a Finite Number of Matrices Related to Roots of Unity

The following is a conjectured generalization of the claimed identity which may help in proving it. We prove this generalization (and hence also the identity from the question) in the case that $3$ ...
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{...
9 votes

Limiting probabilities for two-player game drawing random uniform numbers

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$. Edit: I added a more general strategy below, giving a bound that seems likely to be optimal. Player A will pick some ...
  • 8,851
9 votes
Accepted

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

Maple found this recurrence: ...
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,361
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}{...
  • 902
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, ...
  • 3,305

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