The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
176 views

Solving a two dimensional non-homogenous linear recurrence

How one can solve the following recurrence: \begin{align} X[i,0] &=0 \quad \forall i =1,\ldots, m\\ X[m,n] &= a_n X[m,n-1]+b_n \sum_{i=k_m}^{m-1}X[i,i] +c_n \end{align} Where $a_i\ge 1 ,~ 0 ...
4
votes
2answers
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<\...
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, ...
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 ...
6
votes
0answers
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{...
0
votes
0answers
78 views

Approximate closed-form solution for a recurrence

Find an (approximate) closed-form solution for $S(m, b)$. $$S(m,b)=\sum_{i=0}^{\lfloor (e-1)/2\rfloor}{e \choose i}S(m-1, b-i) \quad + \sum_{i=\lfloor (e-1)/2\rfloor+1}^{\min(b,e)}{e\choose i}{(...
1
vote
1answer
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 ...
0
votes
1answer
338 views

Giving a general term of a recursive function, and upper bound for it

Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$. Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise Let $b_{t+1}...
6
votes
3answers
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 ...
2
votes
0answers
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,...
4
votes
3answers
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 ...
3
votes
2answers
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
1answer
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 ...
1
vote
2answers
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
0answers
101 views

Trying to get an idea of the maths I could use for this optimization problem

Firstly, apologies if some of the notation or terminology is odd, or if I am defining functions that have standard notation associated with them already - I am not familiar with the concepts in this ...
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
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{...
6
votes
5answers
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 = ...
16
votes
3answers
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 ...
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$. $$f:(\mathbb{N}\cup\{0\})\times(\mathbb{N}\...
2
votes
1answer
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
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 = A_{\lfloor{n/2}\...
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 ...