# Questions tagged [recurrences]

The recurrences tag has no usage guidance.

252
questions

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,...

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$$
...

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\...

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})^...

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 [ \...

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 ...

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 = ...

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 ...

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:
...

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, ...

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 ...

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,...

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, ...

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| ...

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,...

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$.
...

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{...

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, ...

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)...

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 ...

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 $...

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 $...

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$...

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$.
...

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 ...

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 ...

-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 ...

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 ...

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 ...

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 ...

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,&...

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 ...

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 ...

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 ...

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?
...

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} ...

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 ...

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 ...

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\...

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/...

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{...

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 ...

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 ...

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} \...

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 ...

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 ...

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}{\...

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 ...

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 ...