We study divide-and-conquer recurrences of the form

\begin{equation*}
= \alpha f\lpa{\ltr{\tfrac n2}}
+ \beta f\lpa{\lcl{\tfrac n2}}
+ g(n) \qquad(n\ge2),
\end{equation*}

with $g(n)$ and $f(1)$ given, where $\alpha,\beta\ge0$ with
$\alpha+\beta>0$; such recurrences appear often in analysis of
computer algorithms, numeration systems, combinatorial sequences,
and related areas. We show that the solution satisfies always the
simple identity

\begin{equation*}
= n^{\log_2(\alpha+\beta)} P(\log_2n) - Q(n)
\end{equation*}

under an optimum (iff) condition on $g(n)$. This form is not only an
identity but also an asymptotic expansion because $Q(n)$ is of a
smaller order. Explicit forms for the continuity of the
periodic function $P$ are provided, together with a few other
smoothness properties. We show how our results can be easily applied
to many dozens of concrete examples collected from the literature,
and how they can be extended in various directions. Our method of
proof is surprisingly simple and elementary, but leads to the
strongest types of results for all examples to which our theory

§ INTRODUCTION

This paper is a sequel to [27], where we studied the
case $(\alpha,\beta)=(1,1)$ of the following recurrence

\begin{equation}\label{a1}
= \alpha f\lpa{\ltr{\tfrac{n}{2}}}
+ \beta f\lpa{\lcl{\tfrac{n}{2}}}
+ g(n) \qquad (n\ge 2),
\end{equation}

with $f(1)$ and $\{g(n)\}_{n\ge2}$ given; we focus here on the
general case of two given constants $\alpha,\beta > 0$. (The case
when $\alpha\le0$ or $\beta\le0$ is briefly discussed in Section
<ref>.) As in [27], our aim in this paper will be

* to establish optimum iff-conditions for the identity

\begin{equation}\label{a2}
= n^{\rho}P(\log_{2}n)-Q(n) \qquad(n\ge1),
\end{equation}

which is also an asymptotic expansion, where

\begin{align}\label{rho}
\rho
:= \log_2(\alpha+\beta),
\end{align}

$P$ is a bounded, continuous, periodic function and
$Q(n)$ is of a smaller order $o(n^{\rho})$; and

* to explore the usefulness of such a result by examining other
associated properties and applying to many concrete examples.

In addition, we also examine further smoothness properties of
the periodic function $P$, and introduce and explore a new notion to
describe the equivalence of different recurrences.

An elementary interpolation approach.
The crucial step of our approach is to identify a (generally
nonlinear) interpolation function $\varphi(x)$ such that the sequence
$f(n)$ as defined by (<ref>) for positive integers $n$ can be
extended to a continuous function $f(x)$ defined for all real
$x\ge1$ in the way that $f(x)$ equals the original sequence $f(n)$
when $x=n$, a positive integer, and there is a version of the
recurrence (<ref>) valid for all $x$; see
Section <ref> for details.

Such an interpolation-based analysis for (<ref>) will then be
extended (in S:qary) to the more general $q$-ary recurrence
($q\ge2$) of the form

\begin{equation}\label{E:qary}
= \sum_{0\le j<q}\alpha_{j}f\lpa{\ltr{\tfrac{n+j}q}}
+g(n) \qquad (n\ge q),
\end{equation}

for some given constants $\alpha_0,\dots,\alpha_{q-1}$, and a result
of the form (<ref>) will also be derived under some conditions.
Typical situations where (<ref>) arises is the application of
divide-and-conquer into $q$ parts whose sizes are as evenly as
possible. The special case when $\alpha_j=1$ for $0\le j<q$ was
already discussed in [27]. Another special case is
$\ga_j=0$ for $1\le j\le q-2$, which yields (with $\ga=\ga_0$ and
$\gb=\ga_{q-1}$) the recursion $f(n) = \alpha f(\tr{\frac nq})+\beta
f(\cl{\frac nq})+g(n)$ considered in <cit.>
and [33] although they allow also non-integer $q>1$.

Recurrences with or without floors and ceilings.
While the divide-and-conquer paradigm with evenly divided parts is
widely used in computer algorithms, our formulation of the
divide-and-conquer recurrence (<ref>), as well as the very
precise identity (<ref>), is surprisingly rare in the computer
algorithm literature; instead one finds predominantly a recurrence of
the form

\begin{align}\label{E:srr}
= (\alpha+\beta) f\lpa{\tfrac n2}+g(n),
\end{align}

or more generally

\begin{align}\label{E:srr2}
= \sum_{0\le j<d}\alpha_j f\lpa{\tfrac n{q_j}}
+ g(n),
\end{align}

where $\alpha, \alpha_j>0$, $d=1,2,\dots$ and $q_j>1$. According to
the first edition of Cormen et al.'s widely used textbook on
Algorithms <cit.>: “When we state and solve
recurrences, we often omit floors, ceilings, and boundary conditions.
We forge ahead without these details and later determine whether or
not they matter. …we shall address some of these details to show
the fine points of recurrence solution methods."

Such a simplifying approach also appears in most publications on
Algorithms. One of our aims in this paper is to show that
retaining floors and ceilings is not much more complicated than
omitting them, and with various advantages that are mostly unnoticed
in the literature. This suggests that one main reason of omitting
floors and ceilings in handling a divide-and-conquer recurrence lies
more in methodological deficiencies than simply technical
conventions; the approach proposed in this paper will then complete
to some extent the required methodological developments.

More precisely, when $\alpha,\beta, g(n)\ge0$, typical approaches
adopted in the computer algorithms community to solving the
recurrence (<ref>) include

* dropping floor and ceiling in (<ref>) by assuming $n$ to be
a power of $2$, resulting in the closed-form expression

\begin{align}\label{E:2^m}
= \sum_{1\le j\le m}(\alpha+\beta)^{m-j}g(2^j)
+ (\alpha+\beta)^m f(1),
\end{align}

* lower- and upper-bounding $f$ by keeping only floor and only
ceiling function in (<ref>), leading to

\begin{align}\label{E:fmn}
f_-(n) := (\alpha+\beta)f_-\lpa{\tr{\tfrac n2}} + g(n),
\end{align}

\begin{align}\label{E:fpn}
f_+(n) := (\alpha+\beta)f_+\lpa{\cl{\tfrac n2}} + g(n),
\end{align}

While simple and effective in estimating the growth order of $f(n)$
for large $n$, both approaches suffer from subtle oversights and
intrinsic limitations, with different shortcomings.

First, in either of the approaches (<ref>) and
(<ref>)–(<ref>), the next crucial property used in
estimating the asymptotic growth of $f(n)$ is monotonicity,
which in the first approach is of the form $f(2^m)\le f(2^m+\ell)\le
f(2^{m+1})$ for $0\le \ell \le 2^m$, and $f_-(n)\le f(n)\le f_+(n)$
in the second approach. However, these inequalities may not hold in
general due to the periodic nature of the recurrences (<ref>),
(<ref>) and (<ref>). For example, take $\alpha=\beta=1$
and $g(n) = 1+\mathbf{1}_{n \text{ odd}}$ with $f(1)=f_+(1) = 0$.
Then $8=f(7)>f(8)=7$, and $f(15)=17>f_+(15)=16$. Thus the use of the
monotonicity is more subtle than it is generally taken to be.

On the other hand, when $g(n) = \mathbf{1}_{n \text{ odd}}$ with
$f(1)=0$ (which yields A296062 in the On-Line Encyclopedia of
Integer Sequences database [34] with many combinatorial
interpretations), then $f(n)$ oscillates between $0$ and $\Theta(n)$.
Thus not only monotonicity fails but also the growth order oscillates
violently, although our result yields that $f(n) = nP(\log_2n)$ for
some continuous periodic function; see (<ref>).

Apart from monotonicity, there is yet another deeper reason why the
original sequence (<ref>) is preferred to its simplified one-sided
versions (<ref>) and (<ref>): the periodic function $P$
in (<ref>) is always continuous, while the corresponding
one for the solution of either (<ref>) or (<ref>) is
almost always discontinuous; more precisely, in typical cases
the function $P(t)$ is discontinuous at every $t$ such that $2^t$ is
a dyadic rational, i.e., has a finite binary representation (see
Salphabeta=0 and, for details in the case $\ga+\gb=2$,
<cit.>). But why does continuity matters here?
The reason is because the periodic function $P$ when evaluated at
$\log_2n$ (see (<ref>)), involves indeed functions evaluated at
the dyadic rational $n/2^{\tr{\log_2n}}$ (see (<ref>) and
(<ref>)), so that discontinuity causes the sequence (or the
original cost function) to have more violent jumps even for
neighbouring input sizes. Thus simplifying the recurrence (<ref>)
to either (<ref>) or (<ref>) has the advantage of being
easily solvable by iteration, but suffers from structural
discontinuities, or more rough oscillations.

Master theorems.
Another commonly used approach to solve (<ref>) is to apply the
so-called “master theorems" (see [2, 11]),
which are generally effective and user-friendly, but does not provide
more precise asymptotic approximations. For example, in the case of
(<ref>), if $g(n) = O(n^{\rho-\ve})$, $\ve>0$, then the master
theorem <cit.> or [33] gives $f(n)
= \Theta(n^\rho)$, where $\rho$ is defined in (<ref>), while
under the same growth order of $g$, our approach (see
Corollary <ref>) again guarantees (<ref>) with explicitly
computable functions $P$ and $Q$. There do exist finer master
theorems that give more precise asymptotics under stronger
assumptions on $g(n)$ (such as monotonicity; see [13]),
but none of them is as precise as our identity (<ref>).

Discrete and continuous master theorems.
An additional feature of our interpolation-based analysis is that we
always work on the same real function $f(x)$, which coincides with
the original sequence $f(n)$ at integer parameters, unlike general
master theorems that distinguish between “discrete master theorems”
and “continuous master theorems”; for example, according to

To distinguish the two situations, we call the master theorem
without floors and ceilings the continuous master theorem and the
master theorem with floors and ceilings the discrete master theorem.

The subtleties of the two different versions (together with other
issues) are only very recently thoroughly examined in
[33], where they write:

Several academic works provide proofs and proof sketches of the
discrete master theorem. To the best of our knowledge, however, all
of these proofs are either incomplete, incorrect, or require
sophisticated mathematics.

See also the long paper (more than 300 pages) [4] for
other delicate issues arising from divide-and-conquer recurrences.
Additionally, the chapter on “Recurrences” (Chapter I.4) in the
first edition of Cormen et al.'s book [10] is now
largely expanded and updated in the latest, very recent, edition
<cit.>, more than three decades after its first
edition and following the corresponding developments in clarifying
the subtleties; see [4, 11].

For more information and references on master theorems and
divide-and-conquer recurrences, see, for example, [13, 23, 26, 33, 35]. See also
[27] for more references on other approaches (including
complex-analytic, Tauberian, renewal, fractal geometry, and Ansatz or
guess-and-prove, called the substitution method in [11])
used in the literature for solving (<ref>).

Periodic equivalence of sequences.
For a more canonical way to group or classify the diverse periodic
functions $P$, we will introduce in Section <ref> a useful
notion called “periodic equivalence”, roughly meaning that
different sequences share, modulo amplitude and scale, the same
oscillating part. For example, denote by $S_{2,1}(n)$ (A006046) the
total number of odd entries in the first $n$ rows of Pascal triangle;
then $f(n) = S_{2,1}(n)$ satisfies (<ref>) with
$(\alpha,\beta)=(2,1)$, $g(n)=0$ and $f(1)=1$. We have $S_{2,1}(n)=
n^{\log_23}P(\log_2n)$; see Ex:pascal. Then the following
OEIS sequences, all satisfying (<ref>) with
$(\alpha,\beta)=(2,1)$, are periodically equivalent to $S_{2,1}(n)$
(involving, up to scale and amplitude, the same $P$):

OEIS id.     $g(n)$     $f(1)$     $f(n)$
A051679     $\frac18n^2 - \begin{cases}
\frac n4,& \text{$n$ even}\\
\frac18,& \text{$n$ odd}
\end{cases}$     $0$

A080978     $-2$     $3$     $2S_{2,1}(n)+1$

A159912     $\tr{\frac n2}$     $1$     $2S_{2,1}(n)-n$

A171378     $\cl{\frac n2}^2-\mathbf{1}_{n \text{ odd}}$
$0$     $n^2-S_{2,1}(n)$

A267700     $\tr{\frac n2}$     $0$     $S_{2,1}(n)-n$

See Ex:pascal for more periodically equivalent sequences.

Smoothness of the periodic function.
While the periodic equivalence is introduced to identify the same
fluctuating part of different sequences satisfying the same
recurrence, we also examine the varying smoothness nature exhibited
by different recurrences. The main motivating observation is
that most periodic functions we obtain have visible cusps (likely to
be non-differentiable points), and there are other classes of
functions (such as Lipshitz and Hölder continuous) between the
class of continuous functions and that of continuously differentiable
functions. We will thus clarify the different, characteristic,
inherent types of Hölder continuity of the interpolated function
$f(x)$ and the periodic function $P(t)$ when $(\alpha,\beta)$ varies.

For example, in Figure <ref>, we plot the periodic functions
$P$ (as defined in (<ref>)) when $f$ satisfies (<ref>) with
$g(n)=0$ and $f(1)=1$, and with $(\alpha,\beta)=(\alpha,1)$,
$\alpha=2,3,4,5$ (the lower blue curves) and
$(\alpha,\beta)=(1,\beta)$, $\beta=2,3,4,5$ (the upper green curves).
Our results show that these periodic functions are Hölder
continuous with exponent $\log_2(1+\alpha^{-1})$ and
$\log_2(1+\beta^{-1})$, respectively, and we conjecture that these
exponents are the best possible; see Section <ref> for
details. Thus for these recurrences, the larger the values of
$\alpha$ or $\beta$, the “less smooth" the periodic functions.

Periodic fluctuations of the functions $P(\log_2n)
=f(n)n^{-\log_2(\alpha+\gb)}$ for $n=2,\dots,1024$ when $f$
satisfies (<ref>) with $g(n)=0$, $f(1)=1$ and with (the blue
curves) $\beta=1$ and $\alpha=2,3,4,5$ (from top to bottom),
and (the green curves) $\alpha=1$ and $\beta=2,3,4,5$ (from
bottom to top).

Moreover, we show that many of the periodic functions appearing in
our analysis are indeed not continuously differentiable at all points
in $(0,1)$. Several examples are piecewise differentiable with jumps
in the derivative at some points (see, for example, Ra=b and
E52 and <ref>). Other examples are less smooth; for
brevity of presentation, we discuss only one case (A006581) in detail
in E22-ns and show (in Appendix <ref>) that the
periodic function is continuous but nowhere differentiable, leaving
such a deeper property for other sequences to the interested reader.

A generating function viewpoint.
To see how the general cases differ from the special case
$(\alpha,\beta)=(1,1)$ or more generally $\alpha=\beta$, we consider
the generating function

\begin{equation}\label{gg1}
:= \sum_{n\ge1} f(n) z^n,
\end{equation}

which, by (<ref>) satisfies the functional equation

\begin{equation}\label{gg2}
= \frac{\beta+(\alpha+\beta)z+\alpha z^2}{z}\, A(z^2)
+ B(z),
\end{equation}

\begin{equation}\label{gg3}
:= f(1)(1-\beta)z+\sum_{n\ge2}g(n)z^n.
\end{equation}

We see that if $\alpha=\beta$, then the functional equation becomes

\begin{equation}\label{gg4}
= \frac{\alpha(1+z)^2}z\,A(z^2)+B(z),
\end{equation}

so that the generating function $\bar{A}(z) := \frac{(1-z)^2}z\,A(z)$
of the second difference of $f(n)$ satisfies the simpler equation

\begin{equation}\label{gg5}
\bar{A}(z)
= \alpha \bar{A}(z^2)+\bar{B}(z),
\end{equation}

where $\bar{B}(z) := \frac{(1-z)^2}z\,B(z)$. Assuming for simplicity
(without real loss of generality) that $\bar{B}(0)=0$, we then
obtain, by iteration, the exact solution

\begin{equation}\label{gg6}
= \frac{z}{(1-z)^2}\sum_{k\ge0}
\alpha^{k}\bar{B}\lpa{z^{2^k}}.
\end{equation}

Such a neat representation is the basis of the analytic approach
introduced in [20], but is not available in general
when $\alpha\ne\beta$. We will therefore use a different method.

This paper is structured as follows. We develop in
Section <ref> the required technicalities in order to
prove (<ref>), and then address the smoothness properties of $P$
in Section <ref>. These two sections provide a theoretical
foundation to the resolution of the divide-and-conquer recurrences of
the form (<ref>). Applications of our theory to concrete examples
are discussed in Section <ref> for $\alpha\ne\beta$ and in
Section <ref> for $\alpha=\beta$. We then extend very briefly
our analysis to nonpositive $\alpha$ or $\beta$ in
Section <ref> and to general $q$-ary recurrence
(<ref>) in Section <ref>. For completeness, an appendix
on the connection of our approach to Mellin transforms is given,
together with two others providing detailed proofs of some results in
the paper.

For convenience, we introduce the operator $\Lambda_{\alpha, \beta}$
as follows:

\begin{equation}
\Lambda_{\alpha ,\beta}[f](n)
:= f(n)-\alpha f\left( \left\lfloor \tfrac{n}{2}
\right\rfloor \right) -\beta f\left( \left\lceil
\tfrac{n}{2}\right\rceil\right) .
\end{equation}

Let, for $x>0$,

\begin{align}\label{L,theta}
&:=\left\lfloor \log_{2}x\right\rfloor,
\end{align}

and $L_0 := 0$.

For real $x$ and $y$, we let $x\vee y:=\max(x,y)$.

§ THE RECURRENCE $\LAMBDA_{\ALPHA ,\BETA}[F]=G$

Here and throughout this section, we assume that
$\alpha,\beta>0$, and define $g(1):=0$.
The recurrence (<ref>) can be rewritten as

\begin{equation}\label{b1}
\begin{split}
&=(\alpha +\beta )f(n)+g(2n),   \\
&=\alpha f(n)+\beta f(n+1)+g(2n+1),
\end{split}
\end{equation}

for $n\ge 1$, with given $f(1)$ and $g(n)$, $n\ge 2$.

Extending the sequence $f(n)$ to a function $f(x)$ in
We extend the sequence $f(n)$ to a continuous function $f(x)$
defined for real $x\ge1$ by interpolation between the integers with
scaled copies of a certain function $\varphi:\oi\to\oi$ constructed

\begin{align}\label{b2}
%	\begin{split}
&:= f(n)+\varphi(t)\left( f(n+1)-f(n)\right) \notag\\
&= \left( 1-\varphi(t)\right) f\left( n\right)
+ \varphi(t)f\left( n+1\right) ,
%	\end{split}
\end{align}

for $n\ge 1$ and $0\le t\le 1$; in a similar way, we construct
$g(x)$ from $g(n)$. The function $\varphi$ is constructed so that
we will have

\begin{equation}\label{b3}
= (\alpha +\beta )f\left( \frac{x}{2}\right)
+ g(x), \qquad x\ge2.
\end{equation}

We further define $g(x):=0$ for $x\in[0,1)$; thus $g(x)$ is defined
for $x\ge0$.

The function $\varphi(t)$ depends on $\alpha$ and $\beta$;
we sometimes write it as $\varphi_{\alpha,\beta}(t)$ to emphasise the
dependence on parameters.

Construction of the interpolation function $\varphi $.
We first give relations on $\varphi $ that imply  the functional
equation (<ref>). The existence of such a $\gf$ is shown later.

Let $\varphi(t)=\varphi_{\alpha,\beta}(t)$ be a function on $[0,1]$
such that $\varphi(0)=0$, $\varphi(1)=1$ and

\begin{equation}\label{b4}
\varphi(t)
= \begin{cases}
\tfrac{\beta}{\alpha +\beta}\,\varphi(2t),
& \text{if\/ }t\in [0,\frac{1}{2}], \\
\tfrac{\alpha}{\alpha +\beta}\,\varphi(2t-1)
+\tfrac{\beta}{\alpha +\beta},
& \text{if\/ }t\in [\frac{1}{2},1].
\end{cases}
\end{equation}

Assume that (<ref>) holds. Then (<ref>) holds if we extend
$f(n)$ and $g(n)$ by (<ref>) to $f(x)$ and $g(x)$, respectively,
for all real $x\ge 1$.

If $n\ge 1$ and $0\le t\le \frac{1}{2}$, then, using the interpolation
(<ref>), the recurrences (<ref>) and the assumption (<ref>),
we have

\begin{align}\nonumber
\MoveEqLeft f(2n+2t) -g(2n+2t)  \\
&= (1-\varphi(2t))(f(2n) -g(2n))
+\varphi(2t)(f(2n+1) -g(2n+1))
\nonumber \\
&= (1-\varphi(2t)) (\alpha+\beta) f(n)
+\varphi(2t)\bigpar{\alpha f(n) +\beta f(n+1) }
\nonumber \\
&= (\alpha+\beta) f(n) -\varphi(2t)\beta f(n)
+\varphi(2t)\beta f(n+1)  \nonumber \\
&= (\alpha+\beta) f(n) -(\alpha +\beta) \varphi(t)f(n)
+(\alpha+\beta) \varphi(t)f(n+1)  \nonumber \\
&= (\alpha+\beta) \bigpar{(1-\varphi(t)) f(n)
+\varphi(t)f(n+1)}  \nonumber \\
&= (\alpha+\beta) f(n+t) . \label{b5}
\end{align}

