The recurrences tag has no usage guidance.

**-4**

votes

**0**answers

27 views

### Reccurence relation for [closed]

Hi guys I am a little confused on a question I am working on.
"Write the recurrence relation for: 5, 0, -8, -17, -25, -30,…"
I am getting
Cn= {5 if n=1}
{Cn-1+(2n-1) if n > 1}
...

**0**

votes

**0**answers

61 views

### 2D sequence of integers [closed]

I found the following sequence of integers $a_n^k$, where $n$ and $k$ to extend to infinity. Each row are coefficients of a polynomial, similar to the coefficients of the Legendre polynomials. The ...

**0**

votes

**0**answers

47 views

### Solving Recursive Expression for Counting Unrooted Tree Topologies

The book Bayesian Evolutionary Analysis with BEAST by Alexei J. Drummond et al. (2015) states at section 2.2.1 that the number of rooted unlabelled (binary) tree topologies $a_n$ is given by the ...

**1**

vote

**0**answers

99 views

### A two variable recurrence relation with conditionals

I have arrived at the combinatorial problem of enumerating certain types of ballot paths. This has led to analyzing the sequence defined by the following recurrence
$$
f(n,m) = \begin{cases} f(n, \...

**3**

votes

**1**answer

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

**1**

vote

**1**answer

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

**2**

votes

**1**answer

70 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 $...

**1**

vote

**1**answer

159 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 $\...

**6**

votes

**3**answers

384 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})...

**4**

votes

**1**answer

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

**1**

vote

**1**answer

56 views

### Upper-bounding the value of a generalized Laguerre polynomial (using recurrence relation?)

I would like to produce an easily-interpretable explicit upper bound (i.e. no unspecified constants) for the function
$$
f(n) := L_n^{\left(-n-\frac{d}{2}\right)}\left(-\frac{1}{2}\right), \quad n,d \...

**3**

votes

**1**answer

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

**0**

votes

**0**answers

100 views

### Multidimensional recurrence relations

There are many methods of solving one-dimensional homogeneous linear recurrence relations, i.e. such of the form
$$ a_n = \sum_{k=1}^{m}\alpha_ka_{n-k}.$$
Most widespread use linear algebra or ...

**1**

vote

**0**answers

62 views

### How to solve the following bivariate recurrence?

$$F(n,r) = (1-w(r))F(n-1, r) + w(r-1)F(n-1, r-1)$$
where $w(r)$ is monotonically non-increasing in $r$ and $0 \leq w(r) \leq 1$ with $0 \leq r$
Initial condition:
\begin{eqnarray}
F(0, r) & = &...

**1**

vote

**0**answers

54 views

### Asymptotic growth of $f(x) = 2f(x/2 + x/\ln(x))$

In this paper on the Akra–Bazzi theorem, Tom Leighton mentions in his remark at the bottom of page 8, that a function on the positive reals satisfying $f(x) = 2f(x/2 + x/\ln(x))$ for large enough $x$ ...

**1**

vote

**0**answers

94 views

### For which integer values of $k$ can we find one solution to the equation $\sum\limits_{n=1}^{n=k} \frac{1}{n^s}=0$ by iteration? [closed]

I am trying to find solutions to the well known equation:
$$\sum\limits_{n=1}^{n=k} \frac{1}{n^s}=0$$
Now with this program below I have found that for certain values of the integer $k$ one can find ...

**6**

votes

**2**answers

162 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$...

**2**

votes

**0**answers

101 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+...

**1**

vote

**1**answer

112 views

### Recurrence relations with polynomial coefficients: an undecidable problem

I read once (somewhere) that solving a recurrence relation with polynomial coefficients, in the general case, is an undecidable problem. I can't remember the exact reference and I've been trying to ...

**4**

votes

**0**answers

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

**17**

votes

**1**answer

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

**3**

votes

**1**answer

130 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$-...

**2**

votes

**0**answers

58 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]$....

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

**1**

vote

**1**answer

98 views

### Asymptotic upper bound for recursive function $f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$

I'm looking for an asymptotic upper bound for the function f(x), which is recursively defined as follows: $$f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$$
with $f(1)=1$. I am pretty ...

**0**

votes

**1**answer

170 views

### How to solve a complex recursive relation

Before I get started, let me say for complete disclosure this question came up while I was solving a problem from https://projecteuler.net/.
I've been trying to find a non-recursive representation of ...

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

**2**answers

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

**9**

votes

**3**answers

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

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

**0**

votes

**1**answer

79 views

### Solving the difference equation $h(\vec x)\cdot A(\vec x)=\sum_{i=1}^m A(\vec x - \vec e_i)$

I am trying to solve the following difference equation:
$$h(x_1,x_2,x_3,x_4) \cdot A(x_1,x_2,x_3,x_4)=A(x_1-1,x_2,x_3,x_4)+A(x_1,x_2-1,x_3,x_4)+A(x_1,x_2,x_3-1,x_4)+A(x_1,x_2,x_3,x_4-1)$$
with ...

**1**

vote

**1**answer

81 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&...

**4**

votes

**0**answers

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

**6**

votes

**0**answers

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

**0**

votes

**1**answer

80 views

### Stationary distribution of random walk alias solving uncountably many linear equations [closed]

Let us have interval $I = (i_1,i_2)$, function $f_1 : I \mapsto I$, function $f_2 : I \mapsto I$.
Let $x_0$, $x_1$, $x_2$, ... be series of random variables from interval $I$ denoting random walk. ...

**1**

vote

**0**answers

155 views

### Number of digits in $n$-th term of generalized Fibonacci/Narayana sequence

Let $d$ be a nonnegative integer, and let the sequence ${F_d(n)}$ be defined as follows:
$F_d(n) = 1$ for $n = 0, 1, \ldots, d$
$F_d(n) = F_d(n-1) + F_d(n-1-d)$ for $n>d$
For $d=0$ the sequence ...

**1**

vote

**2**answers

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

**0**

votes

**0**answers

134 views

### Help solving a recurrence relation

For solving a related probability problem, I need to solve the following recurrence relation:-
$q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times \frac{r-(k-1)}{r+b-(k-1)...

**6**

votes

**1**answer

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

**2**

votes

**1**answer

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

**0**

votes

**0**answers

76 views

### For which recurrence relations is it decidable whether a formal power series has a maximal zero coefficient?

In this MSE question, I asked whether one can prove that a generating function has infinitely many coefficients equal to zero. The answer given (and accepted) to that rather broad question was “No”.
...

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

**4**

votes

**2**answers

281 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} +...

**0**

votes

**0**answers

52 views

### A question on bivariate recurrence

Is there a way to get a closed form of this recurrence (albeit approximate):
$$A(n ,k ) = {1 \over {d^k}}A(n-1, k-1) + (1 - {1 \over {d^k}})A(n-1,k)$$
Where, $n,k \ge 0$ and $d \ge 2$ are integers. ...

**9**

votes

**2**answers

320 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), $$
...

**1**

vote

**0**answers

164 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$
\begin{array}{cccccccccc}
1 & = & K_{1}\tbinom{...

**3**

votes

**0**answers

228 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 (...

**1**

vote

**0**answers

101 views

### Convergence and summation of power towers or Ackermann functions

I deleted this at StackExchange as it seems advanced or not very relevant for there and I want to ask here.
Let z be a complex number, $Im(z)\neq 0$ or $Re(z)<4$, m be a natural number, let $f(z,m)...

**2**

votes

**1**answer

193 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_{...

**8**

votes

**1**answer

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