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

- 351

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

- 152k

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

- 26.8k

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) - ...

- 6,964

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

- 38k

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$ ...

- 82.5k

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

- 42.7k

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

- 42.7k

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

- 87k

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

- 42.7k

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

- 6,099

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}$.

- 45.6k

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 $$\...

- 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}$, $...

- 807

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, ...

- 51.8k

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_{...

- 1,857

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

- 501

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$ ...

- 16.3k

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

- 36.5k

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{...

- 82.4k

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:
...

- 38k

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

#### Related Tags

recurrences × 263co.combinatorics × 83

nt.number-theory × 76

sequences-and-series × 76

generating-functions × 26

polynomials × 25

asymptotics × 18

pr.probability × 17

reference-request × 16

integer-sequences × 15

linear-algebra × 14

real-analysis × 10

binomial-coefficients × 10

limits-and-convergence × 9

ca.classical-analysis-and-odes × 8

prime-numbers × 8

ds.dynamical-systems × 7

orthogonal-polynomials × 7

closed-form-expressions × 7

difference-equations × 7

differential-equations × 6

enumerative-combinatorics × 6

valuation-theory × 6

matrices × 5

cv.complex-variables × 5