Similarly, the lower part of (<ref>) can be rewritten as

\begin{align}\label{b4l}
\xpar{\alpha +\beta}\,\varphi\left(\tfrac{1}{2}+t\right)
= \alpha\varphi(2t)+\beta,\qquad t\in[0,\tfrac{1}{2}],
\end{align}

and thus, still for $n\ge 1$ and $0\le t\le \frac{1}{2}$,

\begin{align}\nonumber
\MoveEqLeft f(2n+1+2t)-g(2n+1+2t)  \\
&= (1-\varphi(2t))(f(2n+1) -g(2n+1))
+\varphi(2t)(f(2n+2) -g(2n+2))  \nonumber \\
&= (1-\varphi(2t))(\alpha f(n) +\beta f(n+1))
+\varphi(2t)(\alpha+\beta) f(n+1)  \nonumber \\
&= \alpha f(n) +\beta f(n+1) -\varphi(2t)\alpha f(n)
+\varphi(2t)\alpha f(n+1)  \nonumber \\
&= \alpha f(n) +\beta f(n+1) -\left((\alpha+\beta)
\varphi\left(\tfrac{1}{2}+t\right) -\beta \right)
\bigpar{f(n)-f(n+1)}\nonumber \\
&= (\alpha+\beta) f(n) -(\alpha +\beta)
\varphi\left(\tfrac{1}{2}+t\right) f(n)
+(\alpha+\beta) \varphi\left(\tfrac{1}{2}+t\right) f(n+1)
\nonumber \\
&= (\alpha+\beta)
\left(\left(1-\varphi\left(\tfrac{1}{2}+t\right)
\right) f(n)
+\varphi\left(\tfrac{1}{2}+t\right)f(n+1) \right)
\nonumber \\
&= (\alpha+\beta) f\left(n+\tfrac{1}{2}+t \right).
\label{b6}
\end{align}

Combining (<ref>) and (<ref>), we obtain

\begin{equation}\label{b7}
= (\alpha +\beta )f\left(\tfrac{n}{2}+t\right) +g(n+2t)
\end{equation}

for $n\ge 2$ and $0\le t\le \frac{1}{2}$, and thus (<ref>) holds.

Conversely, it is immediate that if (<ref>) holds for the
extensions of $f$ and $g$ defined by (<ref>), then (<ref>)

In the case $\ga=\gb=1$ treated in [27], the system of
equations (<ref>) has the solution $\gf(t)=t$. In general, it is
not obvious that a continuous solution to (<ref>) exists. We now
show that this is the case, and that this $\varphi $ is unique.

If $\alpha ,\beta >0$, then there exists a unique continuous
function $\varphi(t)=\gf_{\ga,\gb}(t)$ on $[0,1]$ such that
$\varphi(0)=0$, $\varphi(1)=1$ and (<ref>) holds. Moreover,
$\varphi $ is strictly increasing.

The equation (<ref>) and the conditions $\varphi(0)=0$, $\varphi
(1)=1$ define recursively $\varphi(t)$ uniquely for dyadic rational
$t\in [0,1]$; hence, there is at most one continuous $\varphi $
satisfying these requirements. The existence of such a $\varphi$ can
be proved in several different ways.

First proof (probabilistic).
Let $\gf$ be the distribution function $\gf(t):=\Pr(X\le t)$ of the
random variable $X\in\oi$ defined by the binary expansion
$X=0.B_1B_2\dots$, where the bits $B_1,B_2,\dots$ are independent and
with $\Pr(B_i=1)=\frac{\ga}{\ga+\gb}$. Since the random variable
$X':=0.B_2B_3\dots=2X-B_1$ has the same distribution as $X$, we see

\begin{equation}
\begin{split}
\gf(t)
&:= \Pr(X\le t)\\
\Pr(B_1=0)\Pr(X'\le 2t),
% =\frac{\gb}{\ga+\gb}\,\gf(2t),
& t\in[0,\frac12],
\\
\Pr(B_1=0)+\Pr(B_1=1)\Pr(X'\le 2t-1),
% =\frac{\gb}{\ga+\gb}+\frac{\ga}{\ga+\gb}\,\gf(2t-1),
& t\in[\frac12,1],
\end{cases}\\
&= \begin{cases}
\frac{\gb}{\ga+\gb}\,\gf(2t) ,
& t\in[0,\frac12], \\
\frac{\gb}{\ga+\gb}+\frac{\ga}{\ga+\gb}\,\gf(2t-1),
& t\in[\frac12,1],
\end{cases}
\end{split}
\end{equation}

which verifies (<ref>). Furthermore, $\gf$ is continuous and
strictly increasing on $\oi$, with $\gf(0)=0$ and $\gf(1)=1$.

Second proof (digital sums).
An alternative approach begins with an explicit construction, which
will also be useful later. For $t=\sum_{j\ge 1}b_{j}2^{-j}\in
[0,1]$, where $b_{j}\in \{0,1\}$, define

\begin{align}\label{b8a}
\varphi(t)
:= \sum_{j\ge 1}b_{j}
\left(\frac{\alpha}{\beta}\right)^{b_{1}+\cdots +b_{j-1}}
\biggpar{\frac{\beta}{\alpha +\beta}}^{j}.
\end{align}

Equivalently, define, for $t=\sum_{k\ge 1}2^{-e_{k}} \in\oi$, where
$1\le e_{1}<e_{2}<\cdots $ is a finite or infinite sequence,

\begin{equation}\label{b8}
\varphi \biggpar{t=\sum_{k\ge 1}2^{-e_{k}}}
:= \sum_{k\ge 1}
\frac{\alpha^{k-1}\beta^{e_{k}-k+1}}
{\left( \alpha +\beta \right)^{e_{k}}}.
\end{equation}

We first show that both (<ref>) and (<ref>) are well defined
for dyadic rational $t$ with two different representations, namely,

\begin{align}\label{mag}
\sum_{1\le i\le k}2^{-e_{i}}
= \sum_{1\le j<k}2^{-e_{j}}
+ \sum_{j\ge 1}2^{-( e_{k}+j) }.
\end{align}

The value in (<ref>) for the last term on the left-hand side of
(<ref>) is $\frac{\alpha^{k-1}\beta^{e_{k}-k+1}}{\left(\alpha
+\beta \right)^{e_{k}}}$; the value for the sum on the right-hand
side equals

\begin{equation}
\sum_{j\ge 1}
\frac{\alpha^{(k+j-1)-1}\beta^{e_{k}+j-( k+j-1)+1}}
{(\alpha +\beta)^{e_{k}+j}}
\sum_{j\ge 1}\frac{\alpha^{j-1}\beta}
\end{equation}

since the final geometric series sums to 1. Hence, the two
representations in (<ref>) yield the same sum (<ref>), which
always equals the sum (<ref>), and thus $\gf$ is well-defined
on $[0,1]$.

Clearly, $\gf(0)=0$ and $\gf(1)=1$, again by summing the same
geometric sum. Moreover, (<ref>) follows easily from (<ref>),
considering the cases $b_1=0$ and $b_1=1$ separately.

Next, if $t=\sum_{1\le j\le N} b_j 2^{-j}$ is a dyadic rational in
$[0,1)$, and $s:=\sum_{1\le j\le N} b_j$, then, by (<ref>) and
induction on $N\ge0$, we have

\begin{align}\label{bb10}
\gf\bigpar{t+2^{-N}}-\gf(t)
\end{align}

It follows from (<ref>) that $\gf$ is strictly increasing on the
set of dyadic rationals in $\oi$. Furthermore, suppose that
$t_1=j2^{-N}$ is a dyadic rational in $[0,1)$, and let
$t_2:=t+2^{-N}$. If $t\in[t_1,t_2]$, then both $t$ and $t_2$ have
binary expansions beginning with the expansion of $t_1$ (choosing the
infinite representation for $t_2$), and it follows from (<ref>)
that $\gf(t_1)\le \gf(t)\le\gf(t_2)$. Now, suppose $0\le t<u\le 1$,
and choose $N$ such that $2^{1-N}<u-t$. Then there exist $j$ and $k$
with $j2^{-N} \le t\le (j+1)2^{-N}<k2^{-N}\le u\le(k+1)2^{-N}$.
Hence, by what was just shown, $\gf(t)\le \gf
\bigpar{(j+1)2^{-N}}<\gf\bigpar{k2^{-N}}\le\gf(u)$. Thus, $\gf$ is
strictly increasing.

The monotonicity implies that any discontinuity of $\gf$ must be a
jump. Define

\begin{align}
\gD_+\gf(t)
:= \lim_{u\searrow t}\gf(u)-\gf(t), \qquad t\in[0,1),
\end{align}

the jump to the right at $t$, and let $R:=\sup_{t\in[0,1)}\gD_+(t)$.
It follows from (<ref>) that $R=\frac{{\ga\lor\gb}}{\ga+\gb} R$,
and thus $R=0$. Hence, $\gf$ is right-continuous. Similarly, $\gf$
is left-continuous.

The function $\varphi$ for $(\alpha,\beta)=(2,1),
(1,2), (3,1), (1,3)$ (from left to right).

Third proof (recursive construction).
Yet another alternative, similar to the construction of Koch's
snowflake curve [41], is to define
$\varphi^{}_{0}(t):=t, t\in [0,1]$, and then recursively let
$\varphi^{}_{k+1}$ consist of two suitably scaled copies of
$\varphi^{}_{k}$; more precisely

\begin{equation}\label{b9}
\varphi^{}_{k+1}(t)
:= \begin{cases}
\tfrac{\beta}{\alpha +\beta}\,\varphi^{}_{k}(2t),
& \text{if }t\in [0,\frac{1}{2}], \\
\tfrac{\alpha}{\alpha +\beta}\,\varphi^{}_{k}(2t-1)
& \text{if }t\in [\frac{1}{2},1];
\end{cases}
\end{equation}

see Figure <ref> for an illustration. Then, by induction,
$|\gf_{k+1}(t)-\gf_k(t)|\le \bigpar{\frac{{\ga\lor\gb}}{\ga+\gb}}^k$
for $k\ge0$ and $t\in[0,1]$; consequently, the functions
$\varphi^{}_{k}(t)$ converge uniformly on $\oi$ to a continuous
function $\gf$ satisfying (<ref>), with $\gf(0)=0$ and
$\gf(1)=1$. It follows also that $\gf$ is weakly increasing; it is
then easy to show, using (<ref>), that such $\gf$ is strictly
increasing, but we omit this, since we have already shown this using
the other constructions.

If $\ga=\gb$, then (<ref>) is solved by $\gf(t)=t$, just as in
the case $\ga=\gb=1$ treated in [27], so $f(x)$ is
defined in (<ref>) by linear interpolation. If $\ga\neq\gb$,
then this is not the case; a linear interpolation would not yield

Figure <ref> shows that $\gf$ has a typical fractal shape when
$\ga\neq\gb$. We will show in Lemma <ref> and RHolder
below that $\gf$ is  continuous but not Lipschitz continuous
when $\ga\neq\gb$.

The functions $\varphi^{}_k$ for
$k=0,\dots,15$, where $(\alpha,\beta)=(2,1), (1,2)$ (left),
$(\alpha,\beta)=(3,1), (1,3)$ (middle-left), $(\alpha,\beta)=(3,2),
(2,3)$ (middle-right), and $(\alpha,\beta)=(10,1), (1,10)$

It follows from (<ref>) that

\begin{align}
\varphi_{\beta,\alpha}(t)
= 1-\varphi_{\alpha,\beta}(1-t),
\end{align}

so the graph of $\varphi_{\beta,\alpha}$ equals the graph of
$\varphi_{\alpha,\beta}$ rotated about $(\frac12,\frac12)$. See
Figures <ref> and <ref> for a graphical illustration of
some examples.

For later use we note that

\begin{align}\label{rintegral}
\int_0^1\gf(x)\dd x
\end{align}

To see this, we may denote the integral by $I$ and integrate both
sides of (<ref>), which then yields

\begin{align}
= \frac{\gb}{\ga+\gb}\cdot\frac12I+
\frac{\ga}{\ga+\gb}\cdot\frac12I
+ \frac{\gb}{\ga+\gb}\cdot\frac12
= \frac12I + \frac12 \frac{\gb}{\ga+\gb};
\end{align}

solving $I$ gives (<ref>).

By iterating the functional equation (<ref>), we obtain, for

\begin{equation}\label{b10}
=\sum_{0\le k<m}(\alpha +\beta )^{k}g(2^{-k}x)
+(\alpha+\beta)^{m}f(2^{-m}x) ,
\qquad 0\le m\le L_x.
\end{equation}

This leads to the following identity.

Assume that $f$ satisfies (<ref>) and (<ref>). Then,
for $x\ge 1$,

\begin{equation}\label{b15}
x^{-\rho }f(x)
=\sum_{k\ge 0}(2^{-k}x)^{-\rho}g(2^{-k}x)
+f(1)P_0\left( \log_{2}x\right) ,
\end{equation}

where $\rho:=\log_2(\ga+\gb)$ and

\begin{equation}\label{b16}
P_0\left( t\right)
:= \left( 1+( \alpha +\beta-1)
\varphi\lpa{2^{\{t\}}-1}\right)
(\alpha +\beta)^{-\{t\}}
\end{equation}

is a continuous $1$-periodic function satisfying $P_0(0)=P_0(1)=1$.

Since $g(x)=0$ for $x\le1$, the sum in (<ref>) is indeed finite.

First, (<ref>) yields $P_0(0)=1$ and $\lim_{t\nearrow 1}P_0(t)
=\bigpar{1+(\ga+\gb-1)\gf(1)}(\ga+\gb)\qw =(\ga+\gb)(\ga+\gb)\qw
=1=P_0(1)$. Furthermore, $P_0$ is continuous on $[0,1)$ since $\gf$
is continuous, and $P_0$ is $1$-periodic. It follows that $P_0$ is
continuous on $\mathbb R$.

By (<ref>), $f(2)=\left(\alpha +\beta \right) f(1)+g(2)$. Thus,
for $1\le x< 2$, recalling $g(1)=0$,

\begin{align}\label{b16a}
&= f(1)+\varphi(x-1)(f(2)-f(1))  \notag\\
&= f(1)+\varphi(x-1) \bigpar{(\alpha+\beta-1)f(1)+g(2)}\notag\\
&= f(1)\bigpar{1+(\ga+\gb-1)\gf\xpar{x-1}}+g(x)\notag\\
&= f(1)P_0\bigpar{\log_2x}(\ga+\gb)^{\log_2x}+g(x).
\end{align}

Now consider $x\ge1$. Take $m=L_{x}$ in (<ref>) and use
(<ref>) with $x$ replaced by $2^{-L_x}x=2^{\gth_x}\in[1,2)$;
we then obtain, by the relation $\ga+\gb=2^\rho$,

\begin{align}\label{b17}
&=\sum_{0\le k<L_{x}}(\alpha +\beta)^{k}g(2^{-k}x)
+(\alpha+\beta )^{L_{x}}f(2^{-L_{x}}x) \notag\\
&=\sum_{0\le k\le L_{x}}(\alpha +\beta )^{k}g(2^{-k}x)
+(\alpha+\beta )^{L_{x}+\gth_x}f(1)P_0\bigpar{\gth_x}\notag \\
&=\sum_{ k\ge0}2^{\rho k}g(2^{-k}x)
\end{align}

This implies (<ref>).

If $\ga=\gb$, then $\gf(t)=t$ by Rlinear, and thus (<ref>)

\begin{equation}\label{b16=}
P_0\left( t\right)
:= \bigpar{ 1+( \alpha +\beta-1)
\lpa{2^{\{t\}}-1}}
(\alpha +\beta)^{-\{t\}} .
\end{equation}

In the case $\ga=\gb=1$ studied in [27], and also in the
case $\ga=\gb=\frac12$, this yields $P_0(t)\equiv1$. In all other
cases with $\ga=\gb>0$, the periodic function $P_0(t)$ is infinitely
differentiable in $(0,1)$, but a simple calculation shows that the
derivative has a jump at the integers; hence, $P_0$ is Lipschitz but
not continuously differentiable.

If $\gb=1$, then (<ref>) and (<ref>) yield also

\begin{align}\label{b161}
P_0\left( t\right)
= (\alpha +1)^{1-\{t\}}\varphi\lpa{2^{\{t\}-1}}.
\end{align}

We can now give an extension of Theorem 2 in our previous paper

Suppose that $f$ and $g$ are given by (<ref>) and (<ref>).
The following are equivalent.

$n^{-\rho }f(n)=P(\log_{2}n)+o(1)$ as $n\to \infty $, for some
continuous $1$-periodic function $P$ on $\mathbb{R}$.

$x^{-\rho }f(x)=P(\log_{2}x)+o(1)$ as $x\to \infty $, for some
continuous $1$-periodic function $P$ on $\mathbb{R}$.

\begin{align}\label{t1b}
x^{-\rho }f(x)
=P(\log_{2}x)+o(1) \qquad \text{as $x\to \infty $},
\end{align}

for some $1$-periodic function $P$ on $\mathbb{R}$.

The sum

\begin{align}\label{t1Q}
Q(x):=\sum_{m\ge 1}2^{-\rho m}g(2^{m}x)
\end{align}

converges uniformly
for $x\in [1,2]$.

Furthermore, when these conditions hold,

\begin{equation}\label{t1z}
=x^{\rho }P(\log_{2}x)-Q(x), \qquad x\ge1,
\end{equation}

where $Q(x)=o(x^\rho)$ as $x\to\infty$, $Q(x)$ is defined by
(<ref>) for all $x>0$, and the continuous periodic function
$P(t)$ is given by

\begin{equation}\label{t1y}
=\sum_{m\in \mathbb{Z}}2^{-\rho (m+t)}g(2^{m+t})
+f(1)P_0(t), \qquad t\in\mathbb{R},
\end{equation}

with $P_0(t)$ given by (<ref>).

Note that (<ref>) is not only an identity but also an
asymptotic expansion.

Before proving Theorem1, we give two partial results.

Suppose that $h(x)$ is a function such that $h(x)$ lies between
$h\left( \left\lfloor x\right\rfloor \right) $ and $h\left(
\left\lceil x\right\rceil \right)$. Then, the following are

$n^{-\rho }h(n)=P(\log_{2}n)+o(1)$ as $n\to \infty $, for some
continuous $1$-periodic function $P$ on $\mathbb{R}$.

$x^{-\rho }h(x)=P(\log_{2}x)+o(1)$ as $x\to \infty $, for some
continuous $1$-periodic function $P$ on $\mathbb{R}$.

<ref>$\implies$<ref> is trivial.

The proof of <ref>$\implies$<ref> is very similar to the
proof of (i)$\implies $(ii) in <cit.>, so we
omit some details. First, $\log_2x-\log_2\floor{x}=O(1/x)=o(1)$ for
large $x$ and $P$ is uniformly continuous, so $P(\log_2x)
=P\bigpar{\log_2\floor{x}}+o(1)$. Hence, <ref> implies that

\begin{align}
\floor{x}^{-\rho} h\bigpar{\floor{x}}
\end{align}

and consequently, ${x}^{-\rho} h\bigpar{\floor{x}}
=P\bigpar{\log_2{x}}+o(1)$. Similarly, ${x}^{-\rho}
h\bigpar{\ceil{x}}=P\bigpar{\log_2{x}}+o(1)$, and <ref> follows.

Suppose that $g(x)$ is a continuous function on $(0,\infty)$ with
$g(x)=0$ for $x\le 1$. Define

\begin{equation}\label{b12}
:=\sum_{k\ge 0}2^{k\rho }g(2^{-k}x).
\end{equation}

Then, the following are equivalent.

$x^{-\rho }h(x)=P_1(\log_{2}x)+o(1)$ as $x\to \infty $, for some
continuous $1$-periodic function $P_1$ on $\mathbb{R}$.

$x^{-\rho }h(x)=P_1(\log_{2}x)+o(1)$ as $x\to \infty $, for
some $1$-periodic function $P_1$ on $\mathbb{R}$.

$Q(x):=\sum_{k\ge 1}2^{-\rho k}g(2^{k}x)$ converges uniformly
for $x\in [1,2]$.

Furthermore, when these conditions hold, $Q(x)$ is defined for all
$x>0$, $Q(x)=o(x^\rho)$ as $x\to\infty$,

\begin{equation}\label{b13}
=\sum_{m\in \mathbb{Z}}2^{-\rho (m+t)}g(2^{m+t}),
\qquad t\in\mathbb{R},
\end{equation}

\begin{equation}\label{b14}
=x^{\rho }P_1(\log_{2}x)-Q(x),\qquad x>0.
\end{equation}

Again, the proof differs mainly notationally from the proofs of the
corresponding implications in <cit.>, and we
omit some details. Let $G_m(x):=\sum_{k=0}^m2^{-\rho k}g(2^{k}x)$,
and note that <ref> is equivalent to the property that $G_m(x)$
converges uniformly on $[1,2]$ to $G(x) :=Q(x)+g(x)$.

<ref>$\implies$<ref>. Trivial.

Suppose that $y\in[1,2]$ and $m\ge0$. Then (<ref>) yields

\begin{align}\label{bb1}
=\sum_{0\le k\le m} 2^{k\rho}g\bigpar{2^{-k+m}y}
=\sum_{0\le j\le m} 2^{(m-j)\rho}g\bigpar{2^{j}y}
\end{align}

Hence, taking $x=2^my$, <ref> implies, as $m\to\infty$, uniformly
for $y\in[1,2]$,

\begin{align}\label{bb2}
=(2^my)^{-\rho}  h\bigpar{2^my}
\end{align}

Hence $y^{-\rho}G_m(y)$ converges uniformly on $[1,2]$, and thus
$G_m(y)$ converges uniformly on $[1,2]$.

Conversely, (<ref>) now yields

\begin{align}\label{bb3}
(2^my)^{-\rho}  h\bigpar{2^my}
\end{align}

as $m\to\infty$, uniformly for $y\in[1,2]$. Next, we show that

\begin{align}\label{bb4}
:=\sum_{m\in\mathbb{Z}} 2^{-\rho(m+t)}g\bigpar{2^{m+t}}.
\end{align}

is a well-defined $1$-periodic function. First, if $t\in[0,1]$, then
all terms with $m<0$ vanish and thus

\begin{align}\label{bb5}
:=\sum_{m\ge0} 2^{-\rho(m+t)}g\bigpar{2^{m+t}}
=2^{-\rho t} G(2^t),
\end{align}

where the sum converges uniformly for $t\in\oi$ by assumption. This
shows that the sum in (<ref>) converges for $t\in[0,1]$, and
that $P_1(t)$ is continuous there. Furthermore, the sum in
(<ref>) is $1$-periodic in $t$, and thus the sum converges for
all real $t$ and defines a $1$-periodic continuous function

Taking $m=L_x$ and $y=2^{\gth_x}$ in (<ref>) yields as
$x\to\infty$, using (<ref>) and the periodicity of $P_1$,

\begin{align}
=P_1\bigpar{\log_2 x}+o(1).
\end{align}

Hence <ref> holds.

Finally, (<ref>) is (<ref>), which also shows that the sum
defining $Q(x)$ converges for all $x>0$, and that

\begin{align}
&=\sum_{k\ge 0}2^{k\rho }g(2^{-k}x)
+\sum_{k\ge 1}2^{-\rho k}g(2^{k}x) \notag\\
&=\sum_{k\in\mathbb Z}2^{-k\rho }g(2^{k}x)\notag\\
&=x^\rho P_1\bigpar{\log_2x}.
\end{align}

\begin{align}
(2^mx)^{-\rho}Q(2^mx) =x^{-\rho} \sum_{k\ge1} 2^{-\rho(k+m)}g(2^{k+m}x)
=x^{-\rho} \sum_{k\ge m+1} 2^{-\rho k}g(2^{k}x),
\end{align}

which by <ref> converges to 0 as $m\to\infty$, uniformly for
$x\in[1,2]$. Hence, $x^{-\rho}Q(x)\to0$ as $x\to\infty$.

This completes the proof of the proposition.

First, <ref>$\iff$<ref> follows from
Proposition1, with $h(x)=f(x)$.

Next, define $h(x):=f(x)-x^\rho f(1)P_0\bigpar{\log_2x}$, and note
that (<ref>) implies (<ref>). Thus
<ref>$\iff$<ref>$\iff$<ref> and the
last sentence of the statement follow from Proposition2, with

A more practical condition than uniform convergence is the

\begin{equation}
:=\sup_{2^{m}\le n\le 2^{m+1}}|g(n)|.
\end{equation}

If $\,\sum_{m}2^{-m\rho }A_{m}<\infty $ then (<ref>) and
(<ref>) hold, where $P$ is continuous, periodic and given by

Suppose that $g(n)=O\bigpar{n^{\rho-\eps}}$ for some $\eps>0$. Then
(<ref>) and (<ref>) hold with $P$ continuous, periodic and
given by (<ref>), and $Q(x)=O(x^{\rho-\eps})$.

One simple but important case is when $g(n)=0$, $n\ge2$, i.e., the
recurrence $\Lambda_{\ga,\gb}[f]=0$. By suitable normalisations, we
may assume $f(1)=1$. As the sequence $f$ satisfying
$\Lambda_{\alpha,\beta}[f]=0$ with $f(1)=1$ plays a fundamental role
in most of our applications, we denote the solution by
$S_{\alpha,\beta}(n)$ throughout this paper.

Theorem1 applies trivially, with $Q(x)=0$ and $P(t)=P_0(t)$,
and thus

\begin{align}\label{Sgagb}
= f(n)
= n^{\log_2(\ga+\gb)}P_0(\log_2 n)
,\qquad n\ge1,
\end{align}

where $P_0(t)$ is given by (<ref>); thus also, more explicitly,

\begin{align}\label{Sgagb2}
= \bigpar{ 1+( \alpha +\beta-1)
\varphi\lpa{2^{\para{\log_2n}}-1}}
(\alpha +\beta)^{\floor{\log_2 n}}.
\end{align}

(In the case $\ga=\gb$, when $\gf(x)=x$ by Rlinear,
(<ref>) was found, in an equivalent form, by [14].)

Another simple but important case is when $g(2m)=0$ for all $m\ge1$,
i.e., $g(n)$ is non-zero only for odd $n$. Suppose also, for example,
that $g(n)=O(n^{\rho-\eps})$ so that C2 applies. Then,
(<ref>) shows that $Q(n)=0$ for every integer $n$, and thus
(<ref>) yields the identity $f(n)=n^\rho P(\log_2 n)$, $n\ge1$.

We have here studied the case with $o$-estimates and convergence in
e.g. Theorem1. Analogously, we note that it follows easily
from Lemma3 and (<ref>) that

\begin{equation}
\begin{split}
f(x)=O(x^\rho) \quad\text{for }x\ge1 \\
% G_m(x):=
\sum_{0\le k\le m}2^{-\rho k}g(2^{k}x)=O(1)
\quad\text{for $x\in[1,2]$ and $m\ge0$}.
\end{split}
\end{equation}

We concentrate in this paper on the case when $g(n)$ grows more
slowly than $n^\rho$ (and (<ref>) converges), and thus the sums
in (<ref>) and (<ref>) are dominated by terms with $k$ large
(more precisely, $k=L_x+O(1)$ in (<ref>)). One might also
consider the opposite case, when $g(n)$ grows more rapidly that
$n^\rho$. In this case, the sums in (<ref>) and (<ref>) are
dominated by their first terms, which shows that (typically, at
least) $f(n)$ grows at the same rate as $g(n)$, and has the same
smoothness properties. (In particular, there is no smoothening effect
as we can see in (<ref>).) We consider one example as part of
EMoser, but we otherwise leave this case to a future study.
(Except for several examples where we reduce to a slower growing $g$
by subtracting a polynomial.)

§ SMOOTHNESS PROPERTIES OF THE PERIODIC FUNCTION $P$

We prove in this section that under certain conditions on $g(n)$
stronger than those in Theorem1, the periodic function $P$
is  continuous, and has an absolutely convergent Fourier
series expansion. We also show that the interpolating function
$\gf$ is  continuous, and thus the interpolated function
$f(x)$ is not only continuous but always locally  continuous.

In this section, starting from the recursion (<ref>), we tacitly
assume that $\alpha,\beta>0$ and $g(1)=0$; also $P_0$, $P_1$ and $P$
are functions defined as in S:recurrence; furthermore, we

\begin{align}\label{E:lambda}
\lambda
:=\log_{2}\frac{\alpha +\beta}
{\alpha \vee \beta}\in (0,1].
\end{align}

Note that $\gl=1$ if and only if $\ga=\gb$.

Bounded variation, Lipschitz continuity and Hölder
We recall some standard definitions. A function $\phi $ is
Lipschitz continuous on an interval $[a,b]$ if there exists
a positive number $C$ such that

\begin{equation}
\le C|x-y| \quad \text{(}x,y\in [a,b]\text{).}
\end{equation}

This definition extends to Hölder continuity by replacing
the last inequality by

\begin{equation}
| \phi(x)-\phi(y)|
\le C| x-y|^{\gamma}\quad \text{(}x,y\in [a,b]\text{)},
\end{equation}

for some $0<\gamma \le 1$. Let $\mathrm{H}_{\gamma}[a,b]$ be the
space of functions $\phi $ on $[a,b]$ such that the seminorm

\begin{equation}\label{c1}
\| \phi\|'_{\mathrm{H}_{\gamma}[a,b]}
:=\sup_{a\le x<y\le b}\frac{|\phi(x)-\phi(y)|}
\end{equation}

is finite; this is a Banach space with the norm

\begin{equation}\label{c2}
\|\phi\|_{\mathrm{H}_{\gamma}[a,b]}
+\sup_{x\in [a,b]}| \phi(x)| .
\end{equation}

A function $\phi $ is of bounded variation on $[a,b]$ if its
total variation is bounded. Such a function is differentiable almost
everywhere. Let $\mathrm{BV}[a,b]$ be the space of functions on
$[a,b]$ of bounded variation, with the norm

\begin{equation}
\|\phi\|_{\mathrm{BV}[a,b]}
\end{equation}

where $V$ denotes the total variation.

Note that both $\mathrm{BV}[a,b]$ and $\mathrm{H}_{\gamma}[a,b]$ are
Banach algebras. Also $\mathrm{H}_{1}\subset \mathrm{BV}$, namely,
Lipschitz continuity implies bounded variation.

Smoothness of $\gf$ and $P$.
We prove first that the interpolating function $\gf$ is Hölder
continuous. Note that $\gf$ is trivially of bounded variation since
it is monotone.

$\varphi \in\mathrm{H}_{\lambda}[0,1]$.

First, let $x=m2^{-N}$ and $y=(m+1)2^{-N}$ for some integers
$N\ge0$ and $m<2^N$. Then (<ref>) implies

\begin{align}\label{lh1}
\gf(y)-\gf(x)
\le \Bigpar{\frac{\ga\vee \gb}{\ga+\gb}}^{N}
\end{align}

For general $x$ and $y$ with $0\le x< y\le 1$, let $N:=\ceil{-\log_2
\left( y-x \right)}$ and $k:=\floor{x2^N}$. Then $2^{-N}\le y-x \le
2^{1-N}$ and $k2^{-N} \le x<y\le (k+3)2^{-N}$. Hence, using
(<ref>) thrice,

\begin{equation}
\varphi(y)-\varphi(x)
\le \gf\bigpar{(k+3)2^{-N}} - \gf\bigpar{k2^{-N}}
\le  3\cdot 2^{-N\gl}
\le 3|y-x|^\gl.
\end{equation}

This proves that $\varphi \in\mathrm{H}_{\lambda}[0,1]$.

$P_0\in \HH_\gl[0,1]\cap \BV[0,1]$.

For $t\in[0,1]$, we may replace $\{t\}$ by $t$ in (<ref>). It
then follows from LHolder that the first factor in
(<ref>) belongs to $\mathrm{H}_{\lambda}\oi$, and so does the
second factor since it has a bounded derivative. Hence, $P_0\in
\mathrm{H}_{\lambda}\oi$.

Similarly, both factors in (<ref>) then are monotone on
$[0,1)$, and therefore of bounded variation. Hence $P_0\in
\mathrm{BV}[0,1]$.

To treat the function $P$, we need a smoothness assumption on the
sequence $g(n)$. Let

\begin{align}\label{AB}
:=\max_{2^{m}\le n\le 2^{m+1}}| g(n)|
\eqtext{and}
B_{m}:=\max_{2^{m}\le n<2^{m+1}}| g(n+1)-g(n)| .
\end{align}

If $\rho>0$ and

\begin{equation}\label{c3}
\sum_{m\ge0}2^{(1-\rho )m}B_{m}
\end{equation}

\begin{align}\label{c3A}
\sum_{m\ge0}2^{-\rho m }A_{m}
<\infty .
\end{align}

Note that $\rho>0$ is equivalent to $\ga+\gb>1$.

Let $m\ge1$. For every $n$ lying in the interval $2^{m}\le n\le

\begin{align}\label{cj1}
&\le |g(2)|+\sum_{2\le j<n}|g(j+1)-g(j)|\notag\\
&\le |g(2)|+\sum_{1\le k\le m}2^{k}B_{k},
\end{align}

implying that

\begin{equation}\label{cj2}
\le |g(2)|+\sum_{1\le k\le m}2^{k}B_{k}.
\end{equation}

\begin{align}\label{cj3}
\sum_{m\ge1}2^{-\rho m}A_{m}
&\le \sum_{m\ge1}2^{-\rho m}
\biggpar{|g(2)|+\sum_{1\le k\le m}2^{k}B_{k}}\notag\\
\end{align}

This proves the lemma.

If $\rho>0$ and (<ref>) holds, then $P\in \HH_\gl[0,1]\cap
\BV[0,1]$.

Let $g_{m}(x):=g(2^{m}x)$. Then, by (<ref>) and $g(x)=0$ for
$x\le 1$, we have

\begin{equation}\label{c5}
=2^{-\rho t}\sum_{m\ge0}
2^{-\rho m}g_{m}(2^{t})+f(1)P_0(t)
\qquad(t\in [0,1]).
\end{equation}

Since the function $2^{-\rho t}$ belongs to $\mathrm{BV}[0,1]$,
which is a Banach algebra, we see that

\begin{equation}\label{c6}
\Vert P(t)\Vert_{\mathrm{BV}[0,1]}
\le \CC\sum_{m\ge0}2^{-\rho m}
\Vert g_{m}(2^{t})\Vert_{\mathrm{BV}[0,1]}
+|f(1)|\,\Vert P_0(t)\Vert_{\mathrm{BV}[0,1]},
\end{equation}

for some constant $\CCx>0$. Furthermore, by the monotonicity of
the interpolating function $\varphi$, we obtain

\begin{align}\label{c7}
\Vert g_{m}(2^{t})\Vert_{\mathrm{BV}[0,1]}
&=\Vert g_{m}(x)\Vert_{\mathrm{BV}[1,2]}\notag \\
&=\Vert g(x)\Vert_{\mathrm{BV}[2^{m},2^{m+1}]}\notag\\
&=\sup_{2^m \le x\le 2^{m+1}}|g(x)| +
\sum_{2^{m}\le n<2^{m+1}}|\Delta g(n)|\notag\\
&\le A_m+ 2^{m}B_{m},
\end{align}

where $\Delta g(n):=g(n+1)-g(n)$. It follows from
(<ref>)–(<ref>), Lemma5, (<ref>) and Lemma4
that $P(t)\in \mathrm{BV}[0,1]$.

Similarly, for the Hölder norm, we have

\begin{align}\label{c8}
\Vert P_1(t)\Vert_{\mathrm{H}_{\lambda}[0,1]}
&\le \CC\sum_{m\ge 0}2^{-\rho m}
\Vert g_{m}(2^{t})\Vert_{\mathrm{H}_{\lambda}[0,1]} \notag\\
&\le \CC\sum_{m\ge 0}2^{-\rho m}
\Vert g_{m}(x)\Vert_{\mathrm{H}_{\lambda}[1,2]},
\end{align}

where, furthermore, by the definitions (<ref>)–(<ref>) and

\begin{align}\label{c8a}
\Vert g_{m}(x)\Vert_{\mathrm{H}_{\lambda}[1,2]}
&= \Vert g_{m}(x)\Vert'_{\mathrm{H}_{\lambda}[1,2]}
+\sup_{x\in[1,2]}|g_m(x)| \notag\\
&= 2^{\lambda m}
\Vert g(x)\Vert'_{\mathrm{H}_\lambda[2^{m},2^{m+1}]}
+\sup_{x\in[2^{m},2^{m+1}]}|g(x)| \notag\\
&= 2^{\lambda m}
\Vert g(x)\Vert'_{\mathrm{H}_\lambda[2^{m},2^{m+1}]}
\end{align}

In order to bound $\Vert g\Vert'_{\mathrm{H}_\lambda[2^{m},
2^{m+1}]}$, we estimate $|g(y)-g(x)|$ for $2^{m}\le x\le y\le 2^{m+1}
$. By splitting the interval $[x,y]$ into $[x,\left\lceil
x\right\rceil ]$, $[\left\lceil x\right\rceil ,\left\lfloor
y\right\rfloor ]$ and $[\left\lfloor y\right\rfloor ,y]$, it suffices
(up to a constant factor in the norm) to consider the two cases $n\le
x\le y\le n+1$ and $x=n$, $y=n+\eta$, where $n$ and $\eta$ are

