Questions tagged [recurrences]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
125 views

Explicit expression for recursive sums - II

A twist on just unfolded recursive summation formula. Let polynomials in nonnegative integer variables $t_1,t_2,\dots$ be defined by the recurrence: \begin{split} g_0 &= 1, \\ g_k(t_1,t_2,\dots,...
user avatar
9 votes
2 answers
383 views

Explicit expression for recursive sums

Let $t_1,t_2,\dots,t_k$ be non-negative integers. Can the following sum $$f_k(t_1,t_2,\dots,t_k):=\sum_{j_1=0}^{t_1} \sum_{j_2=0}^{t_2+j_1} \sum_{j_3=0}^{t_2+j_2} \dots \sum_{j_k=0}^{t_k+j_{k-1}} 1$$ ...
user avatar
0 votes
1 answer
73 views

Reducing recurrence relations mod10 [closed]

I have been playing around with integer sequences as of late, and the following question occurred to me: Suppose for $m$ fixed we have some some initial values $a_1,\cdots,a_m$ and for all $n\in\...
user avatar
1 vote
0 answers
99 views

Self-referencing recurrence relation with exponential

I have the self-referencing recurrence relation $$ d(0) = 0 $$ $$ d(1) = a $$ $$ d(n+1) = d(n) + a*e^{-(\frac{d(n)-n*c}{b})^4} $$ Written as a sum: $$ d(N) = a*\sum_{n=0}^{N}e^{-(\frac{d(n)-n*c}{b})^...
user avatar
  • 11
0 votes
1 answer
35 views

Recursive function - proof by induction

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists. I've encountered the following function: $f([])=[]$ $f([x])=[x]$, for $x \in \Sigma$ $f(x:L)=f(L)$, for $x \in \Sigma$ and $L \in [ \...
user avatar
  • 31
2 votes
1 answer
95 views

Does the set of matrices with bounded recursive products form a fractal?

We are given three matrices $A,B,C$ which have determinant 1, are not unitary and that their size is the same. Consider the following process. On each step we take three words $W_1,W_2,W_3$ consisting ...
user avatar
1 vote
0 answers
67 views

Quasiperiodic sequence, finite differences, recursion

Consider a sequence $\{an\}$ consisting of fractional parts of the numbers $an$ for natural numbers $n$ where $a$ is an irrational number. Its $n$th value is in the interval $(x;y)$ for numbers $n = ...
user avatar
65 votes
2 answers
3k views

Function that produces primes

For any $n\geq 2$ consider the recursion \begin{align*} a(0,n)&=n;\\ a(m,n)&=a(m-1,n)+\operatorname{gcd}(a(m-1,n),n-m),\qquad m\geq 1. \end{align*} I conjecture that $a(n-1,n)$ is always ...
user avatar
0 votes
0 answers
87 views

Conjecture on a sieve of Flavius Josephus

Flavius Josephus's sieve: Start with the natural numbers; at the $k$-th sieving step, remove every $(k+1)$-st term of the sequence remaining after the $(k-1)$-st sieving step; iterate. Some examples: ...
user avatar
1 vote
1 answer
55 views

Stern-Brocot tree and subtree

Let $a(n)$ be A007306, denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range $[0,1]$). Let $b(n)$ be A002487, Stern's diatomic series (or Stern-Brocot sequence): $b(0) = 0, ...
user avatar
4 votes
3 answers
195 views

Infinite sum of Laguerre polynomials: is $\sum_{k=0}^{\infty}\frac{n!}{(k+n)!}x^kL_n^k(x)^2=e^x+P(x)$, with $P$ a polynomial of degree $2n-1$?

I have the following expression: $$ \sum_{k=0}^{\infty}\frac{n!}{(k+n)!}x^k(L_n^k(x))^2, $$ where $$ L_n^k(x)=\sum_{j=0}^n(-1)^j\binom{n+k}{n-j}\frac{x^j}{j!} $$ is the usual associated Laguerre ...
user avatar
  • 83
8 votes
4 answers
271 views

How to find the asymptotics of a linear two-dimensional recurrence relation

Let $d$ be a positive number. There is a two dimensional recurrence relation as follow: $$R(n,m) = R(n-1,m-1) + R(n,m-d)$$ where $R(0,m) = 1$ and $R(n,0) = R(n,1) = \cdots = R(n, d-1) = 1$ for all $n,...
user avatar
  • 195
0 votes
1 answer
81 views

Sum of part of consecutive terms of expansion of (x+y)^n

Let $S(x, y, m_1,m_2, n) = \sum\limits_{i=m_1}^{m_2} \binom{n}{i}x^i y^{n-i}$, where $0 < m_1\leq m_2 < n$. I want to derive the relation between $S(x, y, m_1, m_2, n)$ and $S(x, y, m_1-1, m_2, ...
user avatar
  • 103
3 votes
1 answer
269 views

Polynomial function defined recursively by a resultant - is it well defined?

Preliminaries Let $ n $ be an integer such that $ n \geq3 $. Denote $ \left[ n \right] \equiv \{1,2, \ldots ,n \} $. Let $ P $ be a non-empty subset of $ \left[ n \right] $ such that $ \left|P \right| ...
user avatar
6 votes
0 answers
89 views

Bounds on exponential and character sums of ratio of linear recurrences

Let $\mathbb{F}_q$ be a finite field of $q$ elements, let $\chi$ be a non-trivial additive character of $\mathbb{F}_q$, and let $\psi$ be a non-trivial multiplicative character of $\mathbb{F}_q$. Also,...
user avatar
  • 111
2 votes
1 answer
96 views

Modulo $2$ binomial transform of A243499 applied $k$ times

Let $m \geqslant 1$ be a fixed integer. Let $f(n)$ be A007814, exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. ...
user avatar
0 votes
1 answer
136 views

Modulo $2$ binomial transform of A124758

Let $f(n)$ be A153733, remove all trailing ones in binary representation of $n$. Here \begin{align} f(2n)& = 2n\\ f(2n+1)& = f(n)\\ \end{align} Then we have an integer sequence given by \begin{...
user avatar
1 vote
0 answers
52 views

Inverse modulo $2$ binomial transform of generalised A284005

Let $m \geqslant 1$ be a fixed integer. Let $\operatorname{wt}(n)$ be A000120, $1$'s-counting sequence: number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Let $f(n)$ be A007814, ...
user avatar
0 votes
0 answers
95 views

Subsequence which is identical to A122778

Let $\operatorname{wt}(n)$ is A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Let $a(n)$ be A284005, \begin{align} a(0)& = 1\\ a(n)& = (1+\operatorname{wt}(n)...
user avatar
1 vote
0 answers
138 views

Open tours by a biased rook (proof verification)

Related questions: Number of open tours by a biased rook on a specific $f(n)\times 1$ board which end on a $k$-th cell from the right Sum with products turned into subsequences Combinatorial ...
user avatar
1 vote
0 answers
53 views

Subsequences related with square table

Let $m\geqslant1$ be a fixed integer. Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $...
user avatar
2 votes
0 answers
77 views

Subsequence of Laguerre polynomials

Let $m\geqslant1$ be a fixed integer. Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $...
user avatar
3 votes
1 answer
131 views

Sequences that sums up to second differences of Bell and Catalan numbers

Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Let $g(n)$ be A025480, $g(2n) = n$...
user avatar
3 votes
0 answers
92 views

Identical digits at the end of adjacent terms of the sequence

Let $m\geq 2$ be a fixed integer. Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. ...
user avatar
0 votes
0 answers
55 views

Alternative expression for $a(2n)$

Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Then we have an integer sequence ...
user avatar
2 votes
1 answer
143 views

Pair of recurrence relations with $a(2n+1)=a(2f(n))$

Let $f(n)$ be A053645, distance to largest power of $2$ less than or equal to $n$; write $n$ in binary, change the first digit to zero, and convert back to decimal. Let $g(n)$ be A007814, the ...
user avatar
-1 votes
1 answer
100 views

Linear recurrence period of GF(p) for prime P [closed]

Could you please help with the next questions? Let's we have finite field $GF(P)$ And linear recurrence of the next type: $a_{n+2} = s*a_{n+1} + t*a_{n}$ The question is: what are necessary and ...
user avatar
1 vote
1 answer
257 views

Formula from the recurrence relation

Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Then we have an integer sequence ...
user avatar
1 vote
1 answer
191 views

Subsequences of odd powers

Let $p$ and $q$ be integers. Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Then ...
user avatar
0 votes
1 answer
160 views

Generating function for partial sums of the sequence

Let $p$ and $q$ be integers. Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Then ...
user avatar
1 vote
2 answers
381 views

Recurrence for the sum

Let $m\geq 2$ be a fixed integer. Let $$f(n):=\begin{cases} mf\left(\frac{n}{m}\right),&\text{if $n\mod m = 0$;}\\ 1,&\text{otherwise} \end{cases}$$ then if we have $$a(n):=\begin{cases} 1,&...
user avatar
1 vote
0 answers
66 views

Recurrence for the viabin numbers of the self-conjugate integer partitions

Let $a(n)$ be A290254, the viabin numbers of the self-conjugate integer partitions, also defined as $\left\lbrace 0 \right\rbrace$ union fixed points of A059894, self-inverse permutation defined as ...
user avatar
3 votes
2 answers
340 views

Subsequence of the cubes

Let $p$ and $q$ be integers. Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Then ...
user avatar
2 votes
0 answers
84 views

A subsequence expressed in terms of a sum with a triangle

We have a sequence which generalize A329369: $$a(2n+1, p, q) = a(n, p,q), a(2n, p , q) = pa(n, p,q) + qa(n - 2^{f(n)}, p,q) + a(2n - 2^{f(n)}, p,q), a(0, p, q) = 1$$ where $f(n)$ is A007814, exponent ...
user avatar
3 votes
1 answer
286 views

Recursive formula for n-th prime derived from a previous question

Based on my previous answer and your help Is there a procedure for extracting first integer $q_0$ from $\sum\limits_{k=0}^{\infty}\frac{1}{q_k^z}$, all $0<q_0<q_1<...$ integers, $z$ complex? ...
user avatar
2 votes
0 answers
124 views

Generating Fuss-Catalan numbers using the regular Catalan number

Let $A_{n}(p,r)$ denote the $n$-th Fuss-Catalan number with parameter $(p,r)$. $A_{n}(p,r)$ has the closed form $A_{n}(p,r) = \frac{r}{np+r} {np+r \choose n}.$ For example, $A_{n}(2,1) = \frac{1}{n+1} ...
user avatar
  • 21
4 votes
0 answers
83 views

Asymptotics of holonomic recurrences and the Birkhoff-Trjitzinsky method

While reading about asymptotics of holonomic recurrences, I had the following impressions that are related to the divulgation of the theory: I don't know what is the current status of the divulgation ...
0 votes
0 answers
57 views

Reference request: Counting integer sequences in homogeneous linear recurrences

Are there references in the literature that deal with the probability of finding an integer sequence in a linear homogeneous recurrence with constant coefficients $ \in \mathbb{Z}$? (or provides a way ...
user avatar
3 votes
1 answer
137 views

About the sequence $s_n:=f_{n,n} $ where $f_{0,n}=f_{n,0}= n^n$ and $f_{m,n} = f_{m-1,n}+ f_{m,n-1} + f_{m-1,n-1}$

Let the sequence: $s_n:=f_{n,n} $ where $f_{0,n}=f_{n,0}= n^n$ and $f_{m,n} = f_{m-1,n}+ f_{m,n-1} + f_{m-1,n-1}$, for $mn>0$. Computationally it seems that $\frac{s_{n+1}}{s_{n}} \approx e\cdot ...
user avatar
3 votes
1 answer
236 views

A generating function related to the Delannoy numbers

What is the generating function of $f_{m,n}$? $ f_{m,n} = \begin{cases} 0 , & \text{if $m<0 $ or $ n<0$ }; \\ f_{n,m} , & \text{ if $n<m$}; \\ 1, & \text{ if $0=m$ and $ n\...
user avatar
0 votes
0 answers
105 views

Is the sequence $s_n:=f_{n,n} $ where $f_{0,n}=f_{n,0}= n!$ and $f_{m,n} = f_{m-1,n}+ f_{m,n-1} + f_{m-1,n-1}$ P-recursive?

Is the sequence $s_n:=f_{n,n} $ where $f_{0,n}=f_{n,0}= n!$ and $f_{m,n} = f_{m-1,n}+ f_{m,n-1} + f_{m-1,n-1}$ P-recursive? https://en.wikipedia.org/wiki/P-recursive_equation https://en.wikipedia.org/...
user avatar
0 votes
0 answers
142 views

Proof of the recurrence from general recurrence

We have general recurrence for A284005 $$a(n)=(1+b(n))a(\left\lfloor\frac{n}{2}\right\rfloor), a(0)=1$$ where $b(n)$ (A000120) is number of $1$'s in binary expansion of $n$ $$b(n)=b(\left\lfloor\frac{...
user avatar
0 votes
1 answer
190 views

What are the odds for a random collection of numbers to have sum less than a certain number?

Let's say we have $I$ collections of numbers, $N_i$ numbers in each. A collection may contain repeating numbers. We randomly take one number from each collection. What is the probability for a sum of ...
user avatar
2 votes
0 answers
181 views

What is the role of the Laplace transform in the topological recursion formalism?

While reading papers on topological recursion, among them The Laplace transform, mirror symmetry, and the topological recursion of Eynard–Orantin by M. Mulase, they describe the mirror symmetry ...
user avatar
0 votes
1 answer
132 views

How to probe the recursiveness order of a sequence $\{S_n\}$ whose generating function is known

How to probe the recursiveness order of a sequence $\{S_n\}$ whose generating function is known: $$ \sum_{n\geq0} S_n z^n= \frac{4 z \left(\sqrt{49 z^2-18 z+1}+7 z-1\right)}{\sqrt{49 z^2-18 z+1} \...
user avatar
0 votes
1 answer
157 views

Binary recurrence from general recurrence

We have general recurrence for A243499 (which is product of parts of integer partitions as enumerated in the table A125106) $$a(n)=(1+b(n))a(t(n)), a(0)=1$$ where $b(n)$ is A023416 (which is number of ...
user avatar
6 votes
1 answer
424 views

Maximum number of positive roots is $3$

Let $$f(x) = a+b(x+p)^t+c(x+p)^t(x+q)^t+d(x+p)^t(x+q)^t(x+r)^t,$$ where $t>1$ is any positive real number, $p>q>r>0$ or $p<q<r$ are positive integers and $a,b,c,d$ are any ...
user avatar
  • 213
1 vote
0 answers
170 views

Uniform lower bound for the distance between terms of a linear recurrence sequence

Let $(u_k)_{k=0}^\infty$ be a non-degenerate linear recurrence sequence of algebraic numbers. Denote by $\alpha_1,\dots,\alpha_m$ its characteristic roots, and suppose that $\alpha := \underset{i}{\...
user avatar
  • 11
0 votes
1 answer
111 views

Bounding the $n$-th term of a sequence, given a non-linear recursive bound

I asked the following question in MSE: Let $a,b\in\mathbb{R}^+$. Suppose that $\{x_n\}_{n=0}^\infty$ is a sequence satisfying $$|x_n|\leq a|x_{n-1}|+b|x_{n-1}|^2, $$ for all $n\in\mathbb{N}$. How can ...
user avatar
  • 517
5 votes
1 answer
314 views

Reference request: recurrence relation for Catalan numbers

I would like to know if the following recurrence relation for Catalan numbers (see mathoverflow.net/questions/191524 and also math.stackexchange.com/questions/2113830) has appeared in a paper or a ...
user avatar

1
2 3 4 5 6