Questions tagged [recurrences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5
votes
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
4answers
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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 ...