In the first case, $n\le x\le y\le n+1$ with $2^{m}\le n<2^{m+1}$, we
have $g(y)-g(x)=\Delta g(n)\left( \varphi (y)-\varphi(x)\right)$.
Since $\varphi \in \mathrm{H}_{\lambda}[0,1]$ by LHolder,

\begin{equation}\label{c9}
\le \CC|\Delta g(n)|\,|y-x|^{\lambda}
\le \CCx B_{m}|y-x|^{\lambda}.
\end{equation}

In the second case,

\begin{equation}\label{c10}
\le \sum_{0\le i<\eta}|\Delta g(n+i)|
\le \eta B_{m}
\le B_{m}2^{m(1-\lambda )}\eta^{\lambda}.
\end{equation}

Combining the two cases, we obtain from (<ref>) and (<ref>)

\begin{equation}\label{c11a}
\Vert g\Vert_{\mathrm{H}_{\lambda}[2^{m},2^{m+1}]}^{\prime }
\le \CC B_{m}2^{(1-\lambda )m}.
\end{equation}

Consequently, (<ref>) yields

\begin{equation}
\Vert g_m\Vert_{\mathrm{H}_{\lambda}[1,2]}
\le \CCx2^{m} B_{m} +A_m. \label{c11b}
\end{equation}

It follows from (<ref>), (<ref>), (<ref>) and
Lemma4 that $P_1\in \mathrm{H}_{\lambda}[0,1]$, and then $P\in
\mathrm{H}_{\lambda}[0,1]$ by Lemma5.

LHolder is best possible: $\gf\notin \mathrm{H}_{\gam }\oi$
for $\gam>\gl$. In particular, $\gf$ is not Lipschitz continuous
(and not differentiable) unless $\ga=\gb$. To see this, it suffices
to note that (<ref>) yields $\gf(2^{-j})-\gf(0)=
\bigpar{\frac{\gb}{\ga+\gb}}^j$ and $\gf(1)-\gf(1-2^{-j})=
\bigpar{\frac{\ga}{\ga+\gb}}^j$ for all $j\ge1$, and one of these
equals $\bigpar{\frac{\ga\vee\gb}{\ga+\gb}}^j

Hence, (<ref>) shows that if $\ga+\gb\neq1$, then also
Lemma5 is best possible: $P_0\notin \mathrm{H}_{\gam }\oi$ for
$\gam>\gl$. Furthermore, (<ref>) shows that typically also
$P\notin \mathrm{H}_{\gam }\oi$ for $\gam>\gl$. (Also in the case
$f(1)=0$, since $g(x)$ has the same smoothness as $\gf$.) However,
note that $P$ may be more smooth in special cases (which means that
there is cancellation of non-smoothness in (<ref>)); for example,
we may take any continuously differentiable periodic function $P(t)$
and let $f(n):=n^\rho P(\log_2n)$ and then define $g(n)$ by

Fourier series.
The periodic function $P(t)$ may be described by its Fourier
coefficients; these are given by the following formula, where we use
the notation

\begin{align}\label{chik}
\chi_{k}:=\frac{2k\pi }{\log 2}\ii,
\qquad  k\in\bbZ.
\end{align}

If Theorem1<ref> holds (and thus all statements in
Theorem1), then the Fourier coefficients
$\hP(k):=\int_{0}^{1}P(t)e^{-2k\pi it}\dd t$ of $P(t)$ are given by

\begin{equation}\label{c4}
\widehat{P}(k)
=\frac{1}{\log 2}\int_{1}^{\infty }
\frac{g(u)}{u^{\rho + \chi_{k}+1}}\dd u
+\frac{f(1)}{\log 2}\int_{0}^{1}
\frac{1+(\alpha +\beta -1)\varphi(u)}
{(1+u)^{\rho +\chi_{k}+1}}\dd u,
%\qquad k\in\bbZ,
\end{equation}

where the first integral is (at least) conditionally convergent.

If (<ref>) holds, then (<ref>) holds, with absolutely
convergent integrals.

If $\ga+\gb>1$ and (<ref>) holds, then $P(t)$ has an absolutely
convergent Fourier series $P(t)=\sum_{k\in
\mathbb{Z}}\widehat{P}(k)e^{2\pi ikt}$, for $t\in \mathbb{R}$, where
the coefficients are given by (<ref>), with absolutely convergent

The Fourier coefficients of $P(t)$ are given by, using the
definitions (<ref>), (<ref>) and (<ref>),

