Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

2
votes
2answers
109 views

Find formula for recurrence relation with two function and two variables

$f(n,k) = 2g(n-2,k-1)+f(n-1,k)$ $g(n,k) = g(n-1,k-1)+f(n,k)$ when $n\le0$ or $k\le0: \quad f(n,k) = 0$ when $n < k:\quad f(n,k) = 0$ when $n-k<-1:\quad g(n,k) = 0$ when $k=0:\quad g(n,k) = 1$ $...
1
vote
1answer
107 views

Finding closed form of recurrence relation in two variables [closed]

I have a recurrence, $$F(n, m) = F(n-1, m) + F(n, m-1) + F(n-1,m-1) $$ $$F(n,1) = 0$$ $$F(1,n) = 2*(n-1)$$ I would like to compute $F(N,M)$ in terms of $N$ and $M$. The system is defined for $1 \...
0
votes
0answers
85 views

Solve a recurrence relation in two variables [closed]

How do we solve the relation $$ f(n,m) = f(n-1,m) + f(n-1,m-1) + f(n-2,m-1), $$ where the value of $n\ge3$, $1\le m\le n$ and $f(n,1) = 2n$.
9
votes
0answers
208 views

How explain these remarkable empirical observations about mod 3 modular forms of levels 1 and 5?

Define $b(n)$ by $b(0)= 0$, $b(3n)= 9b(n)$, $b(3n+1)= 9b(n) + 1$, $b(3n+2)= 9b(n) + 3$. (This sequence does not show up in the OEIS, but the similar Moser-de Bruijn sequence A000695 appears in many ...
2
votes
0answers
65 views

Convergence Based on Recurrence Relation

I am studying a sequence based on the following recurrence: $$X[t] = \sqrt{\alpha X[t-1]^2+(X[t-1]^2-\alpha X[t-2]^2)\frac{(2-X[t-1])^2}{X[t-1]^2}}$$ $$X[0]=0$$ $$X[1]>0$$ $$\alpha \in (0,1)$$ I ...
2
votes
1answer
94 views

time delay ergodic theorem

given dynamic system $(X, \mathcal{B}, F, \mu), \mu \circ F^{-1}=\mu, F $ is mixing, $ A \in \mathcal{B}, s.t. \mu(A) >0 $. consider dynamic system $(X\times X, \mathcal{B}\otimes \mathcal{B}, ...
3
votes
1answer
255 views

Detecting if a series represents a rational function

A lemma by Kronecker states that the series $f(z):= \sum_{i=0}^{\infty} c_i z^i$ represents a rational function if and only if for every $m \gg 0$ the determinant of the following matrix is equal to ...
0
votes
0answers
97 views

Does this recurrence yields only prime numbers?

The title of this question is merely illustrative, since I do not expect an answer by yes or not, but I seek some reference on the subject. In this article: https://pdfs.semanticscholar.org/e9be/...
11
votes
1answer
490 views

A recursive formula

$$a_0 = 1, \ \ a_{n+1} = \ 1+\frac{n *a_n}{n+a_n} , \ \ n=0,1,2,3,4,...$$ I have built the above recursive formula. Some terms of sequence are: 1, 1, 3/2, 13/7, 73/34, 501/209, 4051/1546, 37633/...
2
votes
0answers
116 views

lower bounding the absolute value of a determinant

In a problem that I'm working on currently, the following question came up and I feel this should be fairly elementary, but I couldn't prove it myself/couldn't find a reference. Any pointers or ...
1
vote
0answers
29 views

linear difference inequality with error

Let $(\alpha,\gamma,\beta)$ real number such that $\alpha+\gamma+\beta=1$, let $(e_n)_{n\in\mathbb{N}}$ be a summable non-negative sequence and let $(u_n)$ be a non-negative sequence such that $\...
0
votes
1answer
98 views

Solutions to linear equations from recurrence sequences with no repeated roots

Let $U=(u_n)_{n=0}^{\infty}\subseteq\mathbb{C}$ be a sequence enumerated by a linear homogeneous recurrence relation with constant coefficients, i.e., there is some $d\geq 1$ and $a_1,\ldots,a_d\in\...
4
votes
1answer
136 views

An inequality involving $k$-generalized Fibonacci numbers

I have worked on a Diophantine equation by using transcendental and reduction methods given by Baker and Davenport. However, to solve completely the equation I have one complicated case and I proved ...
0
votes
0answers
60 views

the enumeration of 2 dimensional lattice walks with fixed number steps and largest distance from the end point ti the origin

There is actually an one dimensional version of this problem. For each step of the lattice walk, we can move either east for one unit or west for one unit. The problem is that given a fixed $n$ steps ...
0
votes
1answer
183 views

Funny recurrence

Could someone help me solve the following recurrence? $$ T(k) \le 1+\sum_{i=1}^{n_k}T(k_i), $$ where $n_k\le k$, $k_i\le \frac23 k$ $\forall i = 1, \dots n_k$, and $\sum_{i=1}^{n_k}k_i \le k$. The ...
0
votes
1answer
142 views

When does this recurrence stop?

Denote $n_i=n_{i-1}-\sqrt[k]{n_{i-1}}$. If $n_0=n$ then what is the minimum $i$ at which $n_i<2$ holds? Is there a standard technique to solve such problems? Any references?
6
votes
0answers
85 views

Deciding when certain elements of $L[[x]]$, coming from recursions, are algebraic over $L(x)$

Let $L$ be a finite field of characteristic $2$. Suppose that for some $k > 0$ we are given elements $A(0),\, A(1), \dots, \, A(k-1)$ and $c(0),\, c(1), \dots,\, c(k-1)$ of $L[t]$. Define $A(n)$ ...
0
votes
0answers
33 views

Is this the best primality test using second order recurrences (Lucas Sequences)?

this is the copy of the question asked at mathematics stack exchange. original question https://math.stackexchange.com/q/2705983/469085 little Explanation Using second order lucas sequences $$U_{n +...
3
votes
1answer
286 views

Is there a better proof for this than using the 10-adic numbers?

Here are two somewhat strange sums using the shifted decimal forms of the powers of $3.$ $\begin{equation*}\begin{array}{ccccccc} &1&&&&&& \\ &&3&&&&...
0
votes
1answer
325 views

Is there any number other than 109 whose reciprocal contains the Fibonacci sequence? [closed]

Let $p$ be any odd number, and compute $1/p$ to $p$ decimal places. Compare your answer with the string that is formed by appending all remainders of $(10^n\ \text{mod p}) \text{ mod p}$ where ${0 <...
22
votes
1answer
494 views

Rim hook decomposition and volume of moduli spaces

I did some computer experiments, counting the number of rim-hook decompositions (aka border-strip decompositions) of rectangles of shape $2n \times n$, where each strip has size $n$. Here are 12 of ...
-2
votes
1answer
121 views

Is there any pseudoprime that pass this test above tested range, or any prime that does not show these ending patterns?

if the recurrence sequence is defined by the following foormula, $d_{n + 3} = 3d_{n + 2} - d_{n + 1} - 2d_n$ where $d_1 = 1, d_2 = 3$ and $ d_3 = 7$, this produce the following complex sequence $$1, ...
3
votes
2answers
262 views

Seeking proof to an asymptotics of a recursion or functional equation

My question on math.stackexchange.com and the continuation by an answer to it gives the two summation expressions for the recursion $$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\...
2
votes
1answer
639 views

Power tower made of $2$s and $3$s: too high, too soon?

A power tower of a number $x$ is typified by $$ x^{x^{x^{x^{x^{x^{x^{x^{x^x}}}}}}}}.$$ Here, however, we take the liberty of referring to the set $T$ of "$\{2,3\}$-power towers"; i.e., numbers $$...
4
votes
1answer
161 views

Second order recurrence relation for third order polynomial root

Consider this recurrence relation: $$ \begin{eqnarray*} f_0&=&1\\ f_n&=& \sum_{m=0}^{n-1} \frac{\left(\frac{m+3}{2}\right)_{m-1}}{\left(\frac{m+2}{2}\right)_m} f_{n-m-1} f_m\ \ \ \...
5
votes
1answer
245 views

Simply generated sequences with mysterious differences

Suppose that $a_0 < a_1,$ $b_0 < b_1,$ and $$a_n=a_1b_{n-1}+a_0b_{n-2}+qn+r$$ for $n \geq 2$, where $a_0,a_1,b_0,b_1,q,r$ are integers such that $(a_n)$ and $(b_n)$ are increasing and ${(|a_n|)}$...
7
votes
2answers
346 views

Limit associated with complementary sequences

Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_0b_{n-1}+a_1b_{n-2}$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs ...
2
votes
1answer
278 views

Is there a good bound for this double exponential recursion?

Denote when $k>2m$ $$f_k(2m)=\sum_{i=1,i\geq1}^m\binom{2m}{i}f_k(i)f_k(2m-i)$$ $$f_k(2m+1)=\sum_{i=1,i\geq1}^m\binom{2m+1}{i}f_k(i)f_k(2m+1-i)$$ $$f_k(0)=1.$$ $$f_k(1)=k.$$ What is a good bound ...
3
votes
1answer
118 views

Does a linear Recurrence relation with an nonlinear relation between elements can be solved by a closed formula?

I came across with this cool recurrence relation, and unfortunately i couldn't find sufficient mathematical tools to form it to a closed formula. i read several posts from math overflow saying that ...
0
votes
0answers
59 views

Explicit representation for a recurrence relation yielding the Hilbert series of certain ideals

I would like to find an explicit representation for the recurrence relation $(n+1) \cdot P_{n+1}(X) = P_1(X) \cdot P_n(X) - a(n)\cdot P_{n-1}(X) \, ,$ where $P_i(X)$ are polynomials in the variable $...
1
vote
0answers
131 views

(b,c) rank 2 cluster algebras

Let $x$ and $y$ be variables. Consider the following recurrence: \begin{equation} u_{n}:= \begin{cases} \displaystyle{\frac{1+u_{n-1}^b}{u_{n-2}}} & if\ n\ \text{is even},\\ &\\ \displaystyle{\...
20
votes
2answers
414 views

Do these polynomials have alternating coefficients?

In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence $$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$ Thus: ...
1
vote
2answers
452 views

Can these sequences stay integer-valued as many times as we want and then fail?

Edit: Suppose that we choose some integer $d$ and some natural number $c=c_2$. Then if we plug those values into $$ c_{n+1}=\frac{c_n(c_n+n+d)}n $$ and observe the behavior of this recursively ...
26
votes
1answer
574 views

Is there any positive integer sequence $c_{n+1}=\frac{c_n(c_n+n+d)}n$?

In a recent answer Max Alekseyev provided two recurrences of the form mentioned in the title which stay integer for a long time. However, they eventually fail. QUESTION Is there any (added: ...
14
votes
1answer
1k views

Simple recurrence that fails to be integer for the first time at the 44th term

The sequence defined by $a_0=a_1 =1$ and $$ a_n = \frac{1}{n-1}\sum_{i=0}^{n-1}a_i^2, \quad n > 1 $$ fails to be integer for the first time at $a_{44}$. Why?? You can verify the statement by ...
1
vote
0answers
129 views

Proving the existence of a sequence with recursive growth constraints

Fix $0 < c < 1/3$. Show that there exists a strictly increasing sequence $a_k > 0$, a sequence $b_k \geq 0$, and an infinite set $K \subseteq \mathbb{Z}_{>0}$ such that \begin{align}\...
0
votes
0answers
91 views

stochastic recurrence relation “convergence”

Consider a recurrence relation $x_n = f(x_{n-1})$. Suppose $f(x_n)<0$ for some "large enough" $n$. Now consider a "stochastic variant" $x_n = f(x_{n-1})+y_n$ where $y_n$ is a sequence of random ...
2
votes
1answer
173 views

Solve functional equation: $\frac{F(x)}{F(1)} = 2F\left(\frac{(1+x)^2}{4a}\right)-F(x/a)$

Solve this functional equation: $$\frac{F(x)}{F(1)} = 2F\left(\frac{(1+x)^2}{4a}\right)-F(x/a)$$ for $F(x)$ where $a > 0$ is a parameter. I know there is a trivial constant solution, $F(x) = 1$. ...
1
vote
0answers
89 views

Find bivariate generating function for two-dimensional sequence

How to find generating function for triangle of squares of elements in this sequence? I. e. for $1 + (1 + 4x)y + (1 + 9x + 16x^2)y^2 + ...$ ? It seems that ordinary approach with arithmetic ...
7
votes
1answer
236 views

Counting some binary trees with lots of extra stucture

While working on some computations on Hilbert schemes, I came across the following combinatorial problem. Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...
6
votes
0answers
143 views

Is Somos-8 $\mod 2$ periodic?

It is known that the Somos-$k$ sequences for $k\ge 8$ do not give integers. But the first terms of Somos-8 sequence $s_n=a_n/b_n$ $$1, 1, 1, 1, 1, 1, 1, 1, 4, 7, 13, 25, 61, 187, 775, 5827, 14815,\...
22
votes
2answers
649 views

Possible behaviors of integer sequences that arise from powering nonnegative integer matrices

Let's call a sequence of nonnegative integers $x_1,x_2,\ldots$ matrix-realizable, if there exists a $k\times k$ nonnegative integer matrix $A$ (for some $k$), as well as nonnegative integer vectors $u,...
1
vote
0answers
80 views

Solving a partial difference equation with variable coefficients explicitly

I'm trying to solve the following partial difference equation with variable coefficients: $$a_{i,j,k}=-\frac{j+1}{i}a_{i-1,j+1,k-1}- \frac{k+1}{i}a_{i-1,j-1,k+1}, $$ defined on the grid $(i,j,k) \in \...
3
votes
1answer
240 views

Bound on the number of primitive divisors of the $n$th Fibonacci number

It is a result of Carmichael that for any integer $n > 12$, the Fibonacci number $F_n$ has at least one primitive divisor, that is, a prime factor $p$ such that $p$ does not divide any $F_m$ with $...
1
vote
2answers
341 views

Linear two-dimensional recurrence relation

As part of my research I have to analyze recurrence relations of the form $$f_{m,n} = af_{m-1,n} + bf_{m,n-1} + c,$$ where $a,b,c$ are any given real numbers and $f_{m,0}$ and $f_{0,n}$ any given ...
0
votes
0answers
189 views

Resolve a recursive formula with combination number

For integers $n\ge2$ and $k\ge2$, consider the recursion $$ p(n,k) = \frac{{k^{n - 1} }}{{k^{n - 1} - 1}}\left[1 + \sum\limits_{i = 2}^{n - 1} {\frac{{\binom{n}i (k - 1)^{n - i} }}{{k^{n - 1} }}p(i,...
6
votes
1answer
406 views

About a Ramanujan-Sato formula of level 10, a recurrence, and $\zeta(5)$?

This is a long shot, but I am curious where it leads. First, recall the Dedekind eta function $\eta(\tau)$. I. Level 6 Define, $$\begin{aligned} j_{6A}(\tau) &= \Big(\sqrt{j_{6B}(\tau)} - \...
2
votes
1answer
145 views

Recurrent relation with several indices ( How many $m$-dim cubes in $n$-dim cube )

Actually, I will be asking two, but related, questions. Question 1. Is there some theory about recurrent relations with several indices. For example, If we have a relation on $A_{i;j}$: $$A_{i+\...
3
votes
1answer
110 views

Recurrence relation asymptotics

A continuation from my two previous posts: I have got the following recurrence which describes polynomials: $$ C_n(a) = \sum\limits_{t=0}^{n-1} \binom{n-1}{t} a^{t(n-t)} C_t(a) $$ where $C_1(a)=C_0(...
1
vote
0answers
76 views

Primes dividing functions defined by linear recurrence relations with constant coefficients

For Fibonacci numbers $F_n$ it holds that $p|F_{p-(\frac{5}{p})}$, if $p$ is an odd prime (Legendre symbol). I guessed that the number $5$ came from the roots of the characteristic polynomial and ...