# Questions tagged [recurrences]

The recurrences tag has no usage guidance.

173
questions

**5**

votes

**0**answers

63 views

### A recursion which defines polynomials with integer coefficients?

Let $[n]=1+q+\dots+q^{n-1}$ and $u(n)=\prod_{j=1}^n \gcd([j],[n])$.
Define
$$r(n)=\sum_{d}{(-1)^d \frac{u(n)}{du(\frac{n}{d})^d}r(\frac{n}{d})^d}+\frac{(1-q)^{n-1}u(n)}{n[n]}$$ with $r(1)=1,$ where $...

**1**

vote

**1**answer

80 views

### Solving recurrence of a three variable function

I am fairly new to generating functions and have been trying to solve the following recurrence for a computer science problem.
$$ f(k,d,n) = \sum_{i=1}^{n-1} \binom{n-2}{i-1} \left(\frac{1}{2}\...

**1**

vote

**1**answer

117 views

### Solving recursion of a complex function

I am trying to find a closed form formula for the following recursive function:
$$f_n(h)= \sum_{i=1}^{n-1} \binom{n-2}{i-1} \cdot (0.5)^{n-2} \cdot [ (f_{n-i}(h-1)\cdot \sum_{j=0}^{h-1}f_i(j)) + (f_{i}...

**1**

vote

**0**answers

109 views

### Recursively obtained hard Diophantine equation for “Baseless numbers”

An equivalent problem was originally asked on MSE as Does every number base have at least one “Baseless number”?, but did not receive any answers that would help answer the main question about "...

**1**

vote

**0**answers

38 views

### Obtaining generating function for multivariate recurrence with non-constant coefficients

Consider a second order recurrence of the form below for some fixed $n$
\begin{align}
(n+s-1) A_{n}(k,s) &= (n-k+1) A_{n}(k-1,s-1) + (k+s-3) A_{n}(k,s-1) \\
A_n(k,s) &= 0 \tag{when $s < k$ ...

**6**

votes

**0**answers

187 views

### Computing powers of a special matrix fast

I've got an $n\times n$ matrix that is upper-triangular (all zeros below diagonal), diagonal entries are positive, and entries that are not on the diagonal are either $0$ or $1$. An example matrix ...

**2**

votes

**1**answer

196 views

### Number of non-crossing sets of intervals

Consider the integers $[1,n]=\{1,\dots,n\}$ and call subsets of the type $[a,b]=\{a,\dots,b\}$ with $1\le a < b\le n$ intervals. We say that two intervals $[a,b],[c,d]$ are crossing if either $a<...

**1**

vote

**1**answer

78 views

### Is there a rectangular tiling based on the Padovan sequence? [closed]

I'm thinking of developing a rectangular tiling based on the Padovan sequence (think of the Fibonacci mosaic). It seems like something that should exist, but I can't find anything in the literature. ...

**3**

votes

**1**answer

150 views

### Find the closed-form expression for $c_n$ of this recursive sequence [closed]

$$c_{n + 1} = 2\cdot|c_n| - \sqrt{c_n^2 + 16}$$ with $c_0 = 3$.
My question on math stackexchange was closed because lack of details. Let me clarify: I'm an amateur novelist, I don't know anything ...

**7**

votes

**0**answers

152 views

### No intermediate denominators growth for holonomic functions?

My question concerns holonomic sequences of rational numbers, meaning assignments $a(n) : \mathbb{N} \to \mathbb{Q}$ fulfilling a linear recurrent relation of the form
$$
a(n+k) = \sum_{i=0}^{k-1} p_i(...

**1**

vote

**0**answers

37 views

### Linear matrix recurrences with polynomial coefficients

I am interested in solving linear recurrences of the form
$$a_{n+1}=\sum_{i=0}^K n^i X_i + \sum_{i=0}^L n^i Y_i a_n \tag{1}$$
where the $Y_i$ are $N\times N$ matrices, and the $X_i$ and $a_n$ are $N\...

**1**

vote

**0**answers

53 views

### Density of integers related to the size of its order of appearance in the Fibonacci sequence

Let $z(n)=\min\{k>0 : n\mid F_k\}$. This function is known as the Fibonacci entry point (for example). A result of Sallé gives the sharpest upper bound for $z(n)$, namely, $z(n)\leq 2n$, for all $n$...

**1**

vote

**1**answer

267 views

### Find closed-form expression to $f(n)$

Let
$ \forall n\in\mathbb N.\quad f(n)=
\begin{cases}
\min_{a\in\{\lceil n/2\rceil, \lceil n/2\rceil+1,\dots, n-1\}} \frac 1 4 \binom n a f(a) & \text{if $n\geq 4$}\\
1 & \text{else}
\end{...

**0**

votes

**0**answers

105 views

### On a recurrence relation and Taylor series associated with it

Consider the following recurrence relation :
$$ P(n) = c_n + \sum_{k=1}^{n-1} c_k P(n-k) $$
Now , consider the following Taylor series :
$$F(x) = \sum_{n=0}^{\infty} \frac{x^n(-1)^n}{P(n)n!} $$
...

**8**

votes

**2**answers

369 views

### Supremum of $ a_n = a_{n-1}^3 - a_{n-2} $ [closed]

Let $a_1=0$ and let $ - \ln(2) < a_2 < \ln(2) $
Define
$$ a_n = a_{n-1}^3 - a_{n-2} $$
Then
$$ \sup_{n>2} a_n = a_2 $$
And
$$ \inf_{n>2} a_n = - a_2 $$
How to prove that ?

**2**

votes

**1**answer

60 views

### Dominant root of a family of odd degree polynomials

Let $q$ be an odd positive integer and denote by $f_q(x)=x^q-x^{q-2}-1$. This family of polynomials appears in some problems related to recurrence sequences.
In order to try to use some standard ...

**4**

votes

**1**answer

286 views

### About $a_n = \frac{a_{n-1}(a_{n-1} + C)}{a_{n-2}}.$

Let $A,B,C > 0$. Put $a_1 = A$ and $a_2 = B$ and, for integer $n > 2$,
$$a_n = \frac{a_{n-1}(a_{n-1} + C)}{a_{n-2}}$$
and
$$ T = \lim_{k \to \infty} \frac{a_k}{ a_{k - 1}}.$$
Notice the limit ...

**2**

votes

**1**answer

77 views

### Existence of some prime $x_k | k > 2$ in $x_n = x_{n-1} + x_{n-2}$ whenever $x_1$ is coprime to $x_2$

It is not known whether there is a largest prime in the Fibonacci sequence, but of course there are quite a few primes.
Similarly, the Lucas sequence starting with $L_1=1, L_2 = 3$ comes to a prime ...

**16**

votes

**2**answers

618 views

### Counterpart of cyclotomic polynomials for elliptic divisibility sequences

Let $(U_n)_{n \in \mathbb{N}}$ be a Lucas sequences given by
$$U_0 = 0,\quad U_1 = 1,\quad U_n = P U_{n - 1} - Q U_{n-2},$$
where $P,Q$ are integers with $P^2 - 4Q \neq 0$. It is well known that the ...

**1**

vote

**1**answer

87 views

### Asymptotics of the general second order affine recursion

What is the general method for finding the aymptotics of large $n$ of the sequence $(a_n)_{n=0}^\infty$ defined by the recursion
$$a_{n} = (\alpha_1n+\alpha_2) a_{n-1} + (\alpha_3n+\alpha_4) a_{n-2}+\...

**2**

votes

**0**answers

72 views

### Closed form for unusual recurrence

We have for $k>0$, $n>0$, $m\geqslant0$
$$p_k(n,m)=k(n-1)!\sum\limits_{s=0}^{n-1}\frac{p_{k-1}(s+1,m+1)+p_{k-1}(m+1,s)}{s!}$$
also
$$p_0(n,m)=\begin{cases}
(n-1)!,&\text{$n>0, m=0$}\\
0,&...

**3**

votes

**1**answer

146 views

### Squares in Lucas sequences

Good night, everyone!
According to a celebrated result by J. H. Cohn, the only perfect squares in the Fibonacci sequence are $F_{0}=0$, $F_{1}=F_{2}=1$, and $F_{12}=144$. It is also known that the ...

**1**

vote

**0**answers

94 views

### On a recurrence relation with non-constant coefficients

I am studying a real symmetric tridiagonal matrix $J_{N+1}$ (all off-diagonal elements non-zero) of dimension $N+1$, and I would like to solve the eigenvalue problem. The point is that the ...

**6**

votes

**1**answer

246 views

### Iterated derivative and rectangular standard Young tableaux

We first make a few definitions, seemingly out of the blue (they are introduced/defined in this paper).
Let $F^0_{a}(z) = (1-z)^{-1}$ and define recursively
$$
F^{k+1}_{a}(z) = z^{a-1} \frac{d^a}{dz^...

**0**

votes

**0**answers

109 views

### exponential growth of random fibonacci sequences

I don't know if this is the right place to ask this question because I have the impression that this is quite an elementary one.. But I thought, maybe someone here already read this paper (or would be ...

**4**

votes

**0**answers

176 views

### Convergence with the recurrence $T_{n+1}=T_n^2-T_n+\frac{n}{p_n}$

For each integer $n\geq 1$ I define the recurrence $$T_{n+1}=T_n^2-T_n+\frac{n}{p_n},$$
with $T_1=1$, where $p_k$ denotes the $k-th$ prime.
So multiplying by $(-1)^n$ and telecoping gives that for ...

**0**

votes

**0**answers

60 views

### Prove that the Mertens function is invariant under matrix inversion for $n>3$

Consider the lower triangular matrix $T$ with the definition:
$n \leq3 :$
$$T(n, 1)=1$$
$n>3:$
$$T(n,1)=x_n$$
$n \geq k:$
$n \leq 3:$
$$T(n,k)=1$$
$n \geq k:$
$n>3:$
$k=2 \text{ or } k=3:$
...

**1**

vote

**0**answers

430 views

### Two conjectural identities involving $\zeta(3)$ and the golden ratio $\phi$

Let $\phi$ be the famous golden ratio $\frac{\sqrt5+1}2$, and let
$\zeta(3)=\sum_{n=1}^\infty\frac1{n^3}.$
In 2014, in the paper
Zhi-Wei Sun, New series for some special values of $L$-functions, ...

**4**

votes

**1**answer

117 views

### Nonlinear recurrence

I encounter the following recurrence
\begin{equation} \tag{1}\label{eq:1}
h_{j+1} = h_{j} ( 1 - 1/j - c h_j ), \quad j \geq j_0,
\end{equation}
with $h_{j_0}>0$, $c>0$ and $0< 1-1/j_0 - c h_{...

**6**

votes

**0**answers

93 views

### A question about the span of a sequence of polynomials satisfying a linear recurrence

Let F be a finite field and A(n) in F[t], n in N, be defined by a linear recurrence with coefficients in F[t], together with initial conditions. Is there a decision procedure for determining whether ...

**1**

vote

**1**answer

169 views

### An iterative argument involving $f(n + 1) - f(n) $

I am working with an argument involving an inequality of the form:
$$ f(n + 1) \leq f(n) + C (f(n))^{1 - \frac{1}{\gamma}} \qquad(\ast)$$
where $f$ is a positive function, $\gamma > 0$ and $C >...

**3**

votes

**1**answer

199 views

### A 2d recurrence equation representing a step-free continuous-time Markov process on N^2 with frequency-dependent rates

$\textbf{Background:}$ Consider a particle in $\mathbb{N}^2$ starting at a point $(x,y)$ that can only move one step at a time along the lattice. The particle moves each up or down in continuous time ...

**0**

votes

**1**answer

75 views

### Solving an recursive sequence [closed]

I have an recursive sequence and want to convert it to an explicit formula.
The recursive sequence is:
$f(0) = 4$
$f(1) = 14$
$f(2) = 194$
$f(x+1) = f(x)^2 - 2$

**5**

votes

**1**answer

231 views

### Solving Linear Matrix Recurrences

Question:
Are there standard techniques available for solving the following kind of linear matrix recurrence relations:
$$M_1,\cdots,M_k\ \in\ \mathbb{R}^{m\times n}$$
$$ A_1,\cdots,A_k\ \...

**2**

votes

**3**answers

334 views

### Does this deceptively simple nonlinear recurrence relation have a closed form solution?

Given the base case $a_0 = 1$, does $a_n = a_{n-1} + \frac{1}{\left\lfloor{a_{n-1}}\right \rfloor}$ have a closed form solution? The sequence itself is divergent and simply goes {$1, 2, 2+\frac{1}{2}, ...

**3**

votes

**4**answers

211 views

### Solution of a 2D Recurrence sequence

Can we solve the following recurrence relation:
$$a_{m,n} = 1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}$$
with $a_{0,n}=a_{m,0}=0$? If not, can we get an estimate of the growth of $a_{m,n}?$
I encountered this ...

**4**

votes

**1**answer

162 views

### A 2nd order recursion with polynomial coefficients

I'm hoping to find "exact" an solution to the following simple recursion:
$q_m(j+1) = m \cdot q_m(j) + j(j+m)\cdot q_m(j-1)$
with initial data $q_m(0) = 1$, $q_m(1)=m$, where $m \geq 0$ is an ...

**-1**

votes

**1**answer

117 views

### If $p_n(a,b)$ is a rational number (or integer) for 3 consecutive values of $n$ then every $p_n(a,b)$ is

Let $a$ and $b$ be two real numbers and $p_n(x,y)$ the polynomial: $$p_n(x,y)=\sum_{i=0}^{n-1}x^{n-1-i}y^{i},$$ where $n$ is a positive integer.
In a previous post I asked if $p_n(a,b)$ was a ...

**5**

votes

**3**answers

346 views

### Enumeration of lattice paths of a specific type

One of the approaches to "Special" meanders led (in particular) to the following question:
What is the number $a_{m,n}(\ell)$ of $\ell$-step paths from $(1,1)$ to $(m,n)$ using the ...

**2**

votes

**0**answers

44 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

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

**2**

votes

**0**answers

78 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

468 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

681 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

230 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

269 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

108 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

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

**12**

votes

**1**answer

552 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

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