Questions tagged [recurrences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
86 views

Bounding the $n$-th term of a sequence, given a non-linear recursive bound

I asked the following question in MSE: Let $a,b\in\mathbb{R}^+$. Suppose that $\{x_n\}_{n=0}^\infty$ is a sequence satisfying $$|x_n|\leq a|x_{n-1}|+b|x_{n-1}|^2, $$ for all $n\in\mathbb{N}$. How can ...
4
votes
1answer
260 views

Reference request: recurrence relation for Catalan numbers

I would like to know if the following recurrence relation for Catalan numbers (see mathoverflow.net/questions/191524 and also math.stackexchange.com/questions/2113830) has appeared in a paper or a ...
1
vote
1answer
253 views

Why $\lim_{n\rightarrow \infty}\frac{F(n,n)}{F(n-1,n-1)} =\frac{9}{8}$?

$$F(m,n)= \begin{cases} 1, & \text{if $m n=0$ }; \\ \frac{1}{2} F(m ,n-1) + \frac{1}{3} F(m-1,n )+ \frac{1}{4} F(m-1,n-1), & \text{ if $m n>0$. }% \end{cases}$$ Please a proof of: $$\lim_{...
4
votes
0answers
105 views

Positivity conjecture for Somos sequences

Let $\{s_n\}$ be the Somos-$4$ sequence, which is defined by $$s_{n+4}s_n=\alpha s_{n+3}s_{n+1}+\beta s_n^2.$$ It is known that $s_n$ is a Laurent polynomial: $s_n\in\mathbb{Z}[s_1^{\pm1}, \ldots, s_4^...
1
vote
0answers
180 views

Why $\lim_{n\rightarrow \infty}\frac{F(n,n)}{F(n-1,n)} =\lim_{n\rightarrow \infty}\frac{F(n+1,n)}{F(n,n)} $?

Let $\alpha,\beta, \gamma \in \mathbb{R}^+$ be and the function $$ F(m,n)= \begin{cases} 1, & \text{if $m n=0$ }; \\ \alpha F(m ,n-1)+ \beta F(m-1,n )+ \gamma F(m-1,n-1), & \text{ if $m n>...
11
votes
3answers
970 views

What is the limit of $a (n + 1) / a (n)$?

Let $a(n) = f(n,n)$ where $f(m,n) = 1$ if $m < 2 $ or $ n < 2$ and $f(m,n) = f(m-1,n-1) + f(m-1,n-2) + 2 f(m-2,n-1)$ otherwise. What is the limit of $a(n + 1) / a (n)$? $(2.71...)$
5
votes
1answer
160 views

Hook lengths, contents and recurrence

For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively. Define the functions $$f_n(t):=\...
3
votes
2answers
254 views

Finding the summation formula for the recurrence relation $T_n=T_{n-1}\;+(n-1)\cdot T_{n-2}\;$

The exponential generating function of this recurrence relation, $T_n=T_{n-1}\;+(n-1)\cdot T_{n-2}\;$, is $$f(x)=e^{x + \frac{x^2}{2}}$$ Multiplying the exponential generating functions for each term, ...
3
votes
1answer
285 views

Special permutations of $\{1,2,3,\ldots,n\}$

How do you show that number of permutations of $\{1,2,3,\ldots,n\}$ such that image of no two consecutive numbers is consecutive is $$n! + \sum_{k = 1}^{n}(-1)^k\sum_{i = 1}^{k}\dbinom{k - 1}{i - 1}\...
1
vote
1answer
54 views

Proving that a preorder traversal of a rooted tree $T(V, E)$ is $O(\lvert V \rvert)$ [closed]

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
10
votes
3answers
418 views

Asymptotic analysis of $x_{n+1} = \frac{x_n}{n^2} + \frac{n^2}{x_n} + 2$

Problem: Let $x_1 = 1$ and $x_{n+1} = \frac{x_n}{n^2} + \frac{n^2}{x_n} + 2, \ n\ge 1$. Find the third term in the asymptotic expansion of $x_n$. I have posted it in MSE six months ago without ...
9
votes
1answer
283 views

Two-term recurrence relation

We consider the following system of recurrence relations for $n \in \mathbb Z$ and $\vert \lambda \vert=1$ with $\lambda \in \mathbb{C}$ $$a_{n+1} = \lambda a_{n-1}+ \lambda^* a_n + \lambda^* n b_n $$ ...
6
votes
1answer
211 views

What is the direct proof of the recurrence relation about lattice path enumeration given by Bizley?

Let $k$ be a nonnegative integer and let $m,n$ be coprime positive integers. Let $\phi_k$ be the number of lattice paths from $(0,0)$ to $(km,kn)$ with steps $(0,1)$ and $(1,0)$ that are never rising ...
0
votes
1answer
79 views

Recurrence relation in matrices

I have the following recursive sequence: $Z_k = Z_{k-1} - AA^TZ_{k-1}xx^T$ where $Z_k \in \mathbb R^{n \times d}, A \in \mathbb R^{n \times d}, d > n, rank(A) = n, x \in \mathbb R^{d \times 1}$ $A$ ...
0
votes
0answers
28 views

if $vec(W_{k-1}) = x_{k-1}\otimes A^Tv_{k-1}$ Then $vec(W_k) = x_k \otimes A^Tv_k$

This question is very simple, but notation heavy. Bear with me. We have a constant matrix $A \in \mathbb R^{n \times d}$ where $d \geq n$ and $rank(A) = n$. We also have a constant vector $b \in \...
4
votes
0answers
129 views

Asymptotics of ratios of polynomially recursive sequences

A sequence $a_n$ is said to be polynomially recursive (P-recursive) if it satisfies: $$p^{[r]}(n)a_{n+r}+\cdots+p^{[1]}(n)a_{n+1}+\cdots + p^{[0]}(n)a_n=0$$ where $p^{[i]}(t)\in \mathbb{Q}[t]$ are ...
2
votes
1answer
201 views

Some determinants which are closely related to recurrences

Let the sequence $(a(n,k))_{ n \in \mathbb{Z}}$ satisfy $$\sum_{j=0}^k c(k,j)a(n-j,k)=0$$ with $c(k,j)=c(k,k-j)$ and $c(k,0)=1$ and with initial values $a(-n,k)=0$ for $1\leq n\leq{k-1}$ and $a(0,k)=...
0
votes
0answers
34 views

Find coefficient such that limit is invertible matrix (interesting and in-depth)

First the question. Let $A \in \mathbb R^{n \times d}$ where $d > n$ and $rank(A) = n$. Let $b \in \mathbb R^{n \times 1}$. We are interested in the sequences $\{W_k\} \subset \mathbb R^{d \times d}...
2
votes
1answer
156 views

Approximation of a quadratic map by using a limited binary representation

We are given the sequence defined by the recurrence relation $a_{n+1}=a_n^2+1$ with $a_0=0$. Let $h$ be a positive integer (it represents the maximum number of bits, up to a constant factor, that we ...
10
votes
1answer
1k views

“Laurent phenomenon”?

Define the recurrence \begin{align*} n(2n+x-3)u_n(x) &=2(2n+x-2)(4n^2+4nx-8n-3x+3)u_{n-1}(x) \\ &-4(n+x-2)(2n-3)(2n+2x-3)(2n+x-1)u_{n-2}(x) \end{align*} with initial conditions $u_0(x)=0$ and $...
0
votes
1answer
69 views

Closed-form for recursive “geometric-like” recursion

I asked this question of MSE, but to no avail; alas, here I am. Let $k>0$, $C\geq 1$, $\alpha \in (0,1]$, and let $(x_n)_{n\geq 1}$, be a sequence of real numbers given by the recursion $$ x_{n+1} =...
4
votes
0answers
92 views

Consecutive integers which are products of Fibonacci numbers

Let $F_1, F_2, \dots$ be the sequence of Fibonacci numbers, and let $\mathcal{M}$ be the set of positive integers expressible as a product of Fibonacci numbers (OEIS A065108). One can prove that $$F_{...
1
vote
1answer
145 views

The number of permutations of given order

I want to count the number of permutations of the given order $k$ in $S_n\;(\sigma^k=id,\sigma^l\neq id\;for\;l<k)$. I found some works about that problem, but they are more general than necessary. ...
2
votes
1answer
109 views

“Approximating” linear recursion with homogenous polynomial coefficients by linear recursion with constant coefficients

In a lecture I once attended, I remember the speaker using a result of the following nature: $``$Let $\{A_n\}_{n=1}^\infty \subset \mathbb R$ be a sequence satisfying a recursion of the form $$P(n) ...
0
votes
0answers
36 views

Laplace transform of sum of random variables in first hitting time problem

Let me refer to the example here. Suppose $X$ is a birth-death (BD) process (represents population size) that evolves by: $X \to X+1$ if a birth occurs with rate $\mu$, $X \to X-1$ if a death occurs ...
3
votes
1answer
160 views

On pseudoprimes to the base $a$ (Fermat pseudoprimes)

In 1980, C. Pomerance, J. Selfridge, and S. S. Wagstaff defined a pseudoprime to the base a to be any composite odd $n$ such that $n \mid a^{n-1} - 1$. More recently, in 2013, S. S. Wagstaff referred ...
6
votes
1answer
381 views

Reciprocity for fans of bounded Dyck paths

This is a continuation of some questions asked by Johann Cigler: Number of bounded Dyck paths with "negative length" and Number of bounded Dyck paths with negative length as Hankel ...
0
votes
1answer
107 views

Hybrid numeration system on $[0,1]^2$

Let $X_0,X_1\in [0,1]$ and $b_1,b_2>0$ be integers. We are going to create a numeration system for vectors $(X_0,X_1)$, the base being the vector $(b_1,b_2)$, as follows. Recursively define $X_k=\{...
2
votes
2answers
618 views

Recursive random number generator based on irrational numbers

Here $\{\cdot\}$ and $\lfloor \cdot\rfloor$ denote the fractional part and floor functions respectively. For a negative, non-integer number $x$, we use the following definition: $\{x\}=1-\{-x\}$. If $...
11
votes
1answer
347 views

Fibonacci-like sequences in $\mathbb{F}_q$ where each element only depends on the previous one

Given a prime power $q$, consider all sequences $(a_n)_{n\in\mathbb{Z}}$ in $\mathbb{F}_q$ for which $a_{n+1}=a_n+a_{n-1}$ for all $n\in\mathbb{Z}$. Call such a sequence simple if there exists a ...
1
vote
0answers
62 views

Quick ways to compute transition matrices for classical symmetric function bases

I am trying to implement quick algorithms for computing the transition matrices involving the monomial, power-sum, elementary, complete homogeneous and Schur polynomials. There are several relations ...
4
votes
1answer
257 views

A sequence reminiscent of Fibonacci's recursion

The sequence in question is A296768 in the Online Encyclopedia. It starts with 1, 3, 5, 9, 11, 17, 24, 32, 36, 46, ... It is obtained by starting with the positive integers in order, (b(i)= i for all ...
10
votes
2answers
280 views

Closed walks on an $n$-cube and alternating permutations

Let $w(n,l)$ denote the number of closed walks of length $2l$ from a given vertex of the $n$-cube. Then, it is well-known that $$\cosh^n(x)=\sum_{l=0}^{\infty}\frac{w(n,l)}{(2l)!}x^{2l}.$$ ...
0
votes
1answer
176 views

How to solve this conditional recurrence relation?(two variable and conditions)

I am trying to solve the following recurrence relation $4 \leq n \;\; \; \; \; \;$ and $\; \; \; \; 2\leq i \leq \lfloor{\frac{n}{2}}\rfloor$ $F(2i,n)=$ $\begin{cases} \frac{1}{2(2i)-5}F(2i-2,...
0
votes
0answers
31 views

Hawkes Process : recursive formula for : $R'_{m,n} (k) = \sum_{ \{i : t_i^n < t_k^m \} } (t_k^m - t_i^n) \exp ( - \beta_{m,n} ( t_k^m - t_i^n ) ) $

I need to use a function inside a my code and it is very expensive. I'd like to know if there exists a recursive version of it. \begin{align*} k = 1, \quad R'_{m,n} (k) &= 0 \\ k \geq 2, \quad R'_{...
0
votes
2answers
195 views

Solving a recurrence relation involving binomial coefficients

This question originates from a graph neural network architecture (see 1) in which an edge-labelled graph $G=(V,E,\eta)$ of size $|V|=n$ with $\eta:E\to \mathbb{R}^{s_0}$ is represented as a "tensor''...
4
votes
0answers
360 views

Square root of a sequence given by a linear recurrence relation

This question is closely related to this one but in a sense a converse of it. Let us concentrate for simplicity on a third order relation $x_{n+3}=ax_{n+2}+bx_{n+1}+cx_n$ with given intial terms $x_1,...
6
votes
0answers
160 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|n,d>1}{(-1)^d \frac{u(n)}{du(\frac{n}{d})^d}r\Big(\frac{n}{d}\Big)^d}+\frac{(1-q)^{n-1}u(n)}{n[n]}$$ with $...
1
vote
1answer
99 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
132 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
184 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
53 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$ ...
5
votes
0answers
199 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
208 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
90 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
163 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
168 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
39 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
432 views

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

For all $n \in \mathbb{N}$, set $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{otherwise} \...

1
2 3 4 5