The recurrences tag has no usage guidance.

**26**

votes

**5**answers

1k views

### Multiplying by irrational numbers in combinatorial problems

This is getting no attention on stackexchange.
Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$.
It had escaped my attention until last week, ...

**17**

votes

**1**answer

468 views

### For a linear recurrence sequence $(u_n)_{n\geq 0}$, can $\{i \mid u_i > 0\}$ be the set of Fibonacci numbers?

Question: Is there a linear recurrence sequence $(u_n)_{n\geq0}$ (on the rationals, but I would also be interested by reals) for which $\text{Pos}(u) = \{i \mid u_i > 0\}$ is precisely the set of ...

**16**

votes

**3**answers

701 views

### A question on the Laurent phenomenon

This question is motivated by my answer to 109955. It gives a
recurrence relation satisfied by a function $P(n)$ whose terms a
priori are rational functions (of three variables) with complicated
...

**11**

votes

**4**answers

692 views

### Relating the roots of polynomials to the solution sets of certain functional equations

Consider a functional equation of the following form:
$$\sum_{k=0}^n a_k\,\underbrace{f(f(\cdots f}_{k}(x)\cdots )=0\quad \big(f:\,\mathbb{R}\to\mathbb{R},\;a_i\in \mathbb{R},\;\text{and}\;f^0=\text{...

**11**

votes

**3**answers

548 views

### A characteristic 2 polynomial recursion

Let $c(n)$ in $\mathbb{Z}/2\mathbb{Z}[x]$ be defined by the recursion $$c(n+4)=c(n+3)+(x^4+x^3+x^2+x)c(n)+x^n\cdot(x+x^2),$$ and the initial conditions
$$c(0)=0,\quad c(1)=1,\quad c(2)=x,\quad c(3)=x^...

**10**

votes

**3**answers

325 views

### Limiting probabilities for two-player game drawing random uniform numbers

Consider this simple 2-person game I just made up:
Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. ...

**9**

votes

**3**answers

492 views

### Product of a Finite Number of Matrices Related to Roots of Unity

Does anyone have an idea how to prove the following identity?
$$
\mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix}
x^{-2j} & -x^{2j+1} \\
1 & 0
\end{pmatrix}\right)=
\begin{cases}
...

**9**

votes

**2**answers

319 views

### Faster formula to compute sum over partitions

Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let
$$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j), $$
...

**8**

votes

**1**answer

570 views

### Hamming weight of Fibonacci numbers

The Hamming weight $w(n)$ is the number of 1s in $n$ when written in binary. Is there some effective bound on Fibonacci numbers $F_n$ with $w(F_n)\le x$ for a given $x$?
Clearly only $F_0=0$ has ...

**8**

votes

**0**answers

538 views

### Is this 2x2 determinant sequence positive and increasing?

Let $X_1,X_2,X_3$ be a three discrete (integer and non-negative valued) random variables with local probabilities $a_k:=\mathbb{P}(X_1=k)$, $b_k:=\mathbb{P}(X_2=k)$, $c_k:=\mathbb{P}(X_3=k)$ and $s_k:=...

**7**

votes

**1**answer

1k views

### Beyond Collatz: A $5n+1$ conjecture? [closed]

Let
$$x_{n+1} = \begin{cases} x_n/2 &;\text{if } x_n \equiv 0 \pmod{2}\\ k\,x_n+1 &; \text{if } x_n\equiv 1 \pmod{2} \end{cases}$$
and $k=3$ and $x_n\in\Bbb N$. Collatz conjectured for this ...

**7**

votes

**2**answers

451 views

### The p-adic valuation of a linear recurrence

Let $(u_n)_{n \geq 0}$ be an integer-valued linear recurrence of order $k \geq 1$. Precisely,
$$u_n = a_1 u_{n-1} + \cdots + a_k u_{n - k} \quad \forall n \geq k ,$$
for some $a_1, \ldots, a_k \in \...

**6**

votes

**3**answers

382 views

### Tricky two-dimensional recurrence relation

I would like to obtain a closed form for the recurrence relation
$$a_{0,0} = 1,~~~~a_{0,m+1} = 0\\a_{n+1,0} = 2 + \frac 1 2 \cdot(a_{n,0} + a_{n,1})\\a_{n+1,m+1} = \frac 1 2 \cdot (a_{n,m} + a_{n,m+2})...

