The tag has no usage guidance.

learn more… | top users | synonyms

26
votes
5answers
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
1answer
422 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
3answers
671 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
4answers
635 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 ...
10
votes
3answers
299 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. ...
10
votes
3answers
492 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 ...
9
votes
3answers
478 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
2answers
305 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
1answer
534 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
0answers
525 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 ...
7
votes
1answer
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
1answer
308 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
1answer
285 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
2answers
147 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 ...
6
votes
3answers
860 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
5answers
494 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
1answer
144 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
0answers
178 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
0answers
159 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 ...
4
votes
3answers
990 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
2answers
270 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
2answers
315 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 ...
4
votes
0answers
110 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 ...
3
votes
1answer
75 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 ...
3
votes
1answer
342 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
0answers
123 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
0answers
195 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
2answers
1k 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 ...
2
votes
1answer
167 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 ...
2
votes
2answers
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$. ...
2
votes
4answers
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
1answer
161 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
1answer
89 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 ...
2
votes
0answers
91 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 ...
2
votes
0answers
55 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 ...
2
votes
0answers
162 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 ...
2
votes
0answers
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
0answers
168 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 ...
2
votes
1answer
696 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
2answers
111 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
1answer
226 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
1answer
74 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 ...
1
vote
1answer
292 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
2answers
112 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
1answer
88 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 ...
1
vote
1answer
197 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
1
vote
0answers
88 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 ...
1
vote
0answers
138 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
0answers
149 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 & = & ...
1
vote
0answers
99 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 ...