\begin{align}\label{c41}
\widehat{P}(k)
&:=\int_{0}^{1}P(t)e^{-2k\pi it}\dd t
\notag\\
&=\sum_{m\in \mathbb{Z}}\int_{0}^{1}g\left( 2^{m+t}\right)
2^{-\rho(m+t)}e^{-2k\pi it}\dd t
\notag\\
\left( 1+(\alpha +\beta -1)\varphi\left(2^{t}-1\right)
\right) (\alpha +\beta )^{-t}e^{-2k\pi it}\dd t
\notag\\
&=\int_{-\infty}^{\infty}g\xpar{ 2^{t}}
2^{-\rho t}e^{-2k\pi it}\dd t
\notag\\
\left( 1+(\alpha +\beta -1)\varphi\left( 2^{t}-1\right)
\right) 2^{-\rho t}e^{-2k\pi it}\dd t,
\end{align}

where the sum and the integral over $(-\infty,\infty)$ are
(conditionally) convergent because the sum in (<ref>) converges
uniformly, and $g(x)=0$ for $x\le1$. (The integrals over $\oi$ are,
trivially, absolutely convergent.) Finally, (<ref>) follows by the
changes of variables $u=2^t$ and $u=2^t-1$, respectively, in the two

C1 shows that all statements in Theorem4 hold, and thus
part <ref> applies, which gives (<ref>). The absolute
convergence of the first integral follows by (<ref>).

By Lemma4, we have (<ref>), and thus <ref> applies.
Since $P$ is a continuous $1$-periodic function, the absolute
convergence of the Fourier series follows directly from Lemma
<ref> by a theorem of Zygmund (see <cit.> or <cit.>).

The formula (<ref>) shows a connection with Mellin transforms;
this is explored further in AMellin.

The conditions of Theorem4<ref> are, of course, not
necessary for absolute convergence of the Fourier series of $P(t)$.
Another simple case is the following.

If $\ga,\gb>0$ and $g(n)=0$, $n\ge2$, we may normalise by $f(1)=1$ as
in Eg=0; thus $f(n)=S_{\ga,\gb}(n)$ and (<ref>) holds.
$P(t)=P_0(t)$ has an absolutely convergent Fourier series, given by
(<ref>) with $g(x)=0$. This follows as in the proof of
Theorem4, now using Lemma5.

Many other examples of $P(t)$ with absolutely convergent Fourier
series are given in Sections <ref>–<ref>. An example
where the Fourier series is not absolutely convergent is part of
EMoser (for some $\ga$).

In the case $\ga=\gb$, the integrals in (<ref>) can easily be
evaluated explicitly, and we obtain the following extension of the
case $\ga=\gb=1$ in <cit.>. Let, as in

\begin{align}\label{D1}
:=\sum_{n\ge2} g(n)\Bigpar{(n-1)^{-s}-2n^{-s}+(n+1)^{-s}},
\end{align}

for all complex $s$ such the sum is convergent; note that if
$g(n)=O(n^{\rho-\eps})$ for some $\eps\ge0$ (this holds at least with
$\eps=0$ whenever Theorem1 applies), then the sum in
(<ref>) is absolutely convergent in the half-space $\Re s
>\rho-1-\eps$, and thus $D(s)$ is analytic there. Note also (as in
[27]) that if $\Re s$ is large enough, (<ref>) can be
rearranged as a Dirichlet series (using $g(0)=g(1)=0$)

\begin{align}\label{D2}
=\sum_{n\ge1} \Bigpar{g(n+1)-2g(n)+g(n-1)}n^{-s}.
\end{align}

If $\ga=\gb>0$ and Theorem1<ref> holds (and thus all
statements in Theorem1), then, assuming $\rchi_k\neq0,1$,

\begin{align}\label{c4+}
\hP(k) &= \frac{1}{(\rho+\chi_k)(\rho-1+\chi_k)\log 2}
\Bigpar{D(\rho-1+\chi_k)
+ \frac{(2\ga-1)(\ga-1)}{\ga}f(1)}.
\end{align}

The formula (<ref>) is used (often tacitly) in numerous examples

The two exceptional cases are $k=0$ and either $\ga=\gb=\frac12$ or
$\ga=\gb=1$; in these cases, (<ref>) is of the form $0/0$ and is
replaced by a suitable limit form. The case $\ga=1$ is included in
<cit.>; the case $\ga=\frac12$ is similar, but
we omit the details.

Theorem4 applies and yields (<ref>); we treat the two
integrals in (<ref>) separately. For the first integral,
<cit.> holds whenever
$\ga=\gb$, and shows that

\begin{align}\label{maja}
\int_{1}^{\infty } \frac{g(u)}{u^{\rho + \chi_{k}+1}}\dd u
= \frac{D(\rho-1+\chi_k) }{(\rho+\chi_k)(\rho-1+\chi_k)},
\end{align}

with the sum (<ref>) converging at least conditionally.

Since $\ga=\gb>0$, we have $\gf(u)=u$ and thus the second integral in
(<ref>) is, by a simple calculation using

\begin{align}\label{maj0}
\int_{0}^{1}  \frac{1+(2\alpha -1)u}
{(1+u)^{\rho +\chi_{k}+1}}\dd u
&=\int_{0}^{1}\lrpar{\frac{2\alpha -1} {(1+u)^{\rho +\chi_{k}}}
+    \frac{2-2\alpha} {(1+u)^{\rho +\chi_{k}+1}}}\dd u
\notag\\&
\cdot\frac{1}{(\rchi_k)(\rho-1+\chi_k)}.
\end{align}

Using (<ref>)–(<ref>) in (<ref>) yields (<ref>).

For later use we note that, still assuming $\ga=\gb$, if the
condition Theorem1<ref> holds, then
<cit.> more generally yields the Mellin transform

\begin{align}\label{majs}
\int_{1}^{\infty } \frac{g(u)}{u^{s+1}}\dd u
= \frac{D(s-1) }{s(s-1)}
\end{align}

with the integral converging absolutely at least for every complex
$s$ with $\Re s>\rho$.

Let $\ga=\gb>0$, and consider $P_0(t)$ given by (<ref>) in
Ra=b. By ChPa=b, with $g(n)=0$ and $f(1)=1$ (and thus
$D(s)=0$), we have the Fourier coefficients, assuming

\begin{align}\label{maj1}
\hP_0(k)
\frac{1}{(\rchi_k)(\rho-1+\chi_k)},
\qquad k\in\bbZ.
\end{align}

In particular, (<ref>) verifies that $P_0(t)$ has an absolutely
convergent Fourier series, as shown more generally in Eg=0b.
If $\ga\in\para{\frac12,1}$ (so $\rho=0$ or 1), (<ref>) shows
that $\hP_0(k)$ vanishes for every $k\neq0$, which is obvious since
then $P_0(t)\equiv1$ by Ra=b. In all other cases, (<ref>)
yields $\bigabs{\hP_0(k)}=\Theta\bigpar{k^{-2}}$ as $k\to\pm\infty$,
which agrees well with the fact that $P_0(t)$ is Lipschitz but not
$C^1$; see again Ra=b.

Again, by the recursive relations in (<ref>), we can express the
second integral in (<ref>) in the series form