**6**

votes

**1**answer

293 views

### Polynomial recurrence relation covering the integers (and then Gaussian integers)

Say that a polynomial recurrence relation (my terminology)
for $f_i$ is:
$k$ initial conditions setting $f_1,\ldots,f_k$ to integers ($\in \mathbb{Z})$.
A recurrence equation of the form $f_i =$ a ...

**6**

votes

**2**answers

158 views

### Asymptotics of a recursion

suppose we have the following two sequences
$$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$
$$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$
where $l$...

**6**

votes

**3**answers

977 views

### References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...

**6**

votes

**5**answers

503 views

### Uniqueness of values in recurrence relations

Given an integer $k > 1$, define the sequences $X(k,n), Y(k,n)$ as follows:
$a=4k-2,$ $y_0 = 1,$ $y_1 = a + 1,y_n = ay_{n-1} - y_{n-2}$
$b = 4k + 2,$ $ x_0 = 1,$ $x_1 = b - 1,$ $x_n = ...

**6**

votes

**1**answer

150 views

### Writing the quotient of solutions of linear ODEs as the solution of a nonlinear ODE

Let $A(x)$ and $B(x)$ be solutions to homogeneous linear ODEs with polynomial coefficients, i.e., $A(x)$ satisfies
$$p_KA^{(K)} + p_{K-1}A^{(K-1)} + \cdots + p_1A' + p_0A=0$$
and $B(x)$ satisfies
$$...

**6**

votes

**0**answers

196 views

### Degenerate linear recurrence sequences

Let $(u_n)_{n \geq 0}$ be a linear recurrence given by
$$u_n = a_1 u_{n-1} + \cdots + a_k u_{n-k} \quad \forall n \geq k ,$$
where $u_0, \ldots, u_{k-1}, a_1, \ldots, a_k \in \mathbb{Z}$. We recall ...

**6**

votes

**0**answers

185 views

### Non-crystallographic cluster algebras

