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

Questions tagged [recurrences]

The tag has no usage guidance.

1
vote
0answers
38 views

A conjectural formula for the “minimal degree function”, $k\rightarrow d\min(k)$, attached to recursion, $f\rightarrow A(f)$, in char $3$

THE RECURSION: $f\rightarrow A(f)$ $A: t(\mathbb{Z}/3)[t^3]\rightarrow t(\mathbb{Z}/3)[t^3]$ is the $\mathbb{Z}/3$-linear map with $A(t)=0, A(t^4)=t, A(t^7)=t^4$, and $A((t^9)f)=(2t^9)A(f)+(t^3)A((t^...
6
votes
1answer
210 views

$p_n(x,y)=\sum_{i=0}^{n-1}x^{n-1-i}y^{i}$ is always an integer

Does anyone know if the following problem has ever been studied? Let $a$ and $b$ be two real numbers and consider the polynomial: $$p_n(x,y)=\sum_{i=0}^{n-1}x^{n-1-i}y^{i}$$ where $n$ is a ...
0
votes
0answers
26 views

Reference requested about the rank of appearance in the Lucas sequences

Given $u_n$ a Lucas sequence, we define the rank of appearance of $m$ in $\{u_n\}_{n\geq 0}$, indicated with $z_u(m)$, as the smallest positive integer $n$ such that $m$ divides $u_n$. I would like ...
0
votes
0answers
24 views

Solving 2-dimensional recurrence matrix of homogenous polynomials

I know this isn't research-level mathematics, but I posted this on stack exchange, even offered a bounty but got no responses and no comments, so I am hoping to get an answer here. In $2012$, ...
2
votes
0answers
62 views

Curious if this chaotic recurrence relation has a name and/or interesting properties

I was playing around with 2-dimensional recurrence relations and I stumbled upon this: $$ x_{n+1} = \sin(k(y_n + x_n))\\ y_{n+1} = \sin(k(y_n - x_n)) $$ I was wondering if this was a known ...
2
votes
2answers
126 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
125 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 \...
9
votes
0answers
213 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
69 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
256 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
98 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
517 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
122 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
30 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
99 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
139 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
62 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 ...
8
votes
4answers
847 views

Find a formula for the recurrent sequence $q_{n+1}=q_n(q_n+1)+1$

Find an analytic formula for the recurrent sequence $$q_{n+1}=q_n(q_n+1)+1,\;\;q_0\in\mathbb N.$$ (The question was asked on 03.05.2018 by M. Pratsovytyi, see page 109 of Volume 1 of the Lviv ...
0
votes
1answer
185 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
143 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?
7
votes
0answers
88 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
288 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
326 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
499 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
123 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
265 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
640 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
162 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
248 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
350 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
119 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 ...
1
vote
0answers
133 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
421 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
457 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 ...
27
votes
0answers
682 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
130 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
99 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
174 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
92 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
245 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
654 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
257 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
369 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
194 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,...