# Questions tagged [recurrences]

The recurrences tag has no usage guidance.

207
questions

**0**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**3**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

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

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