Background
Fomin and Zelevinsky have introduced cluster algebras in an influential article. To define a cluster algebra, Fomin and Zelevinsky have defined a mutation of seeds. Here, a seed $(\mathbf{...

**4**

votes

**3**answers

1k views

### Linear Recurrence Relations in 2 Variables with Variable Coefficients

Consider the following recurrence relation:
$$-2a_{n,m} +a_{n-1,m}+a_{n,m-1}=0,$$
where $a_{n,m} \in \mathbb{C}.$I would like a purely combinatorial way to understand the subspace of solutions to this ...

**4**

votes

**2**answers

278 views

### Strong divisibility of Lucas sequences

Let $a$ and $b$ be relatively prime integers and let $u_n$ be their associate Lucas sequence, i.e., the second order linear recurrence sequence satisfying $u_0 = 0$, $u_1 = 1$ and $u_{n+2} = au_{n+1} +...

**4**

votes

**2**answers

325 views

### Asymptotic growth of recurrence relation $x_n=\min\limits_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2)$

Suppose $a>0$ . Define
$$x_n=\min_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2) \text{ with } x_1=0.$$
Can we find $r>0$ such that there exists two positive constant $c_1,c_2$ such that
$$c_1<\...

**4**

votes

**1**answer

218 views

### Eliminating a variable from a two-variable linear recurrence

In attempting to enumerate a combinatorial class of objects, I've come to a bivariate recurrence:
$$
a_{n,k} = 2a_{n,k-1} + (k+1)a_{n-1,k+1} - ka_{n-1,k} - a_{n,k-2} + a_{n-1,k-1}.
$$
Together with ...

**4**

votes

**0**answers

161 views

### Puzzling behaviour of a recursively defined sequence of functions

This question arose in connection with another problem that I described earlier in Constructing a generating function using a series with all negative and positive powers of a variable. I had certain ...

**4**

votes

**0**answers

132 views

### ``Occasional'' Laurent phenomenon

This question is motivated by Richard Stanley's A question on the Laurent phenomenon (motivated by his answer to the question what is the probability that a scissor became the champion?).
He asked ...

**3**

votes

**2**answers

2k views

### Methods for solving two variable recurrence

I have a recurrence
$$f(i,j) = 1+ \frac{N-i}{N} f(i,j-1) + \frac{i}{N} f(i-1, j)$$
$$f(i,0) = 0$$
$$f(0,j) = j$$
I would like to compute $f(N,M)$ in terms of N and M. The system is defined for $...

**3**

votes

**1**answer

175 views

### Solving recursion / finding generating function of a probability mass function

I am assessing the probability distribution on a running time of some algorithm that we've developed. I am looking for a family of probability mass functions $f_n$ with the following recurrence:
$$
f_{...

**3**

votes

**1**answer

122 views

### Solving algebraic recurrence relations on a cyclic graph

I have a set of $n$ variables $p_1, \ldots p_n$ with $0 \leq p_i \leq 1$ and a defining equation for each of one of the forms:
$p_i = 0$.
$p_i = 1$
$p_i = p_j p_k$ for some $j, k$ with $i, j, k$ all ...

**3**

votes

**1**answer

121 views

### How to deduce the recursive derivative formula of B-spline basis?

Description
Let $\vec{U}=\{u_0,u_1,\ldots,u_m\}$ denotes a non-decreasing sequence of real numbers, i.e, $u_i\leq u_{i+1} \quad i=0,1,2\ldots m-1$.
and the $i$-th B-spline basis function of $p$-...

**3**

votes

**1**answer

368 views

### Books request on nonlinear recurrence relations.

Hi, do you have some sort of a bibliography on advanced techniques in recurrence equations, such as nonlinear ones and others?
As I see it recurrence equations are quite similar to differential ...

**3**

votes

**0**answers

197 views

### Arithmetical properties of certain recurrence relations

Consider the following recurrence relation:
$$(4i+6j+1)(2i+3j)a_{i,j}=3j a_{i+1,j-1}-2i a_{i-1,j}+32i(i-1) a_{i-2,j+1}, i\ge0, j\ge0,$$
$$a_{0,0}=1.$$
This equation appeared in the article (...

**2**

votes

**1**answer

187 views

### General four-term recurrence relations

I was perusing through this paper and I was wondering if there is any literature on general four term recurrence relations. Specifically, say a recurrence of the form
$$A(n)u_{n+3}+B(n)u_{n+2}+C(n)u_{...

**2**

votes

**2**answers

1k views

### How to solve a specific multivariate recurrence relation (or general ones)

How do you solve this recurrence (or multivariate recurrences in general)? Note that $p\in[0,1]$ and $n\in\mathbb{N}$ are given constants, where $np\leq 1$.
$$f:(\mathbb{N}\cup\{0\})\times(\mathbb{N}\...

**2**

votes

**4**answers

2k views

### Recurrence T(N)=T(N/LOGN)+1 [closed]

I'm stuck on the following reccurrence :
T(N)=T(N/LOGN)+1,IF N>2
T(N)=0,if 0<=N<=2
I need a function T(N) for all N>0
Is there some method for solving ...

**2**

votes

**1**answer

67 views

### linear recurrence inequality

Given two real analytic functions, $g(x)$ and $f(x)$, on an open interval $I\subset \mathbb{R}$, it is obvious that $g(x) \leq f(x)$ does not imply $g_n \leq f_n$ (here $g_n = [x^n] g(x)$ denotes the $...

**2**

votes

**1**answer

177 views

### Definition of primitive divisor of a Lucas sequence

If $\{a_n\}_{n=1}^\infty$ is a sequence of integers, then the definition of primitive divisor of one of its terms is quite natural:
Def. 1. A prime number $p$ is a primitive divisor of $a_n$ if $p \...

**2**

votes

**0**answers

95 views

### Factorization of linear recurrences

For each (commutative unitary) ring $R$, let $\mathfrak{R}(R)$ be the set of all linear recurrences over $R$, that is, the set of all sequences $(a(n))_{n \geq 0}$ in $R$ such that
$$a(n+k) = r_1 a(n+...

**2**

votes

**0**answers

56 views

### The characteristic polynomial of the product of two linear recurrences

Let $\mathbb{F}$ be a field and let $(a_n)_{n \geq 0}$, $(b_n)_{n \geq 0}$ be two linear recurrences with terms in $\mathbb{F}$ and respective characteristic polynomials $f(X), g(X) \in \mathbb{F}[X]$....

**2**

votes

**0**answers

164 views

### Master theorem for probabilistically inspired recurrences

Is there a general solution for multi-variable recurrences of the following form which come from Markov chain analysis?
$f(i,j,k) = p_1 f(i-1, j,k) + p_2 f(i, j-1,k) + p_3 f(i,j,k-1) + p_4 f(i-1,j-1,...

**2**

votes

**0**answers

99 views

### Perturbation analysis for three term recurrences

Jacobi polynomials, denoted by $J^{(\alpha,\beta)}_n$, on $[-1,1]$ satisfy a three term recurrence
$$ J_{n+1}^{(\alpha,\beta)}(x) = (A_n+B_nx)J^{(\alpha,\beta)}_n + C_nJ_{n-1}^{(\alpha,\beta)}(x), \...

**2**

votes

**0**answers

171 views

### Partitions of central sets via dynamical systems

In the book "Recurrence in Ergodic Theory and Combinatorial Number Theory", 1981, Furstenberg introduced the notion of central sets.
He proved in Theorem 8.8 that in each finite partition of $\mathbb{...

**2**

votes

**1**answer

768 views

### Three term recurrence relation.

For given $n,\ell\in\mathbb N_0$, I am interested in studying the following recursion relation for some $\mu\in\mathbb R$:
$$\sqrt{-1} \tfrac{j(\ell-j+1)(n-j+1)(n+j+1)}{2(2j-1)(2j+1)} a_{j-1} - \...

**1**

vote

**2**answers

115 views

### Transforming a recurrence to the product of two other recurrences

This question deals with sequence:
$$a_0 = 0,\ a_1 = 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6$$
The question is about establishing that $a_n$ is a composite number (except some finite cases).
In one ...

**1**

vote

**1**answer

231 views

### Infinitely many sufficiently large powers in linear recurrences

Edit Aaron solved the original question with the
fourth order $$ a(n)=n2^n+\frac{(-1)^n-1^n}{2} $$
trying to make the question harder.
Let $a(n)$ be a linear recurrence with constant coefficients,
of ...

**1**

vote

**1**answer

158 views

### find solution of complex number recurrence equation

I have the following recurrence equation:
$$(\mu\ n + \nu) f_{n} + J\Phi^{*} \sqrt{n+1}f_{n+1} + J\Phi\ \sqrt{n}f_{n-1} = 0$$
for complex numbers $f_{n}$ where $n = 0,1,2,3,...,\infty$ and complex $\...

**1**

vote

**1**answer

79 views

### recursive equation to solve( similar to combinatorics)

I have this recursive equation:
$$\begin{align*} F(m,n)=F&=F(m,n-1)+F(m-1,n)-F(m-1,n-1-m) \\\\ F(m,0)&=F\left(m,m(m+1)/2\right)=1\\ F(m,i)=0&=0\text{ if i<0, i> }i<0\text{ or }i&...

**1**

vote

**1**answer

338 views

### Closed form solution to an iterative equation.

$f(n+1) = f(n) + f(n)^{a}$ where $a \in (0,1)$ and $n \ge 1$ with $f(1) = m$.
If $a=0$, we see $f(n) = m + n - 1$ and if $a=1$, we see $f(n) = 2^{n-1}m$. So the recursion seems to interpolate ...

**1**

vote

**2**answers

117 views

### A recursive Double sequence related to uniform Cardinal B-spline

Given a sequence $A_n(k)$ defined as follows:
$A_0(0)=1$, $A_0(k)=0$ for all nonzero integers $k$ and
$$A_{n}(k)=(n+1-k)^2A_{n-1}(k-1)+2(n(n+1)-k^2)A_{n-1}(k)+(n+1+k)^2A_{n-1}(k+1)$$
for all positive ...

**1**

vote

**1**answer

57 views

### linear recurrence inequality of positive terms

This is a follow up on my previous linear recurrence inequality question.
I have some matrices which satisfy a linear recurrence formula of the form
$$
A_{n+1} = \alpha A_{n} + \beta A_{n-1},\qquad n\...