# Questions tagged [recurrences]

The recurrences tag has no usage guidance.

**1**

vote

**0**answers

38 views

### A conjectural formula for the “minimal degree function”, $k\rightarrow d\min(k)$, attached to recursion, $f\rightarrow A(f)$, in char $3$

THE RECURSION: $f\rightarrow A(f)$
$A: t(\mathbb{Z}/3)[t^3]\rightarrow t(\mathbb{Z}/3)[t^3]$ is the $\mathbb{Z}/3$-linear map with $A(t)=0, A(t^4)=t, A(t^7)=t^4$, and $A((t^9)f)=(2t^9)A(f)+(t^3)A((t^...

**6**

votes

**1**answer

210 views

### $p_n(x,y)=\sum_{i=0}^{n-1}x^{n-1-i}y^{i}$ is always an integer

Does anyone know if the following problem has ever been studied?
Let $a$ and $b$ be two real numbers and consider the polynomial: $$p_n(x,y)=\sum_{i=0}^{n-1}x^{n-1-i}y^{i}$$
where $n$ is a ...

**0**

votes

**0**answers

26 views

### Reference requested about the rank of appearance in the Lucas sequences

Given $u_n$ a Lucas sequence, we define the rank of appearance of $m$ in $\{u_n\}_{n\geq 0}$, indicated with $z_u(m)$, as the smallest positive integer $n$ such that $m$ divides $u_n$.
I would like ...

**0**

votes

**0**answers

24 views

### Solving 2-dimensional recurrence matrix of homogenous polynomials

I know this isn't research-level mathematics, but I posted this on stack exchange, even offered a bounty but got no responses and no comments, so I am hoping to get an answer here.
In $2012$, ...

**2**

votes

**0**answers

62 views

### Curious if this chaotic recurrence relation has a name and/or interesting properties

I was playing around with 2-dimensional recurrence relations and I stumbled upon this:
$$
x_{n+1} = \sin(k(y_n + x_n))\\
y_{n+1} = \sin(k(y_n - x_n))
$$
I was wondering if this was a known ...

**2**

votes

**2**answers

126 views

### Find formula for recurrence relation with two function and two variables

$f(n,k) = 2g(n-2,k-1)+f(n-1,k)$
$g(n,k) = g(n-1,k-1)+f(n,k)$
when $n\le0$ or $k\le0: \quad f(n,k) = 0$
when $n < k:\quad f(n,k) = 0$
when $n-k<-1:\quad g(n,k) = 0$
when $k=0:\quad g(n,k) = 1$
$...

**1**

vote

**1**answer

125 views

### Finding closed form of recurrence relation in two variables [closed]

I have a recurrence,
$$F(n, m) = F(n-1, m) + F(n, m-1) + F(n-1,m-1) $$
$$F(n,1) = 0$$
$$F(1,n) = 2*(n-1)$$
I would like to compute $F(N,M)$ in terms of $N$ and $M$. The system is defined for $1 \...

**9**

votes

**0**answers

213 views

### How explain these remarkable empirical observations about mod 3 modular forms of levels 1 and 5?

Define $b(n)$ by $b(0)= 0$, $b(3n)= 9b(n)$, $b(3n+1)= 9b(n) + 1$, $b(3n+2)= 9b(n) + 3$. (This sequence does not show up in the OEIS, but the similar Moser-de Bruijn sequence A000695 appears in many ...

**2**

votes

**0**answers

69 views

### Convergence Based on Recurrence Relation

I am studying a sequence based on the following recurrence:
$$X[t] = \sqrt{\alpha X[t-1]^2+(X[t-1]^2-\alpha X[t-2]^2)\frac{(2-X[t-1])^2}{X[t-1]^2}}$$
$$X[0]=0$$
$$X[1]>0$$
$$\alpha \in (0,1)$$
I ...

**2**

votes

**1**answer

94 views

### time delay ergodic theorem

given dynamic system $(X, \mathcal{B}, F, \mu), \mu \circ F^{-1}=\mu, F $ is mixing, $ A \in \mathcal{B}, s.t. \mu(A) >0 $.
consider dynamic system $(X\times X, \mathcal{B}\otimes \mathcal{B}, ...

**3**

votes

**1**answer

256 views

### Detecting if a series represents a rational function

A lemma by Kronecker states that the series $f(z):= \sum_{i=0}^{\infty} c_i z^i$ represents a rational function if and only if for every $m \gg 0$ the determinant of the following matrix is equal to ...

**0**

votes

**0**answers

98 views

### Does this recurrence yields only prime numbers?

The title of this question is merely illustrative, since I do not expect an answer by yes or not, but I seek some reference on the subject.
In this article: https://pdfs.semanticscholar.org/e9be/...

**11**

votes

**1**answer

517 views

### A recursive formula

$$a_0 = 1, \ \ a_{n+1} = \ 1+\frac{n *a_n}{n+a_n} , \ \ n=0,1,2,3,4,...$$
I have built the above recursive formula. Some terms of sequence are:
1, 1, 3/2, 13/7, 73/34, 501/209, 4051/1546, 37633/...

**2**

votes

**0**answers

122 views

### lower bounding the absolute value of a determinant

In a problem that I'm working on currently, the following question came up and I feel this should be fairly elementary, but I couldn't prove it myself/couldn't find a reference. Any pointers or ...

**1**

vote

**0**answers

30 views

### linear difference inequality with error

Let $(\alpha,\gamma,\beta)$ real number such that $\alpha+\gamma+\beta=1$, let $(e_n)_{n\in\mathbb{N}}$ be a summable non-negative sequence and let $(u_n)$ be a non-negative sequence such that
$\...

**0**

votes

**1**answer

99 views

### Solutions to linear equations from recurrence sequences with no repeated roots

Let $U=(u_n)_{n=0}^{\infty}\subseteq\mathbb{C}$ be a sequence enumerated by a linear homogeneous recurrence relation with constant coefficients, i.e., there is some $d\geq 1$ and $a_1,\ldots,a_d\in\...

**4**

votes

**1**answer

139 views

### An inequality involving $k$-generalized Fibonacci numbers

I have worked on a Diophantine equation by using transcendental and reduction methods given by Baker and Davenport. However, to solve completely the equation I have one complicated case and I proved ...

**0**

votes

**0**answers

62 views

### the enumeration of 2 dimensional lattice walks with fixed number steps and largest distance from the end point ti the origin

There is actually an one dimensional version of this problem. For each step of the lattice walk, we can move either east for one unit or west for one unit. The problem is that given a fixed $n$ steps ...

**8**

votes

**4**answers

847 views

### Find a formula for the recurrent sequence $q_{n+1}=q_n(q_n+1)+1$

Find an analytic formula for the recurrent sequence $$q_{n+1}=q_n(q_n+1)+1,\;\;q_0\in\mathbb N.$$
(The question was asked on 03.05.2018 by M. Pratsovytyi, see page 109 of Volume 1 of the Lviv ...

**0**

votes

**1**answer

185 views

### Funny recurrence

Could someone help me solve the following recurrence?
$$
T(k) \le 1+\sum_{i=1}^{n_k}T(k_i),
$$
where $n_k\le k$, $k_i\le \frac23 k$ $\forall i = 1, \dots n_k$, and $\sum_{i=1}^{n_k}k_i \le k$.
The ...

**0**

votes

**1**answer

143 views

### When does this recurrence stop?

Denote $n_i=n_{i-1}-\sqrt[k]{n_{i-1}}$. If $n_0=n$ then what is the minimum $i$ at which $n_i<2$ holds? Is there a standard technique to solve such problems? Any references?

**7**

votes

**0**answers

88 views

### Deciding when certain elements of $L[[x]]$, coming from recursions, are algebraic over $L(x)$

Let $L$ be a finite field of characteristic $2$. Suppose that for some $k > 0$ we are given elements $A(0),\, A(1), \dots, \, A(k-1)$ and $c(0),\, c(1), \dots,\, c(k-1)$ of $L[t]$. Define $A(n)$ ...

**0**

votes

**0**answers

33 views

### Is this the best primality test using second order recurrences (Lucas Sequences)?

this is the copy of the question asked at mathematics stack exchange. original question https://math.stackexchange.com/q/2705983/469085
little Explanation
Using second order lucas sequences
$$U_{n +...

**3**

votes

**1**answer

288 views

### Is there a better proof for this than using the 10-adic numbers?

Here are two somewhat strange sums using the shifted decimal forms of the powers of $3.$
$\begin{equation*}\begin{array}{ccccccc}
&1&&&&&& \\
&&3&&&&...

**0**

votes

**1**answer

326 views

### Is there any number other than 109 whose reciprocal contains the Fibonacci sequence? [closed]

Let $p$ be any odd number, and compute $1/p$ to $p$ decimal places. Compare your answer with the string that is formed by appending all remainders of $(10^n\ \text{mod p}) \text{ mod p}$ where ${0 <...

**22**

votes

**1**answer

499 views

### Rim hook decomposition and volume of moduli spaces

I did some computer experiments, counting the number of rim-hook decompositions (aka border-strip decompositions) of rectangles of shape $2n \times n$, where each strip has size $n$.
Here are 12 of ...

**-2**

votes

**1**answer

123 views

### Is there any pseudoprime that pass this test above tested range, or any prime that does not show these ending patterns?

if the recurrence sequence is defined by the following foormula, $d_{n + 3} = 3d_{n + 2} - d_{n + 1} - 2d_n$ where $d_1 = 1, d_2 = 3$ and $ d_3 = 7$, this produce the following complex sequence $$1, ...

**3**

votes

**2**answers

265 views

### Seeking proof to an asymptotics of a recursion or functional equation

My question on math.stackexchange.com and the continuation by an answer to it gives the two summation expressions for the recursion
$$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\...

**2**

votes

**1**answer

640 views

### Power tower made of $2$s and $3$s: too high, too soon?

A power tower of a number $x$ is typified by
$$ x^{x^{x^{x^{x^{x^{x^{x^{x^x}}}}}}}}.$$
Here, however, we take the liberty of referring to the set $T$ of "$\{2,3\}$-power towers"; i.e., numbers
$$...

**4**

votes

**1**answer

162 views

### Second order recurrence relation for third order polynomial root

Consider this recurrence relation:
$$
\begin{eqnarray*}
f_0&=&1\\
f_n&=&
\sum_{m=0}^{n-1} \frac{\left(\frac{m+3}{2}\right)_{m-1}}{\left(\frac{m+2}{2}\right)_m} f_{n-m-1} f_m\ \ \ \...

**5**

votes

**1**answer

248 views

### Simply generated sequences with mysterious differences

Suppose that $a_0 < a_1,$ $b_0 < b_1,$ and $$a_n=a_1b_{n-1}+a_0b_{n-2}+qn+r$$ for $n \geq 2$, where $a_0,a_1,b_0,b_1,q,r$ are integers such that $(a_n)$ and $(b_n)$ are increasing and ${(|a_n|)}$...

**7**

votes

**2**answers

350 views

### Limit associated with complementary sequences

Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_0b_{n-1}+a_1b_{n-2}$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs ...

**2**

votes

**1**answer

278 views

### Is there a good bound for this double exponential recursion?

Denote when $k>2m$ $$f_k(2m)=\sum_{i=1,i\geq1}^m\binom{2m}{i}f_k(i)f_k(2m-i)$$
$$f_k(2m+1)=\sum_{i=1,i\geq1}^m\binom{2m+1}{i}f_k(i)f_k(2m+1-i)$$
$$f_k(0)=1.$$
$$f_k(1)=k.$$
What is a good bound ...

**3**

votes

**1**answer

119 views

### Does a linear Recurrence relation with an nonlinear relation between elements can be solved by a closed formula?

I came across with this cool recurrence relation, and unfortunately i couldn't find sufficient mathematical tools to form it to a closed formula. i read several posts from math overflow saying that ...

**1**

vote

**0**answers

133 views

### (b,c) rank 2 cluster algebras

Let $x$ and $y$ be variables. Consider the following recurrence:
\begin{equation}
u_{n}:=
\begin{cases}
\displaystyle{\frac{1+u_{n-1}^b}{u_{n-2}}} & if\ n\ \text{is even},\\
&\\
\displaystyle{\...

**20**

votes

**2**answers

421 views

### Do these polynomials have alternating coefficients?

In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence
$$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$
Thus:
...

**1**

vote

**2**answers

457 views

### Can these sequences stay integer-valued as many times as we want and then fail?

Edit:
Suppose that we choose some integer $d$ and some natural number $c=c_2$. Then if we plug those values into
$$ c_{n+1}=\frac{c_n(c_n+n+d)}n $$ and observe the behavior of this recursively ...

**27**

votes

**0**answers

682 views

### Is there any positive integer sequence $c_{n+1}=\frac{c_n(c_n+n+d)}n$?

In a recent answer Max Alekseyev provided two recurrences of the form mentioned in the title which stay integer for a long time. However, they eventually fail.
QUESTION Is there any (added: ...

**14**

votes

**1**answer

1k views

### Simple recurrence that fails to be integer for the first time at the 44th term

The sequence defined by $a_0=a_1 =1$ and
$$
a_n = \frac{1}{n-1}\sum_{i=0}^{n-1}a_i^2, \quad n > 1
$$
fails to be integer for the first time at $a_{44}$. Why??
You can verify the statement by ...

**1**

vote

**0**answers

130 views

### Proving the existence of a sequence with recursive growth constraints

Fix $0 < c < 1/3$. Show that there exists a strictly increasing sequence $a_k > 0$, a sequence $b_k \geq 0$, and an infinite set $K \subseteq \mathbb{Z}_{>0}$ such that
\begin{align}\...

**0**

votes

**0**answers

99 views

### stochastic recurrence relation “convergence”

Consider a recurrence relation $x_n = f(x_{n-1})$. Suppose $f(x_n)<0$ for some "large enough" $n$. Now consider a "stochastic variant" $x_n = f(x_{n-1})+y_n$ where $y_n$ is a sequence of random ...

**2**

votes

**1**answer

174 views

### Solve functional equation: $\frac{F(x)}{F(1)} = 2F\left(\frac{(1+x)^2}{4a}\right)-F(x/a)$

Solve this functional equation:
$$\frac{F(x)}{F(1)} = 2F\left(\frac{(1+x)^2}{4a}\right)-F(x/a)$$
for $F(x)$ where $a > 0$ is a parameter. I know there is a trivial constant solution, $F(x) = 1$. ...

**1**

vote

**0**answers

92 views

### Find bivariate generating function for two-dimensional sequence

How to find generating function for triangle of squares of elements in this sequence? I. e. for
$1 + (1 + 4x)y + (1 + 9x + 16x^2)y^2 + ...$ ? It seems that ordinary approach with arithmetic ...

**7**

votes

**1**answer

245 views

### Counting some binary trees with lots of extra stucture

While working on some computations on Hilbert schemes, I came across the following combinatorial problem.
Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...

**6**

votes

**0**answers

143 views

### Is Somos-8 $\mod 2$ periodic?

It is known that the Somos-$k$ sequences for $k\ge 8$ do not give integers. But the first terms of Somos-8 sequence $s_n=a_n/b_n$
$$1, 1, 1, 1, 1, 1, 1, 1, 4, 7, 13, 25, 61, 187, 775, 5827, 14815,\...

**22**

votes

**2**answers

654 views

### Possible behaviors of integer sequences that arise from powering nonnegative integer matrices

Let's call a sequence of nonnegative integers $x_1,x_2,\ldots$ matrix-realizable, if there exists a $k\times k$ nonnegative integer matrix $A$ (for some $k$), as well as nonnegative integer vectors $u,...

**1**

vote

**0**answers

80 views

### Solving a partial difference equation with variable coefficients explicitly

I'm trying to solve the following partial difference equation with variable coefficients:
$$a_{i,j,k}=-\frac{j+1}{i}a_{i-1,j+1,k-1}- \frac{k+1}{i}a_{i-1,j-1,k+1}, $$
defined on the grid $(i,j,k) \in \...

**3**

votes

**1**answer

257 views

### Bound on the number of primitive divisors of the $n$th Fibonacci number

It is a result of Carmichael that for any integer $n > 12$, the Fibonacci number $F_n$ has at least one primitive divisor, that is, a prime factor $p$ such that $p$ does not divide any $F_m$ with $...

**1**

vote

**2**answers

369 views

### Linear two-dimensional recurrence relation

As part of my research I have to analyze recurrence relations of the form
$$f_{m,n} = af_{m-1,n} + bf_{m,n-1} + c,$$
where $a,b,c$ are any given real numbers and $f_{m,0}$ and $f_{0,n}$ any given ...

**0**

votes

**0**answers

194 views

### Resolve a recursive formula with combination number

For integers $n\ge2$ and $k\ge2$, consider the recursion
$$
p(n,k) = \frac{{k^{n - 1} }}{{k^{n - 1} - 1}}\left[1 + \sum\limits_{i = 2}^{n - 1} {\frac{{\binom{n}i (k - 1)^{n - i} }}{{k^{n - 1} }}p(i,...