\begin{align}\label{E:int-phi}
\int_0^1 \frac{1+(\alpha+\beta-1)\varphi(t)}
{(1+t)^{\rho+\chi_k+1}}\,\dd t \nonumber\\
&\quad =  1+ \sum_{m\ge0}\sum_{0\le j<2^m}
\alpha^{\nu(j)}\beta^{m+1-\nu(j)}
\Lpa{\frac1{(2^m+j+\tfrac12)^{\rho+\chi_k}}
\end{align}

which is more useful for numerical purposes, where $\nu(j)$ denotes
the number of $1$s in the binary expansion of $j$. See
Appendix <ref> for a proof.

§ APPLICATIONS, I. $\ALPHA\NE\BETA$

We discuss applications of our results in this section, grouping them
according to the growth order of $g$. Most examples are taken from
OEIS, sometimes with a shift of the index (which for simplicity of
presentation is not explicitly specified in this paper). For example,

\begin{align}
f(n) = \alpha f\lpa{\ltr{\tfrac {n+d}2}}
+\beta f\lpa{\lcl{\tfrac {n+d}2}}+ g(n)
\qquad(n\ge n_0\ge1),
\end{align}

then $\bar{f}(n) := f(n+d)$ satisfies

\begin{align}
\bar{f}(n)
=\alpha \bar{f}\lpa{\ltr{\tfrac{n}2}}
+\beta \bar{f}\lpa{\lcl{\tfrac{n}2}}+ g(n+d)
\qquad(n\ge n_0-d).
\end{align}

Note also that if (<ref>) holds only for $n\ge n_0$, we can make
it hold for all $n\ge2$ by redefining $g(n)$ for $2\le n<n_0$. See
A294456 (contained in E11) for an example.

Some of the examples are defined in OEIS by a recursion of the form
(<ref>); in other examples, such a recursion is stated as a
property; in yet other examples below, no such recursion is given
explicitly in OEIS, but can be concluded from other properties given
there. Of course, every sequence $f(n)$ satisfies
$\gL_{\ga,\gb}[f]=g$ for some sequence $g(n)$; we are only interested
in cases when $g(n)$ has a simple explicit form, and in particular
does not grow too fast. We regard polynomial terms in $f(n)$ as
essentially trivial, so we also include examples when they dominate
$f$ and the periodic fluctuations constitute a lower-order term. (In
such cases our theorems apply only after subtracting a suitable

To avoid trivialities, we discard in our discussions sequences from
OEIS whose generating functions are rational with all singularities
on the unit circle. (For example, polynomials.) Such sequences are in
the thousands in OEIS.

For notational convenience, we insert the subscript to $\varphi$ by
writing $\varphi^{}_{\alpha,\beta}(t)$ whenever necessary. The
symbols $f(n), g(n)$ and $P(t)$ are all generic and may differ from
one instance to the other; we also specify explicitly them as
$f_{\text{A006046}}(n)$, $g_{\text{A006046}}(n)$, and
$P_{\text{A006046}}(t)$ if needed. Note that our indexing of the
sequence $f$ may differ from that on OEIS by a shift; for example,
$f_{\text{A006581}}(n)=\text{A006581}(n+1)$ for $n\ge1$. Also the
format $g(n) = \begin{cases}\cdots\\ \cdots \end{cases}$ in the
tables without explicit mention always means the values of $g(n)$ in
the even and odd cases, respectively.

We continue to assume $\ga,\gb>0$, and consider in this section cases
with $\ga\neq\gb$. On the other hand, examples in the special cases
when $\alpha=\beta$ exhibit more structural properties and explicit
expressions, and will be discussed in Section <ref>. The
properties are very similar to the case when $\alpha=\beta=1$ that we
already examined in detail in [27], although there are
also subtle differences on the smoothness of the periodic functions.

§.§ Periodic equivalence

We introduce a simple notion here, very useful in identifying the
relation between sequences. The main case is when two sequences $f_1$
and $f_2$ both satisfy Theorem1 (with the same $\rho$), and
the corresponding periodic functions $P_1$ and $P_2$ are the same, or
more generally proportional. It will be convenient to be a bit more
general, and regard polynomial terms as trivial. We thus define:

Two sequences $f_1$ and $f_2$ are said to be periodically
equivalent if, for some $\rho$, $f_j(n)=n^\rho P_j(\log_2n)+p_j(n)$,
$j=1,2$, where $p_j(n)$ are polynomials and $P_j$ are periodic
functions such that ${P}_1(k)=c{P}_2(k)$ for some constant $c\neq0$.
For simplicity, we write $f_1\Bumpeq f_2$.

It is possible to extend the definition to asymptotically
periodic equivalence by allowing $f_j(n)=n^\rho
P_j(\log_2n)+p_j(n)+o(n^\rho)$ for $j=1,2$, but the above definition
without $o(1)$-term is sufficient for our use in this paper.

We begin with the simplest cases when $\gL_{\ga,\gb}[f](n)=g(n)=0$.
Such cases cover also the situation when $g(n)=c$ for $n\ge2$ because
normalising $f$ by $\bar{f}(n) := f(n) +\frac{c}{\alpha+\beta-1}$
yields the recurrence $\Lambda_{\alpha,\beta}[\bar{f}]=0$ with
$\bar{f}(1) = f(1) + \frac{c}{\alpha+\beta-1}$. For convenience of
reference, we state this observation, in a somewhat generalised form,
as a lemma.

If $\alpha+\beta>1$, then two sequences defined by
$\Lambda_{\alpha,\beta}[f_1]=0$ with $f_1(1)\ne0$ and
$\Lambda_{\alpha,\beta}[f_2]=c$ are connected by

\begin{align}\label{l4.1}
= \left(f_2(1)+\frac{c}{\alpha+\beta-1}\right)
\frac{f_1(n)}{f_1(1)}
\end{align}

Hence, if $f_2(1) +\frac{c}{\alpha+\beta-1}\ne0$, the sequences
$f_1(n)$ and $f_2(n)$ are periodically equivalent with the underlying
periodic function $P$ satisfying $P\in \HH_\gl[0,1]\cap \BV[0,1]$,
where $\lambda$ is defined in (<ref>).

It is easy to verify that (<ref>) satisfies the recursion
$\Lambda_{\alpha,\beta}[f_2]=c$. and thus (<ref>) holds by
induction. Thus $f_1\Bumpeq f_2$ if $f_2(1)
+\frac{c}{\alpha+\beta-1}\ne0$. The Hölder continuity and bounded
variation of $P$ follow from Lemma <ref>.

Write $f\sim\XLambda_{\alpha,\beta}[c;d,e]$ if
d, & \text{$n$ even}\\
e, & \text{$n$ odd} \end{cases}$ for $n\ge2$.
Suppose that $\alpha+\beta>2$, and that

\begin{align}\label{L-31a}
f_1\sim \XLambda_{\alpha,\beta}[c;d,e]
\quad\text{and}\quad
\left[0;0,
\frac{(\alpha-\beta)c}{\alpha+\beta-2}-d+e\right],
\end{align}

where $f_2(1)=f_1(1)+\frac{2c}{\alpha+\beta-2}
+\frac{d}{\alpha+\beta-1} \neq0$. Then $f_1\Bumpeq f_2$. Furthermore,

\begin{align}\label{L-31b}
f_1(n) = n^\rho P(\log_2n)-
\frac{2cn}{\alpha+\beta-2}
\end{align}

for a periodic function $P\in \HH_\gl[0,1]\cap \BV[0,1]$.

The normalised sequence

\begin{align}\label{L-31c}
\bar{f}(n) := f_1(n) + \frac{2cn}{\alpha+\beta-2}
\end{align}

\begin{align}\label{L-31d}
\Lambda_{\alpha,\beta}[\bar{f}]
= \left(\frac{(\alpha-\beta)c}{\alpha+\beta-2}-d+e\right)
\cdot \mathbf{1}_{n\text{ is odd}},
\end{align}

with the initial condition $\bar{f}(1) =
f_1(1)+\frac{2c}{\alpha+\beta-2} +\frac{d}{\alpha+\beta-1}$. Thus,
$\bar{f}=f_2$. Furthermore, $f_2(n)=n^\rho P(\log_2n)$ for a periodic
function $P$ by Eodd. This yields (<ref>). Again, the
Hölder continuity and bounded variation of $P$ follow from
Lemma <ref>.

§.§ $\Lambda_{\alpha, \beta}[f]=0$

[Generating polynomial of the sum-of-digits
As an immediate application of Theorem4, we consider the
following partial sum

\begin{equation}\label{Sn-theta}
:=\sum_{0\le k<n}\alpha^{\nu(k)}\qquad (n\ge 0),
\end{equation}

where $\alpha>0$ and $\nu (n)$ denotes the number of $1$s in the
binary expansion of $n$. Such sums with various $\alpha$ have been
encountered and studied in a large number of different contexts;
see the recent survey [6] and the references therein
for more information. Then by (<ref>) and the recurrence

\begin{align}\label{nu-rec}
\nu(n)
+\mathbf{1}_{n\text{ is odd}}\qquad (n\ge 1),
\end{align}

we see that $f$ satisfies $\Lambda_{\alpha ,1}[f]=0$ with $f(1)=1$,
or (see Eg=0)

\begin{equation}\label{eq:Sa1}
f(n) = S_{\alpha,1}(n).
\end{equation}

Thus $g(n)\equiv 0$ for all $n$, so (<ref>) is trivial and
Theorem4<ref> applies. Furthermore, (<ref>) yields
$P(t)=P_0(t)$ given by (<ref>), and Theorem1 or
Eg=0 shows that

\begin{align}
=n^{\log_2(\alpha+1)}P_0(\log_2 n)
\qquad(n\ge1),
\end{align}

where, by Theorem4<ref> and (<ref>),

\begin{align}
:= (\alpha+1)^{-\{t\}}
\lpa{1+\alpha\varphi^{}_{\alpha,1}
\lpa{2^{\{t\}}-1}}
= (\alpha+1)^{1-\{t\}}
\varphi^{}_{\alpha,1}\lpa{2^{\{t\}-1}}
\end{align}

has an absolutely convergent Fourier series for $\alpha>0$. This
extends and improves the result established in [25] for
$\alpha$ in the range $(\sqrt{2}-1,\sqrt{2}+1)$, where a completely
different approach was employed: instead of Zygmund's theorem applied
above (see the proof of Theorem4), the proof in
[25] used a theorem of Bernstein saying that a periodic
function $P\in \mathrm{H}_{\lambda}$ with $\lambda >\frac{1}{2}$ has
an absolutely convergent Fourier series. Note that $\lambda
>\frac{1}{2}$ when $\alpha \in (\sqrt{2}-1,\sqrt{2}+1)$.

The Fourier coefficients $\widehat{P_0}(k)$ are by Theorem4
given by, with $\chi_{k}:=\frac{2k\pi i}{\log 2}$,

\begin{equation}\label{c20}
\widehat{P_0}(k)
=\frac{1}{\log 2}\int_{0}^{1}
\frac{1+\alpha \varphi^{}_{\alpha,1}(u)}
{(1+u)^{\log_{2}(\alpha+1 )+\chi_{k}+1}}\dd u
\qquad(k\in\mathbb{Z}).
\end{equation}

The same type of results also hold for the recurrence
$\Lambda_{1,\alpha}[f]=0$, the only difference being replacing the
underlying interpolation function $\varphi^{}_{\alpha,1}$ by

[Recurrence with minimisation or maximisation]

A class of sequences satisfying recurrences of the form

\begin{align}\label{E4.4}
\mu(n)
=\min_{1\le k\le \tr{\frac n2}}\{\alpha
\mu(k)+\beta \mu(n-k)\}\qquad (n\ge 2)
\end{align}

with $\mu(1)=1$ was studied in [5] to solve the AND-OR
Problem. It is proved there that if $\beta \ge \alpha$ are positive
integers, then the minimum in (<ref>) is reached at $k=\lfloor
\frac{n}{2}\rfloor $, so that $\mu(n)=f(n)=S_{\alpha,\beta}(n)$. In
this case, Theorem1 or Eg=0 and Eg=0b imply that
$\mu(n) = n^{\log_2(\alpha+\beta)}P_0(\log_2n)$, where $P_0$ is a
periodic function with an absolutely convergent Fourier series, given
by (<ref>). We can extend this to the cases (i)
$\beta\ge\alpha$, $\beta\ge1$ and (ii) $\alpha\ge\beta$,
$\alpha+\beta\le 1$; see Appendix <ref>.

On the other hand, it is not difficult to see that if $\beta\le 1$,
$\ga+\gb\ge1$, and $\ga\ge\gb^2$, then the minimum in (<ref>) is
attained at $k=1$, and we get a simple geometric expression for
$f(n)$. (Apart from the trivial case $\ga+\gb=1$, when $\mu(n)=1$,
these are the only $(\ga,\gb)$ for which the minimum always is
attained at $k=1$.) The behaviour of the recursion (<ref>) for
the remaining $(\ga,\gb)$ seems to be more complicated. (For example,
the case $1<\gb<\ga$.)

In Aminmix, we show in a similar manner that the solution to
the corresponding recurrence with maximisation

\begin{align}\label{rr-max}
\mu(n)
=\max_{1\le k\le \tr{\frac n2}}\{\alpha
\mu(k)+\beta \mu(n-k)\}\qquad (n\ge 2)
\end{align}

with $\mu(1)=1$ is given by $\mu(n)=f(n)=S_{\alpha,\beta}(n)$
whenever $\alpha\ge \beta$, $\beta\le 1$ and $\alpha+\beta\ge1$. We
again obtain, by Eg=0 and <ref>, that $f(n) =
n^{\log_2(\alpha+\beta)} P_0(\log_2n)$, where $P_0$ is the periodic
function in (<ref>), with an absolutely convergent Fourier
series. The case $\ga>\gb=1$ of (<ref>) was solved (in an
equivalent form) in [32].

For more recurrences with minimisation or maximisation, see
[22, 28] and the references therein.

[OEIS sequences satisfying
$\Lambda_{\alpha,\beta}[f]=0$ with $f(1)=1$ and thus
We collect OEIS sequences of this category in tb-ex4-3,
where $f$ and $P$ are both generic symbols, not necessarily the same
in each occurrence; some of the “popular" sequences will be discussed
in detail below.

1cOEIS id.
A000027     $(1,1)$     Natural numbers     $n$

A064194     $(1,2)$     Gates in AND/OR problem [5]

A006046     $(2,1)$     Odd entries in Pascal's triangle

A268524     $(1,3)$     $\Lambda_{1,3}[f]=0$ with $f(1)=1$

A130665     $(3,1)$     $S_{3,1}(n)$ (see (<ref>));
also (<ref>)

A073121     $(2,2)$     appeared in [14]

A268527     $(1,4)$     $\Lambda_{1,4}[f]=0$ with $f(1)=1$

A116520     $(4,1)$     (<ref>) with $(\alpha,\beta)=(4,1)$

A268526     $(2,3)$     $\Lambda_{2,3}[f]=0$ with $f(1)=1$

A268525     $(3,2)$     $\Lambda_{3,2}[f]=0$ with $f(1)=1$

A130667     $(5,1)$     (<ref>) with $(\alpha,\beta)=(5,1)$

A116522     $(6,1)$     Limit of the power of a matrix

A161342     $(7,1)$     3-D cellular automaton

A116526     $(8,1)$     Limit of the power of a matrix

A116525     $(10,1)$     Limit of the power of a matrix

A116524     $(12,1)$     $\Lambda_{12,1}[f]=0$ with $f(1)=1$

A116523     $(16,1)$     $\Lambda_{16,1}[f]=0$ with $f(1)=1$
OEIS sequences of the form $S_{\ga,\gb}(n)$ (ex4-3).

We will see that these sequences play to some extent a prototypical
role for more general recurrences with nonzero $g$.

On the other hand, the only periodic function in this table that
admits a closed-form expression in terms of elementary functions is
when $(\alpha,\beta)=(2,2)$ for which we have $P(t) =
2^{-\{t\}}\lpa{3-2^{1-\{t\}}}$, by (<ref>).

We note also the following example, where $\gL_{\ga,\gb}[f]$ is not
zero, but a constant.

We can generalise Enu by considering the partial sum, for

\begin{equation}\label{Sum-ab}
:=\sum_{0\le k<n}\alpha^{\nu(k)}\gb^{\nu_0(k)}\qquad (n\ge 0),
\end{equation}

where $\nu(n)$ is as above, and similarly $\nu_0 (n)$ denotes the
number of $0$s in the binary expansion of $n$ (with $\nu_0(0):=0$,

In analogy with (<ref>), we have the recurrence relation

\begin{align}\label{nu0-rec}
\nu_0(n)
+\mathbf{1}_{n\text{ is even}}\qquad (n\ge 1),
\end{align}

and it follows easily that $f$ satisfies  $f(1)=1$ and

\begin{align}\label{gab}
\Lambda_{\alpha ,\beta}[f](n)
\qquad (n\ge2).
\end{align}

Assume  $\ga+\gb>1$. Then, by (<ref>) and lmm-g-const,

\begin{equation}\label{fab}
= \frac{\ga}{\ga+\gb-1}S_{\alpha,\gb}(n)
+\frac{\gb-1}{\ga+\gb-1}\qquad (n\ge 1).
\end{equation}

\begin{equation}\label{Sn-ab}
=\frac{\ga+\gb-1}{\ga}\sum_{0\le k<n}
\alpha^{\nu(k)}\gb^{\nu_0(k)}-\frac{\gb-1}{\ga}
\qquad (n\ge 1).
\end{equation}

By (<ref>) and Eg=0, we have

\begin{align}
=n^{\log_2(\alpha+\beta)}P(\log_2 n)
\qquad(n\ge1),
\end{align}

with $P(t)=P_0(t)$ given by (<ref>). Furthermore, by
Theorem4 or Eg=0b, $P(t)$ has an absolutely convergent
Fourier series.

§.§ $(\alpha,\beta)=(1,2)$ and $(\alpha,\beta)=(2,1)$

The large number of concrete sequences discussed here and in the
following sections show the usefulness and power of the notion of
“periodic equivalence”.

[$\Lambda_{1,2}[f]=g$]  We begin
with A064194 in ex4-3, which satisfies $\Lambda_{1,2}[f]=0$
and thus equals $S_{1,2}(n)$. This sequence enumerates the number of
gates in the AND/OR problem (E4.4) [5]. It also
counts the number of multiplications needed to multiply two degree
$n$ polynomials using Karatsuba's algorithm
as well as the total number of odd entries in the
$(n+1)\times (n+1)$ matrix $\bigl[\binom{i+j}{i}\bigr]_{i,j=0}^n$.
Another interpretation in terms of Sierpiński-like arrays can be
found on Peter Karpov's webpage at

In this case, $f(n) = n^{\log_23}P(\log_2n)$ for $n\ge1$, where, by
Lemma <ref> or Theorem <ref>,

\begin{align}
P(t) = 3^{-\{t\}}
\lpa{1+2\varphi^{}_{1,2}\lpa{2^{\{t\}}-1}}.
\end{align}

Here the interpolation function $\varphi^{}_{1,2}$ has by (<ref>)
the form (see Figure <ref>)

\begin{align}
\varphi^{}_{1,2}\biggl(\sum_{k\ge 1}2^{-e_{k}}\biggr)
\qquad (1\le e_{1}<e_{2}<\cdots ).
\end{align}

Some other sequences periodically equivalent to $S_{1,2}(n)
=f_{\text{A064194}}(n)$ are given in tb-E12, where
denotes the bitwise logic AND operator; we also denote
by $b_j(n)$ the $(j+1)$st bit (from right to left) in the binary
expansion of $n$: $b_j(n) =
\tr{\frac{n}{2^j}}-2\tr{\frac{n}{2^{j+1}}}$ for $j=0,1,\dots,L_n$,
and $\nu_0(n)$ is as in Enu0 the number of $0$s in the binary
expansion of $n$.

1cOEIS id.
$\sum\limits_{0\le k,j<n}\mathbf{1}_{k\textsf{ AND } j\ne0}$
$\tr{\frac n2}^2-\mathbf{1}_{n \text{ odd}}$

$\sum\limits_{1\le j<n}2^{\nu_0(j)}$
$1$     $\frac12(S_{1,2}(n)-1)$

#(pairs $(k,m)$, $1\le k,m\le n$ such that

$(b_j(k),b_j(m))\ne(1,1)$, $0\le j\le \min\{L_k,L_m\}$)
$2\cl{\frac n2}-2$     $S_{1,2}(n)-2n+1$

A325103     #(pairs $(k,m)$, $1\le k<m\le n$ such that

$(b_j(k),b_j(m))\ne(1,1)$, $0\le j\le L_k$)
$\cl{\frac n2}-1$     $\frac12	S_{1,2}(n)-n+\frac12$

A325104     #(pairs $(k,m)$, $1\le k<m\le n$ such that

$(b_j(k),b_j(m))=(1,1)$ for some $0\le j\le L_k$)
$\binom{\tr{\frac n2}+1}{2}-1$

Sequences periodically equivalent to $S_{1,2}(n)$

Observe that

\begin{align}
f_{\text{A325103}}(n)- f_{\text{A325103}}(n-1)
= \text{A115378}(n)
= 2^{\nu_0(n)}-1,
\end{align}

and this provides a proof for the recurrence $\Lambda_{1,2}[f]
=\cl{\frac n2}-1$ satisfied by $f_{\text{A325103}}(n)$. The
consideration of the other two sequences A325102 and A325104 is
similar. On the other hand, the sequence $2^{\nu_0(n)}$ corresponds
to A080100 whose partial sum satisfies $\Lambda_{1,2}[f]=-1$ with
$f(1) = 1$. Then $f(n) = \frac12(S_{1,2}(n)+1)$.

Another example with $(\ga,\gb)=(1,2)$ is the sequence A086845, which
counts the number of comparators used in Bose and Nelson's sorting
networks [3], and satisfies $\Lambda_{1,2}[f]=\tr{\frac
n2}$ with $f(1)=0$. lmm-g-linear applies with
$(c,d,e)=(\frac12,0,-\frac12)$, giving $f(n) =
n^{\log_23}P(\log_2n)-n$; see [25]. In fact,
lmm-g-linear and its proof show that the periodically
equivalent sequence $h(n):=f(n)+n$ satisfies
$\Lambda_{1,2}[h]=-\mathbf{1}_{n\text{ odd}}$ with $h(1)=1$, and thus
$h(n)=n^{\log_23}P(\log_2n)$ by Eodd.

The periodic functions arising from the four sequences
(in left to right order) $\Lambda_{1,2}[f]=\tr{\frac n2}$,
$\Lambda_{1,2}[f]=\cl{\frac n2}$, $\Lambda_{2,1}[f]=\tr{\frac n2}$,
$\Lambda_{2,1}[f]=\cl{\frac n2}$ all with $f(1)=0$, as approximated
by the fractional part
$\bigl\{\frac{f(2^k+j)+2^k+j}{(2^k+j)^{\log_23}}\bigr\}$ for
$0\le j<2^k$ and $k=1,2,\dots,10$.

A006046$(n)$ is the total number of odd entries in first $n$ rows of
Pascal's triangle. This sequence $f(n)$ equals $S_{2,1}(n)$ (defined
in Eg=0) and has a rich literature with different extensions
and connections; for example, it equals (<ref>) with
$\ga=2$; see below, the OEIS page, the survey papers
[38, 6] and Finch's book <cit.> for more information. By Eg=0, we have
$f(n)=n^{\log_23}P_0(\log_2n)$, where
$P_0\in\mathrm{H}_{\log_23-1}[0,1]$ by Lemma5; see
[20, 25]. Some periodically equivalent
sequences (possibly with a shift) are given as follows.

* A051679: Total number of even entries in the first $n$ rows
of Pascal's triangle, namely, $f(n) = \binom{n+1}2-S_{2,1}(n)$.
Then $f(1) = 0$ and

\begin{equation}\label{E:A051679}
\Lambda_{2,1}[f]=
\tfrac18\,{n}^{2}-
\begin{cases}
\frac n4, & \text{if $n$ is even};\\
\frac18, & \text{if $n$ is odd}.\\
\end{cases}
\end{equation}

* A064406: The accumulation of the number of even entries
(A048967) over the number of odd entries (A001316) in row $n$ of
Pascal's triangle (A007318); in other words,
$\A051679(n)-\A006046(n)$. Thus $f(n) = \binom{n+1}{2} -2S_{2,1}(n)$.
Then $f$ satisfies the same recurrence (<ref>) but with the
different initial condition $f(1) = -1$. The sequence is positive
except for the first 18 terms.

* A074330: $S_{2,1}(n+1)-1$.

* A080978: $f(n) = 2 S_{2,1}(n) + 1$. Then $\Lambda_{2,1}[f]= -2$
with $f(1) = 3$.

* A151788: $f(n) := \frac12\,(3S_{2,1}(n)-1)= \frac32
S_{2,1}(n)-\frac12$ and satisfies $\Lambda_{2,1}[f]=1$ with $f(1) =

* A159912: $f(n)=\sum_{j<n}\lpa{2^{\nu(2j+1)}-1}$ satisfies
$\Lambda_{2,1}[f]=\tr{\frac n2}$ and the relation $f(n) =

* A160720: Number of “ON" cells in a certain $2$-dimensional
cellular automaton: $f(1)=1$ and

\begin{equation}
\Lambda_{2,1}[f]= 2n-2-2\times \mathbf{1}_{n\text{ odd}}.
\end{equation}

One has $f(n) = 4(S_{2,1}(n)-n)+1$.

* A160722: Number of “ON" cells in a certain $2$-dimensional
cellular automaton based on Sierpiński triangles. Then
$\Lambda_{2,1}[f] =2\tr{\frac n2}$ with $f(1)=1$ and $f(n) =

* A171378: $f(n)=n^2-S_{2,1}(n)$. Then
$\Lambda_{2,1}[f]=\cl{\frac n2}^2-\mathbf{1}_{n\text{ odd}}$ with
$f(1) = 0$.

* A193494: Worst case of an unbalanced recursive algorithm over
all $n$-node binary trees; $2A(n-1)+1$ satisfies the max-recursion
(<ref>) with $(\ga,\gb)=(2,1)$. Thus the sequence $f(n) :=
A(n-1)= \frac12(S_{2,1}(n)-1)$ satisfies $\Lambda_{2,1}[f]=1$ with
$f(1)=0$; see Ex-min and PAmax.

* A256256: Number of “ON" cells in a cellular automaton on
triangular grid, which is $6S_{2,1}(n)$ and satisfies the recurrence
$\Lambda_{2,1}[f]=0$ with $f(1)=6$.

* A262867: Total number of “ON" cells in a cellular automaton.
$f(n)=n^2-S_{2,1}(n)+1 =f_{\A171378}(n)+1$, which satisfies
$\Lambda_{2,1}[f] = \cl{\frac n2}^2-2- \mathbf{1}_{n\text{ odd}}$.

* A266532: Number of $Y$-toothpicks in a cellular automaton. We
then get the recurrence $\Lambda_{2,1}[f]=3\tr{\frac n2}-2$ and

* A267610: Accumulated number of “OFF” cells in a cellular
automaton. This is $f(n) = S_{2,1}(n)-2n+1$, and
$\Lambda_{2,1}[f]=2\tr{\frac n2}$ with $f(1)=0$.

* A267700: “Tree" sequence in a $90$ degree sector of some
cellular automaton. (Also the partial sum of A038573.) This sequence
satisfies $\Lambda_{2,1}[f]=\tr{\frac n2}$ with $f(1)=0$, so that
$f(n) = S_{2,1}(n)-n$.

A different example with $(\ga,\gb)=(2,1)$ is the sequence A137294,
which arises in a polynomial-time algorithm for a sowing game; see
<cit.> for more information. It satisfies
$\Lambda_{2,1}[f]=1 + \mathbf{1}_{n\text{ odd}}$ with $f(1)=0$. By
Eodd applied to $f(n)+\frac12$, we have $f(n) =
n^{\log_23}P(\log_2n)-\frac12$. See Figure <ref>.

The periodic functions arising from A006046 and A137294 (see
Ex:pascal), respectively.

§.§ Sequences satisfying $\Lambda_{\alpha,\beta}[f]=g$
with $\alpha+\beta\ge4$

The sequence A268524 satisfies $\Lambda_{1,3}[f]=0$ with $f(1)=1$ and
thus equals our $S_{1,3}(n)$, as listed in Example <ref>.

When $(\alpha,\beta)=(3,1)$, the prototype sequence $S_{3,1}(n)$
corresponds to A130665, which satisfies $\gL_{3,1}[f]=0$ and
$f(1)=1$; see ex4-3. Some variants of this sequence from OEIS,
all having $\Lambda_{1,3}[f]=g$ constant, are given in the following
table; they arise mostly from the combinatorics of the
Ulam–Warburton cellular automaton.

1cOEIS id.
1cOEIS id.
A147562     $(1,1)$      $\frac13(4S_{3,1}(n)-1)$
A151914     $(4,-4)$     $\frac43(2S_{3,1}(n)+1)$

A151917     $(1,-1)$     $\frac13(2S_{3,1}(n)+1)$
A151920     $(0,1)$     $\frac13(S_{3,1}(n)-1)$

A160410     $(4,0)$     $4S_{3,1}(n)$
A160412     $(3,0)$     $3S_{3,1}(n)$

Sequences periodically equivalent to $S_{3,1}(n)$

Three other sequences satisfying $\Lambda_{3,1}[f]=g$ are given

1cOEIS id.
A183060     Cellular automaton     $-n+\begin{cases}
\end{cases}$     $1$     $n^2P(\log_2n)+n-\frac23$

A183126     Toothpick sequence     $-4n+\begin{cases}
\end{cases}$     $7$     $n^2P(\log_2n)+4n-1$

A183148     Toothpick sequence     $-3n+\begin{cases}
\end{cases}$     $4$     $n^2P(\log_2n)+3n-1$

Further sequences with $\Lambda_{3,1}[f]=g$

Although very different in appearance, these sequences are all
periodically equivalent to $S_{3,1}(n)$ because, by
Lemma <ref>, the right-hand side of (<ref>) are
all of the form $\Lambda_{3,1}[f;0,0,0]$ when $(\alpha,\beta)=(3,1)$
and $(c,d,e) = (-1,2,3), (-4,3,7)$ and $(-3,3,6)$, respectively. More
precisely, we have the relations ($f_{\text{A130665}}(n)=S_{3,1}(n)$)

\begin{align}
&= \tfrac23 f_{\text{A130665}}(n)+n-\tfrac23,\\
&= 4 f_{\text{A130665}}(n)+4n-1,\\
&= 2 f_{\text{A130665}}(n)+3n-1.
\end{align}

The sequence A268527 in ex4-3 satisfies $\Lambda_{1,4}[f]=0$
with $f(1)=1$, and thus equals our $S_{1,4}(n)$.

Three other sequences were found with $(\alpha,\beta)=(4,1)$. The
first is A116520 which satisfies $\Lambda_{4,1}[f]=0$ and equals
$S_{4,1}(n)$; see ex4-3. Another sequence A151790 equals
$\frac14(5S_{4,1}(n)-1)$. It satisfies $\Lambda_{4,1}[f]=1$ with
$f(1)=1$; as a check, Lemma <ref> and (<ref>) yield

\begin{align}
= \tfrac54f_{\text{A116520}}(n)-\tfrac14
= \tfrac54 S_{4,1}(n)-\tfrac14.
\end{align}

The last sequence with the pattern $(\alpha,\beta)=(4,1)$ we found is
A273578, which is the total number of “ON" cells in a 2-D cellular
automaton. It satisfies $f(1) = 1$ and

\begin{align}
\Lambda_{4,1}[f]=\begin{cases}
\frac{1}{2}\,{n}^{3}+\frac{n}{2}-4,
& \text{if $n$ is even};\\
\frac{1}{2}\,{n}^{3}+\frac{3}{2}\,{n}^{2}-2\,n-4,
& \text{if $n$ is odd}.\\
\end{cases}
\end{align}

This sequence is also periodically equivalent to
$f_{\text{A116520}}(n)$. To see this, we consider the difference
$\Delta(n) = \frac43n^3-\frac13n+1-f(n)$, which satisfies
$\Lambda_{4,1}[\Delta] = 0$ with $\Delta(1) = 1$; thus
$\gD(n)=S_{4,1}(n)= f_{\text{A116520}}(n)$. From this we deduce the

\begin{align}
f(n) = \tfrac43\,n^3 +n^{\log_25}P(\log_2n)
\end{align}

and the relation

\begin{align}
= \tfrac43\,n^3-\tfrac13n+1-
\end{align}

Two other sequences with $\alpha+\beta=5$ are given in ex4-3:
A268526, which satisfies $\Lambda_{2,3}[f]=0$, and A268525, which
satisfies $\Lambda_{3,2}[f]=0$, both with $f(1)=1$.

Sequences in OEIS of this type have to do either with digital sums or
cellular automata. They include A130667 $(=S_{5,1}(n))$ from

1cOEIS id.
A130667     $(5,1)$     $0$     $1$     $n^{\log_26}P(\log_2n)$

A151781     $(5,1)$     $1$     $1$     $n^{\log_26}P(\log_2n)-\frac15$

A186410     $(5,1)$     $-4\tr{\frac n2}+4$     $1$

A270106     $(4,2)$     $-1$     $1$     $n^{\log_26}P(\log_2n)+\frac15$

A273500     $(4,2)$     $\begin{cases}
\frac13\,{n}^{3}+\frac23\,n-4,\\
\frac13\,{n}^{3}+{n}^{2}-\frac73\,n-4,\\
\end{cases}$     $1$
\frac43n^3+n^{\log_26}P(\log_2n)\\
\hfill\qquad-\frac13n+\frac45
\end{matrix}$

A273562     $(4,2)$     $\begin{cases}
\frac16n^3-\frac23n+1,\\
\frac16n^3+\frac12n^2-\frac{13}6n+\frac32,\\
\end{cases}$
$0$     $\begin{matrix}
\frac23n^3+n^{\log_26}P(\log_2n)\\
\hfill\qquad +\frac13n-\frac15
\end{matrix} $

Sequences with $\gL_{\ga,\gb}[f]=g$ with $\ga+\gb=6$

The sequence $S_{4,2}(n)$ is not in OEIS, but the sequence A270106
(which comes from a cellular automaton) equals the sum (<ref>)
with $(\ga,\gb)=(4,2)$, as follows from the discussion in OEIS of its
increments A189007. Hence, Enu0 shows that

\begin{align}\label{S42}
f_{A270106}(n) = \tfrac45S_{4,2}(n)+\tfrac15.
\end{align}

The six sequences above lead only to two periodically distinct ones
(say, A130667 and A270106) because, by Lemma <ref> and
Lemma <ref>, we have (with

\begin{align}
&= \tfrac65f_{\text{A130667}}(n)-\tfrac15\\
&= \tfrac45 f_{\text{A130667}}(n)+n-\tfrac45,
\end{align}

and, recall also (<ref>),

\begin{align}
&= \tfrac43n^3-\tfrac13n+1-f_{\text{A270106}}(n)\\
&= \tfrac23n^3+\tfrac13n-f_{\text{A270106}}(n),
\end{align}

so that

\begin{align}
= \tfrac23n^3-\tfrac23n+1+f_{\text{A27356}}(n).
\end{align}

For $\ga+\gb\ge7$, we found the following examples with $\gb=1$. (The
ones with $g(n)=0$ and $f(1)=1$ appear also in ex4-3.)

1cOEIS id.
A116522     $(6,1)$     $0$     $1$
$n^{\log_27}P(\log_2n)$     $S_{6,1}(n)$

A151792     $(6,1)$     $1$     $1$

A151793     $(7,1)$     $1$     $1$

A160428     $(7,1)$     $0$     $8$
$n^{3}P(\log_2n)$     $8S_{7,1}(n)$

A161342     $(7,1)$     $0$     $1$
$n^{3}P(\log_2n)$     $S_{7,1}(n)$

A116526     $(8,1)$     $0$     $1$
$n^{\log_29}P(\log_2n)$     $S_{8,1}(n)$

A255764     $(8,1)$     $1$     $1$

A255765     $(9,1)$     $1$     $1$

A116525     $(10,1)$     $0$     $1$
$n^{\log_211}P(\log_2n)$     $S_{10,1}(n)$

A255766     $(10,1)$     $1$     $1$

A116524     $(12,1)$     $0$     $1$
$n^{\log_2 13}P(\log_2n)$     $S_{12,1}(n)$

A116523     $(16,1)$     $0$     $1$
$n^{\log_217}P(\log_2n)$     $S_{16,1}(n)$

Sequences with $\gL_{\ga,\gb}[f]=g$ for $\ga+\gb\ge7$

The only  example we found in OEIS with $\beta\ne1$ is A269589
with $(\ga,\gb)=(3,4)$:

\begin{align}
\Lambda_{3,4}[f]
= -6\cdot 2^{\nu_0(n)}\mathbf{1}_{n\text{ odd}},
\end{align}

with $f(1) =1$; this sequence enumerates the number of triples
$(i,j,k)\in[0,n-1]^3$ such that their bitwise  is zero.
By Eodd, we have $f(n) = n^{\log_27}P(\log_2n)$ for some
periodic function $P$.

§ APPLICATIONS II. $\ALPHA=\BETA$

We group in this section examples satisfying the recurrence
$\Lambda_{\alpha,\alpha}[f]=g$. Since the interpolating function
$\varphi^{}_{\alpha,\alpha}(t) = t$ for every $\ga>0$, this is
similar to the case $\ga=\gb=1$ treated in [27]. In
particular, $\varphi_{\ga,\ga}$ is linear on $\oi$, and therefore we
can derive in many cases a closed-form solution in terms of
elementary functions. In cases when the periodic functions do not
have simple explicit forms, we can often derive explicit Fourier
expansions in terms of known functions such as Riemann's or Hurwitz's
zeta functions. As the situations and analysis are very similar to
the case when $(\alpha,\beta)=(1,1)$, we omit most of the details,
which can be found in [27]. Note, however, one difference
between the cases $\ga>1$ and $\ga=1$: as discussed in Ra=b,
the periodic function $P_0(t)$ in Lemma3 is not continuously
differentiable when $\ga>1$; hence, typically, the periodic function
$P(t)$ in Theorem1 also is not continuously differentiable.

We begin with two examples for a general $\ga$.

Consider the sum $f(n):=\sum_{1\le k<n} \ga^{L_k}$. The case $\ga=2$
is A063915. Since $L_k=\nu(k)+\nu_0(k)-1$ for $k\ge1$, we have by
Enu0 and (<ref>)

\begin{align}\label{eiia}
=\sum_{1\le k<n}\ga^{L_k}
=\frac{1}{\ga}\llpa{\sum_{0\le k<n}
\ga^{\nu(k)+\nu_0(k)}-1}
\end{align}

at least provided $\ga>\frac12$; the result holds indeed for any
$\ga\neq\frac12$ since both sides are polynomials in $\ga$ for fixed
$n$. It follows easily (cf. (<ref>)), that $\gL_{\ga,\ga}[f](n)

A more general pattern that we found in several OEIS sequences (all
with $\ga=\gb=2$; see Table <ref> below) is of the form in
Lemma <ref>, i.e.,

\begin{align}\label{maj2}
\Lambda_{\ga,\ga}[f]= g(n) = c n+ \begin{cases}
d,&\text{ if $n$ is even}; \\
e,&\text{ if $n$ is odd}.
\end{cases}
\end{align}

Assume for simplicity $\ga>1$, so lmm-g-linear applies. Then
(<ref>) yields the solution

\begin{equation}
f(n) = n^\rho P(\log_2n)-\frac{cn}{\alpha-1}
\end{equation}

Furthermore, it follows, from the proof of lmm-g-linear,
that the Fourier coefficients of the periodic function $P$ are given
by (assuming first $\ga>2$ so that $\rho>2$),

\begin{align}\label{maj3}
\hP(k)
\biggl(\frac{(2\ga-1)(\ga-1)}{\ga}\bar{f}(1)\notag\\
&\hskip4em +
(e-d)\sum_{j\ge1} \Bigpar{(2j)^{-(\rchi_k-1)}-2(2j+1)^{
&=\frac{(2\ga-1)(\ga-1)f(1) + (2\ga-1)(c+e) -\ga d
+2(e-d)(2-\ga)\zeta(\richi_k)}{\ga(\rchi_k)(\richi_k)\log 2}.
\end{align}

By analytic continuation (temporarily allowing complex $\ga$ and
$\rho$), (<ref>) holds for all $\ga$ with $\ga>1$ (so $\rho>1$),
but we have to be careful when $\ga=2$ and thus $\rho=2$, since then
$\zeta$ has a pole at $\richi_0=1$, and we have to interpret (by
continuity) $(2-\ga)\zeta(\richi_0)=-2\log 2$. The formula simplifies
when $\ga=2$, since then all other terms with $\zeta$ disappears. See
further E52, where an explicit formula for $P(t)$ is given for

From a generating function viewpoint, the fact that $\alpha=2$ is
special may be due to the identity

\begin{equation}
\sum_{k\ge0}\frac{\alpha^k z^{2^k}}
{1+z^{2^k}} = \frac{z}{1-z}
\eqtext{iff}\alpha=2.
\end{equation}

§.§ $(\alpha,\beta)=(1,1)$

[Sequences not in [27]]
As this case has already been discussed in detail in
[27], we only list sequences (together with their
closed-form expressions) that are not included in [27].
We use the pattern $f(n) = nP(\log_2n)-Q(n)$. (Some recursions start
at some $n>2$.)

OEIS     $g(n)$     Initials
$P(t)$     $-Q(n)$

– Continued from previous page

OEIS     $g(n)$     Initials
$P(t)$     $-Q(n)$

5rContinued on next page

(binary trees)
$ 1 $     $ \begin{array}{l}
\{f(j)\}_{2\le j\le 3} \\

(binary trees)     $ 1 $
$ \begin{array}{l}
\{f(j)\}_{2\le j\le 3} \\
1-2^{-1-\{t\}}\\ 2^{-\{t\}}\end{array}\right\}$

(recursion)     $ 2 $     $\begin{array}{l}
\{f(j)\}_{1\le j\le 2} \\
2-2^{-1-\{t\}}\\ 1+2^{-\{t\}}\end{array}\right\}$

(binary length)     $ n $     $ f(1) = -1 $
$1-\{t\}-2^{1-\{t\}}$     $n\log_2n$

(binary trees)     $\mathbf{1}_{n\text{ odd}}$
$ f(1) = 0 $     see below     $0$

(digital sum)     $ n-2 $     $ f(1) = 1 $
$1-\{t\}-2^{1-\{t\}}$     $n\log_2n+2$

$ 0 $     $\begin{array}{l}
\{f(j)\}_{4\le j\le 7} \\   %a(n+1)
\end{array}$
4-3\cdot 2^{-2-\{t\}}\\
3+3\cdot 2^{-2-\{t\}}\\
2+5\cdot 2^{-1-\{t\}}
\end{array}\right\}$     $0$

(digital sum)
$2-\mathbf{1}_{n\text{ odd}}$
$ f(1) = -1 $     see below     $-2$

$\mathbf{1}_{n\equiv 3\bmod 4}$     $ f(1) = 0 $
see below     $0$

\frac{1}{2}{n}^{2}-2n\\
\frac{1}{2}
\end{cases}
\end{array}$     $ f(1) = 3 $
$-1+2\{t\}+2^{2-\{t\}}$     $\begin{array}{l}
-1 \end{array}$

Some sequences with $\gL_{1,1}[f]=g$

In particular, the sequence A297531 gives the maximum possible
subword complexity over all binary overlap-free words of a given
length, A301336 counts the difference between the total number of
$1$s and the total number of $0$s in the binary expansions of
$\{0,\dots,n-1\}$, and A303548 equals the sum of the distances from
$n$ to the nearest number with a given Hamming weight.

Note that some of these sequences are discussed in [27]
and were subsequently added to OEIS:

OEIS     A294456
Example in [27]     3.2

Here $\A295513(n)= \A001855(n)-1$, $\A296349(n)=\A083652(n-1)$, and

\begin{align}
f_{\text{A296349}}(n) = f_{\text{A295513}}(n)+2,
\quad
f_{\text{A301336}}(n) =n-2-f_{\text{A296062}}(n).
\end{align}

On the other hand, with $\chi_{k}:=\frac{2k\pi i}{\log 2}$ as above,
using <cit.>,

\begin{align}\label{E:A296062-P}
&= 2-\log_2\pi+\frac1{\log2}
\sum_{k\ne0}\frac{1+2\zeta(\chi_k)}{\chi_k(1+\chi_k)}
\, e^{2k\pi i t}\\
&= 1-P_{\text{A296062}}(t) \\
P_{\text{A303548}}(t) \label{A303548}
&= \tfrac12\log_2\pi-2\log_2\Gamma\lpa{\tfrac34}
\sum_{k\ne0}\frac{\zeta(\chi_k)-2\zeta(\chi_k,\frac34)}
{\chi_k(1+\chi_k)}\, e^{2k\pi i t}.
\end{align}

Finally, the sequence A330038, satisfying $\Lambda_{1,1}[f]=\tr{\frac
n2}$ with $f(1)=1$, is nothing but A000788 (best case of mergesort or
partial sum of $\nu(n)$) plus $n$; see <cit.>.

§.§ $(\alpha,\beta)=(2,2)$

While most analysis here parallels that in [27], we will
see that there are subtle differences in the genesis of periodic
oscillations. In particular, as remarked above, the periodic function
$P(t)$ is generally not continuously differentiable.

[Periodic functions differentiable except at integers]

Consider the simple case when $\Lambda_{2,2}[f]=c$ for $n\ge2$.
Then, by lmm-g-const, Eg=0 and (<ref>) (or directly
by (<ref>) and (<ref>)), we deduce that

\begin{align}
= \lpa{f(1)+\tfrac13\,c}2^{L_n}\lpa{3n-2^{L_n+1}}
\end{align}

so that $f(n) = n^2P(\log_2n)-\frac13c$, where

\begin{equation}
P(t) =  \lpa{f(1)+\tfrac13\,c}P_0(t)
= \lpa{f(1)+\tfrac13\,c} 2^{-\{t\}}(3-2^{1-\{t\}}),
\end{equation}

is continuously differentiable on $\oi$, but not at integer $t$,
where the derivative $P'(t)$ has a jump.

A more general pattern that we identified from the OEIS sequences
is of the form (see Lemma <ref> and EIIb)

\begin{align}\label{L22-linear}
\Lambda_{2,2}[f]= g(n) = c n+ \begin{cases}
d,&\text{ if $n$ is even}; \\
e,&\text{ if $n$ is odd}.
\end{cases}
\end{align}

Then the solution is given by $f(n) = n^2P(\log_2n)-cn-\frac13\,d$
for $n\ge1$, where

\begin{equation}\label{maj4}
P(t) = d-e+\lpa{f(1)+c-\tfrac23\,d+e}
\end{equation}

which easily is verified using lmm-g-linear,
(<ref>)–(<ref>), and the special case

This can be compared with the recursion $\Lambda_{\alpha,\alpha}[f] =
g(n)$ for a general $\ga$ (with the same $g(n)$) studied in
EIIb, where it is readily checked that the Fourier
coefficients (<ref>) (with $\ga=2$) agree with (<ref>) and

The prototype sequence in this category is A073121:

\begin{equation}
\end{equation}

where $P_{\text{A073121}}(t)=P_0(t):=2^{-\{t\}}\lpa{3-2^{1-\{t\}}}$,
which arises as an upper bound for the cardinality of some regular
expressions; see [14] for the more general form
$\Lambda_{\alpha,\alpha}[f]=0$. The Fourier coefficients of $P_0(t)$
are, by (<ref>), of the form

\begin{align}\label{hp022}
\hP_0(k)=\frac{3}{2\log 2\cdot(1+\chi_k)(2+\chi_k)}.
\end{align}

With $S_{2,2}(n)$, the solution to (<ref>) can
alternatively be written as

\begin{equation}
= (d-e)n^2+\lpa{f(1)+c-\tfrac23\,d+e}S_{2,2}(n)
\end{equation}

Table <ref> gives more examples from OEIS that are
periodically equivalent to $S_{2,2}(n)$.

1cOEIS id.
A063915     [l]$\sum_{1\le k<n}2^{L_k}$
$1$     $0$     $\frac13(S_{2,2}(n)-1)$

A073121     [l]Regular
$0$     $1$     $S_{2,2}(n)$

A181497     [l]Combinatorial
$-1$     $1$     $\frac13(2S_{2,2}(n)+1)$

A236305     [l]Nim
game     $\begin{cases}
0 \\ -3
\end{cases}$     $1$

A255748     [l]Cellular
-\frac12n+2 \\ -\frac12n+\frac52
\end{cases}$     $0$

A256249     [l]Josephus
1 \\ 0
\end{cases}$     $0$

A256250     [l]Cellular
1 \\ -3
\end{cases}$     $1$

A256266     [l]Cellular
-3n+12 \\ -3n+15
\end{cases}$     $0$

A256534     [l]Cellular
0 \\ -12
\end{cases}$     $4$

A261692     [l]Cellular
1 \\ 2
\end{cases}$     $0$

A262620     [l]Cellular
1 \\ 5
\end{cases}$     $1$

A266538     [l]Josephus
2 \\ 0
\end{cases}$     $0$
Sequences satisfying $\Lambda_{2,2}[f]=g$ and their
relations to $S_{2,2}(n)$ (E52).

[Piecewise differentiable periodic functions]

When the recurrence $\Lambda_{2,2}[f]=g$ is satisfied only for $n\ge
n_0>1$, the resulting periodic function is specified according to the
initial conditions $f(n)$ with $n\le n_0$. For simplicity, we
consider the sequence A080075 (Proth numbers), which denotes the
numbers of the form $(2r+1)2^k+1$ for $k\ge1$ and $2r+1<2^k$ and has
many variants. The sequence $f(n)=\text{A080075}(n-1)$ then satisfies
$\Lambda_{2,2}[f]=-3$ with the initial conditions $f(2)=3$ and
$f(3)=5$. The solution is then given by $f(n) = n^2P(\log_2n)+1$ for
$n\ge2$ with

\begin{equation}
P(t) = \begin{cases}
&\text{if }t\in[0,\log_2\frac32];\\
&\text{if }t\in[\log_2\frac32,1];
\end{cases}
\end{equation}

see <cit.> for similar behaviour.

1cOEIS id.
A080075     $-3$     $(3,5)$

A082662     $0$     $(1,2)$     $\frac12(f_{\text{A080075}}(n)-1)$

A112714     $3$     $(1,3)$     $f_{\text{A080075}}(n)-2$

A116882     $0$     $(2,4)$     $f_{\text{A080075}}(n)-1$

A260711     $0$     $(8,16)$     $4(f_{\text{A080075}}(n)-1) $

[Non-differentiable periodic functions]
A few sequences defined as the partial sum of the bitwise operator
between $j$ and $n-j$ or their complements satisfy
$\Lambda_{2,2}[f]=g$ with different $g$; see tb-22-ns for a
summary; in all cases $f(1)=0$. Note that the  operator
$\bar{j}$ uses the full number of bits $L_n+1$ for each $0\le j<n$
and equals

\begin{equation}
(\underbrace{1\dots 1}_{L_n-s}
\text{ if }j=(1b_{s-1}\cdots b_0)_2.
\end{equation}

1cOEIS id.
A006581     $\sum\limits_{1\le j\le n-2}
\bigl(j \textsf{ AND } (n-1-j) \bigr)$
\frac {n-1}2
\end{cases}$     $n^2P(\log_2n)$

A006582     $\sum\limits_{1\le j\le n-2}
\bigl(j \textsf{ XOR } (n-1-j) \bigr)$
\end{cases}$     $n^2P(\log_2n)-3n+2$

A006583     $\sum\limits_{1\le j\le n-2}
\bigl(j \textsf{ OR } (n-1-j) \bigr)$
3n-6 \\
\frac 52n-\frac{13}2
\end{cases}$     $n^2P(\log_2n)-3n+2$

A090889     $\sum\limits_{1\le j<n} jv_2(j)(n-j)$
\frac1{12}\,{n}^{3}-\frac 13\,n\\
\frac1{12}\,{n}^{3}-\frac1{12}\,n
\end{cases}$     $\frac16n^3+n^2P(\log_2n)+\frac n3$

A099027     $\sum\limits_{0\le j<n}
\bigl(\bar{j}\textsf{ AND } (n-1-j) \bigr)$
\frac{n}{2} \\
\end{cases}$     $n^2P(\log_2n)-\frac n2$
Sequences satisfying $\Lambda_{2,2}[f]=g$ with
non-smooth periodic functions (E22-ns).

Here $v_2(n)$ denotes the dyadic valuation of $n$ (exponent of the
highest power of $2$ dividing $n$). Note that the recurrence
provided on OEIS for A090889 is incorrect (and the generating
function misses a factor of $2$).

These apparently different sequences are all periodically
equivalent. Indeed, by the recurrences and induction, we can prove
the relations

\begin{equation}
\begin{split}
&= (n-1)(n-2)-2f_{\text{A006581}}(n) \\
&= (n-1)(n-2)-f_{\text{A006581}}(n) \\
&= \tfrac16n(n-1)(n-2)+f_{\text{A006581}}(n)\\
&= \tfrac12n(n-1)-f_{\text{A006581}}(n).
\end{split}
\end{equation}

The Fourier expansion of $P_{\text{A006581}}(t)$ is, by (<ref>)
and standard calculations, given by

\begin{equation}\label{E:P-A006581}
= \frac12-\frac1{4\log 2}
+\frac1{\log 2}\sum_{k\ne0}
\frac{\zeta(\chi_k)}{(1+\chi_k)(2+\chi_k)}
\, e^{2k\pi i t}.
\end{equation}

We prove in Appendix <ref> that the continuous function
$P_{\textrm{A006581}}$ is nowhere differentiable, and that it is not

Another sequence $\A048641$ is defined as the sum
$\sum_{k<n}\gamma(k)$, where $\gamma(k)= k\textsf{ XOR
}\tr{\frac12k}$ denotes the numerical value of the binary reflected
Gray code of $k$ (A003188), and satisfies the recurrence
$\Lambda_{2,2}[f]= \frac12\lpa{n-\sin\frac12n\pi}$ with $f(1)=0$. We
then obtain $f(n) = n^2P(\log_2n)-\frac12n$ with

\begin{align}\label{E:A048641}
= \frac{\pi}{8\log 2}+ \frac1{4\log 2}
\sum_{k\ne0}\frac{\zeta\lpa{1+\chi_k,\frac14}
{(1+\chi_k)(2+\chi_k)}\, e^{2k\pi i t}.
\end{align}

We leave the question whether this function is nowhere differentiable
as an open problem.

Yet another related example is A022560; this is the sum $f(n) :=
\sum\limits_{1\le k<n}2^{v_2(k)}(n-k)$, which satisfies the
recurrence $\Lambda_{2,2}[f]= \tr{\frac14n^2}$. (Note that one of the
recursions given in OEIS is incorrect.) In this case $g(n)$ grows too
rapidly for Theorem1 to be directly applicable, since the
series (<ref>) diverges. A modification of our arguments, see
EB for details, shows that we have

\begin{align}\label{f022560}
\end{align}

with a logarithmic factor in the leading term, and periodic
fluctuations given by

\begin{equation}\label{P022560}
= \frac38+\frac{2\gamma-3}{8\log 2}
+ \frac1{2\log 2}
\sum_{k\ne0}\frac{\zeta\lpa{1+\chi_k}}
{(1+\chi_k)(2+\chi_k)}\, e^{2k\pi i t}.
\end{equation}

See Figure <ref>.

A006581     A048641     A022560

Fluctuations (properly normalised) in the three periodically
distinct cases in E22-ns. At least the first is nowhere

[Sensitivity test: small variations inducing big
differences]  While the previous examples show that many
different toll functions lead to periodically equivalent
oscillations, the same recurrence also exhibits the opposite
sensitivity property, as we now examine. We begin with the difference
$f(n) = f_{\text{A048641}}(n)-\binom{n}2$, which gives A048644 and
satisfies the recurrence $\Lambda_{2,2}[f]= \mathbf{1}_{n \bmod
4\equiv 3}$ with the solution $f(n) = n^2P(\log_2n)$, where
$P(t)=P_{\A048641}(t)-\frac12$ is given by (<ref>) below.

It is interesting to see that changing $3$ to other remainders
results in drastically different periodic functions; compare also
<cit.>. Let $\Lambda_{2,2}[f_j] =\mathbf{1}_{n
\bmod 4\equiv j}$ for $j=0,1,2,3$ with $f_j(1)=0$. Then

\begin{align}
f_j(n) = \begin{cases}
n^2P_0(\log_2n) -\frac13
\mathbf{1}_{n \text{ odd}}, &
\text{ if }j=0,\\
n^2P_j(\log_2n) , &
\text{ if }j=1,3,\\
\mathbf{1}_{n \text{ odd}}, &
\text{ if }j=2,\\
\end{cases}
\end{align}

where $P_0(t)$ is continuously differentiable on $\oi$ (not the same
as $P_0(t)$ from Section <ref>), $P_2(t)=\frac14$ is
a constant, and $P_1(t)$ has many visible cusps in the unit
interval (see Figure <ref>). More explicit
expressions are given by

\begin{align}
P_0(t) &= \tfrac34-2^{1-\{t\}}+\tfrac134^{1-\{t\}}, \\
P_1(t) &= \frac{3}{4\log 2}
-\frac{\pi}{8\log 2}-\frac12
-\frac1{4\log 2}\sum_{k\ne0}
\frac{\zeta(1+\chi_k,\frac14)-\zeta(1+\chi_k,\frac34)-6}
{(1+\chi_k)(2+\chi_k)}\, e^{2k\pi i t},\\
P_2(t) &=\frac14,\\
P_3(t) &
= \frac{\pi}{8\log 2}-\frac12+ \frac1{4\log 2}
\sum_{k\ne0}\frac{\zeta\lpa{1+\chi_k,\frac14}
{(1+\chi_k)(2+\chi_k)}\, e^{2k\pi i t}; \label{A048644}
\end{align}

see Figure <ref> for an illustration. The difference
$\zeta(s,\frac14)-\zeta(s,\frac34)$ is also known as the Dirichlet
beta function; it appears also in several other formulas above and
below. Note that $f_2(n) = \ltr{\frac14n^2}$, which equals the
quarter-squares A002620, and the sum $f_1+f_2+f_3+f_4$ equals A063915
in EIIa and tb-22-1. Also the mean values of these
periodic functions are given by

\begin{align}
\lpa{-\tfrac1{2\log 2}+\tfrac34,
\tfrac{3}{4\log 2}-\tfrac{\pi}{8\log 2}-\tfrac12,
\tfrac14,
\tfrac{\pi}{8\log 2}-\tfrac12}
\approx\lpa{0.02865, 0.01548, 0.25, 0.06655},
\end{align}

respectively, and we see that the mean value of $P_2$ is much larger
than those of other three.

Similarly, by comparing with tb-22-1, the sequence A256249
for a sum for the Josephus problem has $f_{\A256249}=f_0+f_2$. The
sequence A266540 for another sum in the Josephus problem has $f(1)=0$
and $\Lambda_{2,2}[f]=1+\cos\lpa{\frac12n\pi}$ (which has the
periodic pattern $(2,1,0,1)$ for $n\ge0$); hence
$f_{\A266540}=2f_0+f_1+f_3$. It is written on the OEIS page that “It
appears that this sequence has a fractal (or like-fractal)
behaviour.” This is untrue because from the generating function given

\begin{equation}
\sum_{n\ge1}f(n) z^n
= \frac{z^3(1+z^2)}{(1-z^2)(1-z)^2}
\end{equation}

or from our approach, we can derive the identity
$f(n) = n^2P(\log_2n)-\frac23+\frac12\mathbf{1}_{n\text{ is odd}}$
with $P(t) = \frac12-2^{-\para{t}}+\frac234^{-\para{t}}$.

Changing the recurrence to
$\Lambda_{2,2}[f] =1-\cos\lpa{\frac12n\pi}$ does not alter the
smooth nature of the periodic function because $f(n) =
n^2P(\log_2n)-\frac12\mathbf{1}_{n\text{ is odd}}$, where $P(t) =
-\frac12+3\cdot 2^{-t}-2\cdot 4^{-t}$. However, switching cosine
function to sine function does change the nature of the periodic
oscillation because we then have the solution $f(n) =
n^2P(\log_2n)-\tfrac13$ when (i)
$g(n)=1+\sin\lpa{\frac12n\pi}$, where

\begin{equation}
P(t) = \frac1{\log 2}-\frac{\pi}{4\log 2}
-\frac1{2\log 2}\sum_{k\ne0}
\frac{\zeta\lpa{1+\chi_k,\frac14}
\, e^{2k\pi i t},
\end{equation}

and (ii) $g(n)=1-\sin\lpa{\frac12n\pi}$, where

\begin{equation}
P(t) = \frac{\pi}{4\log 2}-\frac1{2\log 2}
+\frac1{2\log 2}\sum_{k\ne0}
\frac{\zeta\lpa{1+\chi_k,\frac14}
\, e^{2k\pi i t}.
\end{equation}

$g(n)=\mathbf{1}_{n\bmod 4\equiv 0}$
$g(n)=\mathbf{1}_{n\bmod 4\equiv 1}$
$g(n)=\mathbf{1}_{n\bmod 4\equiv 2}$
$g(n)=\mathbf{1}_{n\bmod 4\equiv 3}$

Sensitive dependence of the periodic functions on $g(n)$.

Consider finally the partial sum of A229762:

\begin{equation}
:= \sum_{0\le k<n}
\lpa{\lpa{k \;\textsf{XOR}\; \tr{\tfrac k2}}\;
\textsf{AND}\;\tr{\tfrac k2}}.
\end{equation}

Then $\Lambda_{2,2}[f]= \tr{\frac{n+1}4}$. Let $\bar{f}(n) :=
f(n)+\frac n4-\frac18\mathbf{1}_{n\text{ odd}}$. Then $\bar{f}(1) =
\frac18$ and for $n\ge2$

\begin{equation}
\Lambda_{2,2}[\bar{f}]
=\frac{((n\bmod 4)-1)^2-1}8
-\frac18, &\text{if }n \bmod 4 \equiv 1,\\
\frac38, &\text{if }n \bmod 4 \equiv 3,\\
0, &\text{otherwise}.
\end{cases}
\end{equation}

We then deduce that $f(n) = n^2P(\log_2n) -\frac n4
+\frac18{\mathbf{1}_{n\text{ odd}}}$, where we have, using
(<ref>) again, $P(t) = \frac12P_3(t)+\frac18$
with $P_3(t)$ given in (<ref>).

Similarly, the partial sum of the sequence A229763 satisfies
$\Lambda_{2,2}[f]= \frac12(1-(-1)^{\tr{\frac12n}})$ and can be dealt
with by the same procedure.

§.§ $(\alpha,\beta)=(4,4)$

Similarly to the $(2,2)$ case, sequences in OEIS of this category
include digital sums connected to 2-D arrays and double sums
involving bitwise logic operators. Note that a degenerate case occurs
when $f(1)=0$ and $g(n) = 3n$ when $n$ is even and $g(n)=0$
otherwise; in this case, $f(n) = n^3-n$.

[Different sequences, same periodic
We consider the following eight OEIS sequences in which the first
four have $g(n)$ involving $\sin\frac12 n\pi$ (of period $4$) while
the last four have $g(n)$ depending simply on the parity of $n$.

1cOEIS id.

A163242     2-D Gray code
$0$     $n^3P(\log_2n)-\frac12n$

A163365     Hilbert curve
[l]$\frac12\lpa{3+\cos n\pi}n$

$0$     $n^3P(\log_2n)-\frac23n$

A163477     Hilbert curve
[l]$\frac18\lpa{3+\cos n\pi}n$

$0$     $n^3P(\log_2n)-\frac16n$

A163478     2-D Gray code
$0$     $n^3P(\log_2n)-\frac16n$

A224923     $\sum\limits_{1\le i,j<n}(i\textsf{ XOR }j)$
$0$     $n^{3}P(\log_2n)-\frac12n^2$

A224924     $\sum\limits_{1\le i,j<n}(i\textsf{ AND }j)$
\frac14\,{n}^{2}\\
\frac14(n-1)(n-5)
\end{cases}$
$0$     $n^3P(\log_2n)-\frac14n^2$

A241522     game of Nim
\end{cases}$     $1$     $n^3P(\log_2n)$

A258438     $\sum\limits_{1\le i,j<n}(i\textsf{ OR }j)$
\frac14n(7n-12)\\
\frac14(n-1)(7n-11)
\end{cases}$
$0$     $n^3P(\log_2n)-\frac74n^2+n$

Sequences satisfying $\Lambda_{4,4}[f]=g$

While it is visible that
$f_{\text{A163242}}(n)=3f_{\text{A163478}}(n)$ and
$f_{\text{A163365}}(n)=4f_{\text{A163477}}(n)$, it is less
transparent but can be proved by induction that

\begin{equation}
\begin{split}
&= \tfrac1{12}n(n^2-1)+\tfrac16f_{\text{A163242}}(n)\\
&= \tfrac12n^2(n-1)-\tfrac12f_{\text{A224923}}(n)\\
&= n^2(2n-1)-2f_{\text{A224923}}(n)\\
\end{split}
\end{equation}

implying that these eight sequences lead indeed to only two
periodically different ones: the first four and the last four.

Also the Fourier expansions are given by

\begin{align}\label{A163242}
&= \frac{\zeta\lpa{2,\frac14}-
\zeta\lpa{2,\frac34}}{32\log 2}
+\frac{3}{16\log 2}\sum_{k\ne0}
\frac{\zeta\lpa{2+\chi_k,\frac14}-
\zeta\lpa{2+\chi_k,\frac34)}}
\,e^{2k\pi i t}\\
&= \frac{\pi^2}{24\log 2}
+\frac{3}{2\log 2}\sum_{k\ne0}
\frac{\zeta(2+\chi_k)}{(2+\chi_k)(3+\chi_k)}
\,e^{2k\pi i t},
\end{align}

respectively. The two series are absolutely convergent.

A163242     A224923     A067894

The periodic functions in the two representative $(4,4)$
cases (E44) and A067894 (A067894) as approximated by
$n^{-\rho}(f(n)+Q(n))$ for $n=2^k+j$ with $k=0,1,\dots$ and $0\le
j\le 2^k$.

§.§ $(\alpha,\beta)=(10,10)$

Write $0, \dots, n-1$ in binary and add as if they were decimal
numbers. Then $f(1) = 0$ and

\begin{equation}\label{no0}
\Lambda_{10,10}[f] = \tr{\tfrac n2}.
\end{equation}

The solution is

\begin{equation}
f(n) = n^{\log_2(20)}P(\log_2n)-\tfrac1{18}n,
\end{equation}

In particular, we can derive the Fourier series expansion (as in
our previous paper) for $P_{\text{A067894}}(t)$:

\begin{equation}
= \frac4{5\log 2}\sum_{k\in\mathbb{Z}}
\frac{\zeta(\rho-1+\chi_k)}{(\rho-1+\chi_k)(\rho+\chi_k)}
\, e^{2k\pi i t},
\end{equation}

where $\rho=\log_220$.

An extension by replacing $10$ by other values is discussed in

§.§ Partial sums of $\Lambda_{\alpha,0}[f]=g$

One simple way to generate sequences satisfying
$\Lambda_{\alpha,\alpha}[f]=g$ with $\alpha=\beta$ is to consider the
partial sum $f(n) := \sum_{1\le k<n}h(k)$, where
$\Lambda_{\alpha,0}[h]=\xi$; then

\begin{equation}\label{erik}
\Lambda_{\alpha,\alpha}[f]
= h(1)+\sum_{2\le k<n}\xi(k),
\end{equation}

for $n\ge2$. Such a sum (after normalising by $n$) gives the average
order and more smooth asymptotics than the original sequence (which
leads almost always to functions with discontinuities; see
Salphabeta=0 and [27] for more details). For
example, the partial sum of the sequence A006520 (satisfying
$\Lambda_{2,0}[h]=\lcl{\frac12n}$) gives A022560 discussed in
E22-ns with $g(n)=\ltr{\frac14n^2}$.

In a similar manner, if we define $f(n) := \sum_{1\le k\le n}
h(k)$, where $\Lambda_{0,\beta}[h]=\xi$; then

\begin{equation}\label{er2}
\Lambda_{\beta,\beta}[f]
= (1-\beta)h(1)+\sum_{2\le k\le n}\xi(k),
\end{equation}

for $n\ge2$. Note that the equations $\Lambda_{\alpha,0}[h]=\xi$ and
$\Lambda_{0,\alpha}[h]=\xi$ are equivalent up to a shift of both $h$
and $\xi$; thus it suffices to consider only one of them.

The number of such sequences on OEIS exceeds several hundred after
removing sequences whose generating functions are rational (with all
singularities on the unit circle). So far we discussed only OEIS
sequences leading to $(1,1)$, $(2,2)$, $(4,4)$ and $(10,10)$, but in
such partial sum constructions, sequences with different values of
$\alpha$ are frequently found; see tb-EMoser.

[Partial sum of Moser-de Bruijn sequences:  $\alpha\ge0$]

The Moser-de Bruijn sequence A000695 consists of the integers whose
digits in base 4 are in $\para{0,1}$; equivalently, $\A000695(n)$ is
obtained by reading the binary representation of $n$ in base 4. This
sequence $h(n)$ satisfies $\Lambda_{4,0}[h]=\mathbf{1}_{n\text{
odd}}$. Hence, (<ref>) shows that the partial sum
$f(n):=\sum_{k<n} h(n)$ satisfies

\begin{equation}\label{er3}
\Lambda_{4,4}[f](n) = \tr{\tfrac n2},
\qquad n\ge2.
\end{equation}

We can here replace 4 by any base $\ga>1$ (possibly non-integer);
more generally,  we can take any real $\ga$ and define, for any
integer $n=\sum_{j\ge0}b_j 2^j$ with $b_j\in\para{0,1}$,

\begin{align}\label{moser}
h\Bigpar{\sum_{j\ge0}b_j 2^j}:=\sum_{j\ge0}b_j\ga^j.
\end{align}

(One might also take complex $\ga$, but we leave that case to the
adventurous reader.) We then have the generating function

\begin{equation}
\sum_{n\ge1}h(n)z^{n}
= \frac1{1-z}\sum_{k\ge0}\frac{\ga^k z^{2^k}}
\end{equation}

tb-EMoser lists many of such “$\ga$-Moser-de Bruijn
sequences” that we found on OEIS. Note that $\ga=1$ gives
$\A000120(n)= \nu(n)$, the number of $1$s in the binary expansion of
$n$ (see Enu and (<ref>)), and that $\ga=2$ gives the
trivial case $\A000027(n)=n$.

Taking partial sums as above gives us a sequence $f(n):=\sum_{k<n}
h(n)$ with

\begin{equation}\label{er4}
\Lambda_{\ga,\ga}[f](n)
= \tr{\tfrac n2}, \qquad n\ge2.
\end{equation}

The resulting sequence $f$ is found in OEIS in the cases $\alpha=1$,
$2$, $10$, and $-1$, which give A000788, A000217 ($\binom{n}2$),
A067894 (Example <ref>), and A005536 <cit.>, respectively.

$\alpha$     $1$     $2$     $3$     $4$     $5$     $6$
OEIS     A000120     A000027     A005836     A000695     A033042     A033043

$\alpha$     $7$     $8$     $9$     $10$     $11$     $12$
OEIS     A033044     A033045     A033046     A007088     A033047    A033048

$\alpha$      $13$     $14$     $15$     $16$     $17$     $18$
OEIS      A033049     A033050     A033051     A033052     A197351     A197352

$\alpha$      $19$     $20$     $64$     $100$     $-1$     $-2$
OEIS      A197353     A063012     A135124     A063010     A065359     A053985

$\ga$-Moser-de Bruijn sequences in OEIS (EMoser).

For any $\ga>1$, we have, by (<ref>), (<ref>) and

\begin{align}\label{er5}
= n^{1+\log_2 \ga}P(\log_2n)-\frac{n}{2(\ga-1)}.
\end{align}

The same result holds for $\frac12<\ga<1$ by considering
$f_1(n):=f(n)+\frac{1}{2(\ga-1)}n$, which satisfies
$\gL_{\ga,\ga}[f_1](n)=g_1(n):=-\{\frac n2\}$.

If $0<\ga\le\frac12$, then $\rho\le0$, and even if we consider
$f_1(n)$ as above, the sum (<ref>) does not converge uniformly
since the individual terms do not converge uniformly to 0. Hence,
Theorem1 shows that (<ref>) cannot hold with a continuous
$P(t)$. In fact, if $s(x)$ is the sawtooth function that is defined
by $s(n):=\Iodd$ for $n\in\bbZ$, with linear interpolation between
the integers, then $g(x)=\frac12x-\frac12s(x)$ for all $x\ge0$, and
thus (<ref>) implies that, in view of $f(1)=0$,

\begin{align}\label{nn1}
= \frac{x}{2(1-\ga)}
-\frac12\sum_{k\ge0} (2\ga)^k s(2^{-k}x),
\qquad x\ge0.
\end{align}

(This actually holds as soon as $|\ga|<1$.) If $0<\ga<\frac12$, then
the sum in (<ref>) converges uniformly for all $x\ge0$ to a
bounded continuous function on $[0,\infty)$. Note that this function
is dominated by the first few terms in the sum, which are periodic
with small periods $(2,4,\dots)$. Hence $f(n)-\frac{n}{2(1-\ga)}$ can
be approximated arbitrarily well by a periodic function, without any
scaling; such behaviour is very different from the case $\ga>\frac12$
when we instead have a periodic function of $\log_2n$, scaled by
$n^\rho$; see also Rfast.

If $\ga=\frac12$, the sum in (<ref>) is $O(\log x)$ (for
$x\ge2$), but again, there is no smooth asymptotic behaviour. For
example, with $f_1(n):=f(n)-n$, we have
$f_1(\frac13(2^{2\ell}-2^{2k})) =-\frac23(\ell-k)+O(1)$ for $0\le
k<\ell$; taking $0\le k\le \frac12 \ell$, say, shows a rather large
variation on a relatively small interval of length $O(n\qq)$. Note
also $f_1(2^k)=-1$ for all $k\ge0$.

The case $\ga=0$ is trivial, with $f(n)=g(n)=\floor{\frac{n}2}$. The
case $\ga<0$ will be discussed in EMoser-.

Fourier expansion.
We have, by (<ref>) with $g(n) = \floor{\frac n2}$,
when $\Re s$ is large enough,

\begin{align}\label{per1}
\end{align}

It follows by ChPa=b that if $\ga>\frac12$ with
$\alpha\ne1,2$, then the periodic function $P(t)$ in (<ref>) has
the Fourier expansion

\begin{equation}\label{per2}
= \frac{\alpha-2}{\alpha\log 2}
\sum_{k\in\mathbb{Z}}
\frac{\zeta(\rho-1+\chi_k)}
{(\rho-1+\chi_k)(\rho+\chi_k)}\,e^{2k\pi i t}.
\end{equation}

Alternatively, by (<ref>), $f(1)=0$, (<ref>) and
(<ref>), we derive the Mellin transform of $f(x)$:

\begin{align}\label{per3}
\qquad \Re s<\min(-1, -\rho).
\end{align}

This extends to all real $\ga$, with $\rho:=\log(2|\ga|)$ as in
EMoser- when $\ga\le0$. Hence, Mellin inversion yields (after
a change of variable) the integral formula

\begin{equation}\label{per4}
f(n) = \frac1{2\pi i}
\int_{\gs-i\infty}^{\gs+i\infty}
\frac{(1-2^{1-s})\zeta(s)n^{s+1}}
{s(s+1)(1-\alpha 2^{-s})}\dd s,
\end{equation}

for any $\ga$ and any $\gs>\max(\rho-1,0)$. This provides by standard
methods an alternative proof of several of the results above.

In particular, when $\ga=2$, we have $f(n)=\binom n2$ and
$P(t)=\frac12$. When $\ga=1$, we can use TB1 and conclude that

\begin{align}
\end{align}

where $P(t)$ is the Trollope–Delange fractal function (see
[6, 12]):

\begin{equation}\label{per21}
P(t) = \frac12\log_2\pi-\frac14-\frac1{2\log 2}
-\frac1{\log 2}\sum_{l\ne0}\frac{\zeta(\chi_k)}
{\chi_k(\chi_k+1)}\,e^{2k\pi i t}.
\end{equation}

Convergence of Fourier series.
For a fixed real $\gs$, and all real $t$ with $|t|\ge2$, it is known

\begin{equation}\label{zeta}
\begin{cases}
\Theta(|t|^{\frac12-\gs}), & \gs<0,\\
O(|t|^{\frac12}\log|t|), & \gs=0,\\
O(\log|t|), & \gs=1,\\
\Theta(1),&\gs>1,
\end{cases}
\end{equation}

see, e.g.,
or <cit.>.
(Stronger results are known for $0\le\gs\le1$; the best
exponents are still not known for $0<\gs<1$.)
Hence, the Fourier series in (<ref>) and
(<ref>) are absolutely convergent if and only if
$\rho>\frac12$, i.e., if $\ga>\sqrthalf$. Thus, if
$\frac12<\ga<\sqrthalf$, then the Fourier series is not
absolutely convergent. (As a check, we note that (<ref>)
verifies that the Fourier coefficients are in $\ell^2$ for every
$\ga>\frac12$ ($\rho>0$), which is obvious from Parseval's formula.
On the other hand, for $0<\ga\le\frac12$, (<ref>) is not the
Fourier series of any $L^2$ function.)

§ EXTENSION TO NONPOSITIVE $\GA$ OR $\GB$

We have so far considered the recurrence (<ref>), or, equivalently
(<ref>), with $\ga,\gb>0$. Here we discuss rather briefly $\ga$
and $\gb$ with other sign combinations. The case $\ga=\gb=0$ is
trivial, with (<ref>) reduced to $f(n)=g(n)$, and is ignored in
the sequel.

§.§ Recurrences with $\alpha=0$ or $\beta=0$

The situation when $\alpha$ or $\beta$ equals zero is very similar to
the special cases $(\ga,\gb)=(2,0)$ and $(0,2)$ discussed in our
previous paper [27], and we give only some brief
comments. Such sequences abound in OEIS; see tb-EMoser for
a few examples of one kind.

For any $\ga\neq0$, (<ref>) is solved by $\gf_{\ga,0}(t)=0$,
$t\in[0,1)$, and thus (<ref>) yields $f(x)=f(\floor x)$.
Similarly, for $\gb\neq0$, $\gf_{0,\gb}(t)=1$, $t\in(0,1]$, and thus
$f(x)=f(\ceil x)$. The main difference from the case $\ga,\gb>0$ is
that now $\gf$ is discontinuous (at an endpoint), and thus $f(x)$ is
discontinuous except in trivial cases, In the cases $(\ga,0)$ with
$\ga>0$ and $(0,\gb)$ with $\gb>0$, it is easily verified that
Theorem1 holds with modifications similar to the special cases
in <cit.>; note that the periodic
function $P(t)$ now is discontinuous except in trivial cases. If
$\ga<0$ or $\gb<0$, this holds with further modifications as in
SSga<0gb<0 below. We omit the details.

§.§ Recurrences with both $\alpha$ and $\beta$

In this section, we consider the case when $\ga$ and $\gb$ both are
negative; see tb-E<0<0 for a few examples from OEIS
(discussed below). We thus assume the recurrence (<ref>), or,
equivalently, (<ref>) with $\ga,\gb<0$. In this case we define

\begin{align}\label{rho-}
\rho:=\log_2(|\ga|+|\gb|).
\end{align}

Thus $\ga+\gb=-2^\rho$. As above, we define $g(1):=0$. We also extend
the definition of $\gf_{\ga,\gb}(t)$ to negative values of $\ga, \gb$
by $\gf_{\ga,\gb}(t):=\gf_{|\ga|,|\gb|}(t)$, and note that then
(<ref>) holds. The proof of Lemma1 applies, mutatis
mutandis, and shows that (<ref>) holds in this case too. It
follows that the theory developed in Sections
<ref>–<ref> extends to this case, but with an
important modification.

We say that a function $P(t)$ on $\bbR$ is $1$-antiperiodic if
$P(t+1)=-P(t)$ for all $t\in\bbR$. In other words, $P(t)$ is
$1$-antiperiodic if and only if $e^{\pi it}P(t)$ is $1$-periodic.

Note that every $1$-antiperiodic function is $2$-periodic. Moreover, a
$1$-antiperiodic function that is integrable on $\oi$ (and thus on
any compact interval) has a Fourier series that can be written

\begin{align}\label{fou-}
P(t)\sim  \sum_{k\in\bbZ} \hP(k+\tfrac12)e^{(2k+1)\pi\ii t}.
\end{align}

We collect the most important results in the following theorem,
leaving the others in Sections <ref>–<ref> to
the reader.

Suppose that $\ga,\gb<0$, and let $\rho:=\log_2(|\ga|+\gb|)$. Then
Theorem1 holds with the modifications that $1$-periodic is
replaced by $1$-antiperiodic, and that (<ref>) and (<ref>)
are replaced by

\begin{align}\label{t1Q-}
Q(x):=%\sum_{m\ge 1}(-1)^m2^{-\rho m}g(2^{m}x)
\sum_{m\ge 1}(-2^{-\rho})^{m}g(2^{m}x)
=\sum_{m\ge 1}(\ga+\gb)^{-m}g(2^{m}x),
\end{align}

\begin{equation}\label{t1y-}
=\sum_{m\in \mathbb{Z}}(-1)^m2^{-\rho (m+t)}g(2^{m+t})
+f(1)P_0(t), \qquad t\in\mathbb{R},
\end{equation}

where now

\begin{equation}\label{b16-}
P_0\left( t\right)
:= (-1)^{\floor{t}}
\bigpar{ 1+( \alpha +\beta-1)
\varphi\lpa{2^{\{t\}}-1}}
\end{equation}

Moreover, Theorem4 also holds, with the condition
$|\ga|+|\gb|>1$ in part <ref>, and with (<ref>) replaced by

\begin{equation}\label{c4-}
\widehat{P}(k+\tfrac12)
=\frac{1}{\log 2}\int_{1}^{\infty }
\frac{g(u)}{u^{\rho + \chi'_{k}+1}}\dd u
+\frac{f(1)}{\log 2}\int_{0}^{1}
\frac{1+(\alpha +\beta -1)\varphi(u)}
{(1+u)^{\rho +\chi'_{k}+1}}\dd u,
\end{equation}

for $k\in\bbZ$, where

\begin{align}\label{chi'k}
\chi'_{k}
:=\frac{(2k+1)\pi }{\log 2}\ii,
\qquad  k\in\bbZ.
\end{align}

If $\ga=\gb$, then,  in analogy with ChPa=b, (<ref>)
simplifies to

\begin{align}\label{c4+-}
\hP(k+\tfrac12)
&= \frac{1}{(\rho+\chi'_k)(\rho-1+\chi'_k)\log 2}
\Bigpar{D(\rho-1+\chi'_k)
+ \frac{(2\ga-1)(\ga-1)}{\ga}f(1)},
\end{align}

where $D(s)$ is defined in (<ref>).

The proof follows by the same arguments used in Sections
<ref>–<ref>, with minor modifications. In
particular, Lemma3 and Propositions
<ref>–<ref> hold with $P_0$ and $Q$ as
above, $1$-periodic replaced by $1$-antiperiodic, and extra factors
$(-1)^k$ or $(-1)^m$ in the sums in (<ref>), (<ref>),
(<ref>) and in the definition of $G_m(x)$. Note that (<ref>)
now becomes

\begin{align}\label{bb1-}
\end{align}

For the proof of (<ref>), note that (<ref>) holds with
$\chi_k$ replaced by $\chi'_k$, since now $2^{\rho+\chi'_k}

Thus $P(\log_2n)$ in our formulas now is an $1$-antiperiodic function
of $\log_2n$, which implies that it is a $2$-periodic function of
$\log_2n$, or, equivalently, a $1$-periodic function of

Most of the formulas in Sections <ref>–<ref>
hold verbatim for $\ga,\gb<0$ if we instead replace $\rho$ by the
complex logarithm $\rho_{\mathsf c}:=\log_2(\ga+\gb)=\rho+\pi\ii/\log
2$. However, this seems less convenient for applications.

Consider the basic case $g(n)=0$, $f(1)=1$ as in Eg=0; we
again denote the solution $f(n)$ by $S_{\ga,\gb}(n)$. T- shows

\begin{align}\label{Sgagb-}
= n^{\rho} P_0(\log_2 n),\qquad n\ge1,
\end{align}

where now $P_0(t)$ is given by (<ref>). It follows that
(<ref>) still holds, which also follows because for fixed $n$,
$S_{\ga,\gb}(n)$ is a polynomial in $\ga,\gb\in\bbR$, as is
$\varphi\lpa{2^{\para{\log_2n}-1}}(\alpha +\beta)^{\floor{\log_2 n}}$
by (<ref>).

In the special case $\ga=\gb<0$, (<ref>) shows that, in analogy
to (<ref>),

\begin{align}\label{maj1-}
\hP_0(k+\tfrac12)&
\cdot\frac{1}{(\rho+\chi'_k)(\rho-1+\chi'_k)},
\qquad k\in\bbZ,
\end{align}

and, thus (see (<ref>)), $P_0(t)$ has the absolutely convergent
Fourier series

\begin{align}\label{per-}
\frac{(2\ga-1)(\ga-1)}{\ga\log2}
\sum_{k\in\bbZ} \frac{e^{(2k+1)\pi\ii t}}
\end{align}

ccccOEIS     $\left(\alpha,\beta\right)$
$g(n)$     Initials
– Continued from previous page

OEIS     $\left(\alpha,\beta\right)$
$g(n)$     Initials
4rContinued on next page

A005536     $(-1,-1)$     $\tr{\frac12n}$     $f(1)=0$

A079947     $(-1,-1)$     $ n-1 $     $ f(1) = 0 $

A079954     $(-1,-1)$     $ n-2 $     $ f(1) = 0 $

A094120     $(-2,-2)$     $\tr{\frac14n^2}$     $ f(1) = 0 $
Sequences in OEIS satisfying $\Lambda_{\ga,\gb}[f]=g$
with $\ga,\gb<0$.

[Partial sum of Moser-de Bruijn sequences: $\alpha<0$]

Let $\ga<0$. Consider the digital sum $f(n)$ defined in
EMoser as the partial sum of the $\ga$-Moser-de Bruijn
sequence. Then $f$ satisfies (<ref>) with $f(1)=0$. Recall that
$\ga=-1$ gives $\A005536$ treated in <cit.>,
and that $\ga=-2$ gives the partial sums of A053985.

For $\ga<-\frac12$,
we obtain by T-,
directly if $\ga<-1$ and otherwise
by considering

\begin{align}
\label{er5-}
f(n) = n^{1+\log_2 |\ga|}P(\log_2n)-\frac{n}{2(\ga-1)},
\end{align}

for a continuous $1$-antiperiodic function $P(t)$ with the Fourier
expansion (using (<ref>); cf. (<ref>))

\begin{equation}\label{per2-}
= \frac{\alpha-2}{\alpha\log 2}
\sum_{k\in\mathbb{Z}}
\frac{\zeta(\rho-1+\chi_k')}
{(\rho-1+\chi_k')(\rho+\chi_k')}\,e^{(2k+1)\pi i t}.
\end{equation}

As in EMoser, the Fourier series is absolutely convergent if
and only if $\rho>\frac12$, i.e., if and only if $|\ga|>\sqrthalf$.

The case $-\frac12\le\ga<0$ is similar to the case $0<\ga\le\frac12$
discussed in EMoser. (For $\ga=-\frac12$, consider the example
$n=\frac{1}{15}(16^\ell-16^k)$.) Also note that (<ref>) holds
for all $\ga<0$.

[$\ga=\gb=-1$ and thus $\rho=1$]
The function $h(n):=(-1)^{L_n}$ obviously satisfies
$\gL_{-1,0}[h](n)=0$, with $h(1)=1$; thus $h(n)=S_{-1,0}(n)$. By
(<ref>), the partial sums $f(n):=\sum_{1\le k<n}(-1)^{L_k}$

\begin{align}\label{e-1-1a}
\gL_{-1,-1}[f](n)=1, \qquad n\ge2,
\end{align}

with $f(1)=0$. It follows that

\begin{align}\label{e-1-1b}
\end{align}

which is EIIa and (<ref>) with $\ga=-1$;
cf. also Eg=0-. By induction, we have the explicit formula
$f(n) = (-1)^{L_n} n -\frac43(-2)^{L_n}+\frac13$, which implies that
$f(n)=nP(\log_2n)+\frac13$ with the $1$-antiperiodic function

\begin{align}\label{e-1-1p}
= \frac{2}{\log2}
\sum_{k\in\bbZ} \frac{e^{(2k+1)\pi\ii t}}
\end{align}

where the Fourier coefficients follow from (<ref>) and
(<ref>). This sequence is not in OEIS, but the following two
periodically equivalent variants are.

The sequence A079947 is $f(n) := \frac12\sum_{1\le k<n}(1+(-1)^{L_k})$
(partial sums of A030300), which, by (<ref>) or (<ref>),
satisfies $\Lambda_{-1,-1}[f]= n-1$ with $f(1)=0$. We then have, by

\begin{align}\label{a079947}
\end{align}

Explicitly, $f(n) = \frac12\lpa{1+(-1)^{L_n}}n
-\frac23(-2)^{L_n}-\frac13$, so that $f(n) = nP(\log_2n)-\frac13$,
where $P(t)$ is $2$-periodic with

\begin{align}
\Bigpar{\frac12-\frac{2^{1-\frax{t}}}3}
= \frac12+\frac1{\log 2}\sum_{k\in\mathbb{Z}}
\frac{e^{(2k+1)\pi i t}}{\chi'_k(1+\chi'_k)}.
\end{align}

Similarly, A079954 is $f(n) := \frac12\sum_{1\le k<n}(1-(-1)^{L_k})$
(partial sums of A030301), which satisfies $\Lambda_{-1,-1}[f]= n-2$
with $f(1)=0$. We have $f_{\text{A079954}}(n)
=n-1-f_{\text{A079947}}(n)$. Thus, by(<ref>),

\begin{align}\label{a079954}
\end{align}

Explicitly, $f(n) = \frac12\lpa{1-(-1)^{L_n}}n
+\frac23(-2)^{L_n}-\frac23$, so that $f(n) = nP(\log_2n)-\frac23$,
where $P(t)$ is $2$-periodic with

\begin{align}
= \frac12-\frac1{\log 2}\sum_{k\in\mathbb{Z}}
\frac{e^{(2k+1)\pi i t}}{\chi'_k(1+\chi'_k)}.
\end{align}

[$\ga=\gb=-2$ and thus $\rho=2$]
Consider the sequence A094120 given by $f(n):=\sum_{1\le
k<n}\sum_{1\le j\le k}(-2)^{v_2(j)} =\sum_{1\le j<
n}(-2)^{v_2(j)}(n-j)$, where $v_2(j)$ is the dyadic valuation of $j$;
see E22-ns for definition. Note that this is the analogue of
A022560 in E22-ns with $2^{v_2(j)}$ replaced by

By definition, $f(n)$ is the partial sum of $h(k):=\sum_{1\le j\le
k}(-2)^{v_2(j)}$; it is easily seen that $\gL_{-2,0}[h](n)
=\cl{\frac{n}2}$, and thus (<ref>) yields
$g(n):=\Lambda_{-2,-2}[f](n) =\tr{\tfrac14n^2}$. T- does not
directly apply because $g(n)$ grows too rapidly, but we can use a
standard trick and subtract a multiple of $n^2$. We have
$\gL_{-2,-2}[n^2]=2n^2+\Iodd$, and thus $f_1(n):=f(n)-\frac18n^2$
yields $\gL_{-2,-2}[f_1](n)=-\frac38\Iodd$ with $f_1(1)=-\frac18$.
T- applies to $f_1(n)$ and implies that $f_1(n) =
n^2P_1(\log_2n)$ with $P_1(t)$ $1$-antiperiodic, and consequently
$f(n) = n^2P(\log_2n)$, where $P(t)=P_1(t)+\frac18$ is $2$-periodic
with Fourier expansion given by, from (<ref>) applied to $f_1$,

\begin{align}
P(t) = \frac18+\frac3{2\log 2}\sum_{k\in\mathbb{Z}}
\frac{\zeta(1+\chi'_k)}{(1+\chi'_k)(2+\chi'_k)}\,
e^{(2k+1)\pi i t}.
\end{align}

See Figure <ref>.
Note the difference from A022560 in E22-ns where a logarithmic
term appears in (<ref>).

Periodic fluctuations of A094120$(n)/n^2$ (E094120).

§.§ Recurrences with either $\alpha$ or $\beta$

There are many examples in OEIS of sequences satisfying
$\gL_{\ga,\gb}[f]=g$ with $\ga\gb<0$, i.e., one of $\ga$ and $\gb$ is
positive and the other is negative. In this case, we can still define
$\gf(t)$ for dyadic rationals $t\in\oi$ by (<ref>) (and it has to
have this value), but since now $|\ga+\gb|<|\ga|,|\gb|$, this
function is unbounded in every interval, and thus cannot be extended
to a continuous function (or any other reasonable function) on $\oi$.
Hence our methods break down, and we have no general theorem in this
case. Moreover, we do not expect any simple asymptotics in general,
which is illustrated by the following example.

Consider again $f(n)=S_{\ga,\gb}(n)$ defined by
$\gL_{\ga,\gb}[f](n)=0$ and $f(1)=1$. In particular, we have

\begin{align}\label{pm0}
\qquad n\ge1.
\end{align}

Moreover, it is easily seen by induction, or by (<ref>) and
(<ref>), that, for any $\ga$ and $\gb$,

\begin{align}\label{pm1}
\end{align}

By (<ref>) and (<ref>), we have, for example,

\begin{align}
&& k\ge0, \label{pm3}\\
&& k\ge1, \label{pm3-}\\
&& k\ge0 \label{pm3+}.
\end{align}

Consider, for definiteness, the case $\ga>0>\gb$ with
$|\ga|\ge|\gb|$. Then $0\le\ga+\gb<\ga$. Assume also $\ga+\gb\neq1$.
(Otherwise, $S_{\ga,\gb}(n)=1$ for all $n$.) We see from (<ref>)
that $|f(n)|$ may be of the order $\ga^{\log_2n}=n^{\log_2\ga}$,
although (<ref>) shows that $|f(n)|$ also may be much smaller. In
fact, it is easily shown by induction using (<ref>)–(<ref>)
that $|f(n)|\le C\ga^{L_n}$ for some constant $C$ (depending on $\ga$
and $\gb$) and all $n$. Hence, $\xf(n):=n^{-\log_2\ga}f(n)$ is
bounded. However, $\xf(n)$ does not seem to have any simple
asymptotic approximations, as the following arguments show.

First, (<ref>) and (<ref>) show that $\xf(n)$ have
infinitely many jumps with size of order 1. More precisely, it can be
seen from (<ref>) that for every $\eps>0$, there exists $\gd>0$
such that every interval $[N,(1+\eps)N]$ with $N\ge1$ contains some
$n$ such that the jump $|\xf(n+1)-\xf(n)|>\gd$.

Secondly, we cannot have $|f(n)|=n^{\log_2\ga}
\bigpar{P(\log_2n)+o(1)}$ for any $1$-periodic function $P(t)$,
because then substituting $2n$ would give $|f(2n)|=\ga
n^{\log_2\ga}\bigpar{P(\log_2n)+o(1)}$, while (<ref>) would imply
$|f(2n)|=(\ga+\gb)n^{\log_2\ga}\bigpar{P(\log_2n)+o(1)}$, and
together these imply $P(\log_2 n)=o(1)$, so we would have $f(n) =
o(n^{\log_2 \ga})$, which contradicts (<ref>).

There are many OEIS sequences in this category too, and most of them
have $\ga+\gb=0$. We do not discuss these examples further since we
have nothing new to add by our methods, but just mention a prototype
sequence A115384, the partial sum of Thue-Morse sequence (A010060,
the parity of the dyadic valuation), which satisfies
$\Lambda_{-1,1}[f]=\tr{\frac n2}$ with $f(1) = 0$. The exact solution
is given by $f(n) = \tr{\frac n2} +\frac14(1-(-1)^n)
(1+(-1)^{\nu(n-1)})$, where the last term indicates why there is no
simple smooth function providing good asymptotic approximation to
$f(n)-\frac n2$. See also other related sequences A076826, A159481,
A173209 and A245710, which have a very similar behaviour.

§ EXTENSION FROM BINARY TO $Q$-ARY

We consider  briefly the more general recurrence

\begin{align}\label{q1}
= \sum_{0\le j<q}\alpha_{j}f\lpa{\ltr{\tfrac{n+j}q}}
+g(n) \qquad (n\ge q),
\end{align}

for some integer $q\ge2$ and $q$ given constants $\ga_0,
\dots,\ga_{q-1}$; note that the case $q=2$ corresponds to (<ref>).
We now require $g(n)$ for $n\ge q$ and the initial values

Just as the recurrence (<ref>), for example, occurs naturally in
many combinatorial and algorithmic contexts where a problem is split
into two halves, the generalisation (<ref>) occurs typically in
divide-and-conquer context or recursive structures where we instead
divide the source problem into $q$ subproblems of sizes as evenly
as possible.

The case $\ga_0=\dots=\ga_{q-1}=1$ was discussed in [27]
with several examples from the literature and OEIS. We can similarly
extend the method of S:recurrence to treat the general
recursion (<ref>) under suitable conditions. We assume that
$\ga_j$ are real with

\begin{align}\label{q2}
\max_{0\le j<q}|\ga_j| < A:=\sum_{0\le j<q}\ga_j.
\end{align}

Note that (<ref>) holds in the standard case when all $\ga_j>0$;