%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-8/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{thrm}{Theorem}
\newtheorem{lmma}{Lemma}

\title{A Simple Proof of Lerch's Formula}
\author{Tom C. Brown and J\'an Ma\u{n}uch}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and Jan Manuch, \emph{A simple proof of Lerch's formula},
  Proceedings of the Eleventh International Conference on Fibonacci Numbers and
  their Applications. Numer. \textbf{194} (2009), 91--93.}\bigskip\end{center}

\newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}}


\section{Introduction}

Using the convergents of the simple continued fraction for a positive irrational
number\linebreak $\alpha~=~[a_0, a_1, _2, \ldots]~=~a_0~+~\frac1{a_1 + \frac1{a_2 + \cdots}}$,
it is possible to obtain an explicit formula for $\summ{[k\alpha]}$. This
has been done several times. (See \cite{brown+shiue1995-3,hardy+littlewood1922-1,
hardy+littlewood1922-2, ostrowski1922,schoissengeier1986,schoissengeier1984,sos1957}.
These papers all deal with the asymptotic behaviour of the function $C_\alpha(m) = \sum_{k=1}^m
(\{k\alpha\} - \frac12)$, where $\{x\}$ denotes the fractional part of $x$.
Since $k\alpha = [k\alpha] + \{k\alpha\}$, $C_\alpha(m) = \summ{(k\alpha - [k\alpha] - \frac12)}
= \frac{m(m+1)\alpha}2 - \summ{[k\alpha]} - \frac{m(m+1)}4$, any formula for
$\summ{[k\alpha]}$ gives a formula for $C_\alpha(m)$ and conversely.)

The simplest formula for $\summ{[k\alpha]}$ is the following one, taken from \cite{brown+shiue1995-3}.

When $\alpha < 1$, with $\nicefrac{p_n}{q_n} = [0,a_1,a_2,\ldots,a_n]$ ($p_n, q_n$
relatively prime), one has
\[ \sum_{k=1}^{q_n}[k\alpha] = \frac12(p_nq_n - q_n + p_n + (-1)^n). \]

Applying this to $\frac{1 + \sqrt5}2 = 1 + [0,1,1,\ldots]$ gives (after a little
arithmetic) the identity
\[ \sum_{k=1}^{F_n}\left[k\left(\frac{1 + \sqrt5}2\right)\right] = \frac12(F_nF_{n+1} + F_{n-1} - (-1)^n) \]
where $F_0 = 0$, $F_1 = 1$, $F_{n+2} = F_{n+1} + F_n$, $n \geq 0$.

For general $m$, one first writes $m = z_tq_{t-1} + \cdots + z_2q_1 + z_1q_0$,
where $0 \leq z_1 \leq a_1 - 1$; $0 \leq z_i \leq a_i$, $2 \leq i \leq t$; if
$z_i = a_i$, then $z_{i-1} = 0,2\leq i \leq t$. (This is the so-called
``Zeckendorff representation of $m$.'' To find it, subtract the largest possible
$q_j$ from $m$ and repeat.) Then
\[ \summ{[k\alpha]} = \frac12\sum_{1\leq i \leq t} z_i(z_ip_{i-1}q_{i-1} - q_{i-1} + p_{i-1} + (-1)^{i-1}) + \sum_{1\leq i<j\leq t} z_iz_jq_{i-1}p_{j-1} \]

However, in the expression $\summ{[k\alpha]} + \sum_{k=1}^{[m\alpha]}[k\frac1\alpha]$,
the complications arising in the two sums miraculously cancel each other out. M. Lerch
\cite{lerch1904} gave as a problem the identity $\summ{[k\alpha]} + \sum_{k=1}^{[m\alpha]}[k\frac1\alpha]
= m[m\alpha]$. This identity is mentioned in \cite{hardy+littlewood1922-1} and \cite{hardy+littlewood1922-2}.

The authors are not aware of any published proof of this formula, although it is
certainly possible to give a (rather complicated) proof using a formula for
$\summ{[k\alpha]}$. We give below a simple direct proof.

\section{The Proof of Lerch's Formula}

Let $x$ be an irrational number, $x > 1$. Then the set $\{[nx] : n \geq 1\}$
is called a \emph{Beatty sequence}, and is denoted by $\bt{x}$. Our proof
of Lerch's formula is based on the following interesting lemma, first popularized
by Beatty \cite{beatty1927}. (See \cite{berstel+seebold}, and the 12 references given in \cite{fraenkel1969}.)
The papers \cite{borwein+borwein1993} and \cite{fraenkel1969} generalize this result to sequences of the form
$\{[nx + z] : n \geq 1 \}$.

\begin{lmma} Let $x > 1$ and $y > 1$ be two irrational numbers such that $\frac1x
+ \frac1y = 1$. Then the Beatty sequences $\bt{x}$ and $\bt{y}$ form a partition
of $\mathbb{N} = \{ 1, 2, \ldots\}$.\label{sibelius}\end{lmma}
\begin{proof} For any $t\in\mathbb{N}$, define $A_t = \bt{x}\cap(0,t)$, $B_t = \bt{y}
\cap(0,t)$.

Since $x > 1$, $y > 1$ are irrational, we obtain $\frac{t}x - 1 < |A_t| < \frac{t}x$
and $\frac{t}y - 1 < |B_t| < \frac{t}y$. Hence $t - 2 < |A_t| + |B_t| < t$, so $|A_t|
+ |B_t| = t - 1$, for each $t \geq 1$. Now by induction on $t$, it easily follows
that the sets $A_t$ and $B_t$ form a partition of $\{ 1, 2, \ldots, t - 1\}$.
\end{proof}

As an immediate consequence we have:
\begin{lmma} Let $a > 0$ and $b > 0$ be two irrational numbers such that $\frac1a
+ \frac1b = 1$. Let $n$ be a positive integer. Then
\[ \sum_{[ka]\leq n} [ka] + \sum_{[kb]\leq n} [kb] = \frac12n(n + 1) \]
\label{frang}\end{lmma}

Now we are almost ready to prove Lerch's formula. We will need the following facts
about the floor function $\floor{\cdot}$:
\begin{lmma} Let $\alpha > 0$, $x = 1 + \alpha$, $y = 1 + \frac1\alpha$, and let
$m,k$ be positive integers. Then
\begin{enumerate}
\item[\textnormal{(a)}] $\floor{\floor{m\alpha}\frac1\alpha} \leq m \leq \floor{(m\alpha + 1)\frac1\alpha}$
\item[\textnormal{(b)}] $\floor{ky} \leq \floor{mx}$ iff $k\leq \floor{m\alpha}$
\end{enumerate}\label{prokofiev}\end{lmma}
\begin{proof} Part (a) follows directly from the definition of the floor function.
Obviously, $\floor{ky} \leq \floor{mx}$ is equivalent to $k + \floor{k\frac1\alpha} \leq m + \floor{m\alpha}$.

Now, if $k \leq \floor{m\alpha}$ then, by part (a), $\floor{k\frac1\alpha} \leq m$. Adding these
two inequalities gives $k + \floor{k\frac1\alpha} \leq m + \floor{m\alpha}$.

On the other hand, if $k > \floor{m\alpha}$, then $k \geq \floor{m\alpha} + 1$, so by part (a),
$\floor{k\frac1\alpha} \geq m$. Adding the first and last of these inequalities gives
$k + \floor{k\frac1\alpha} > m + \floor{m\alpha}$.\end{proof}

\begin{thrm} (Lerch's formula) Let $a$ be a positive irrational real number. Then for
every positive integer $m$,
\[ \summ{\floor{k\alpha}} + \sum_{k=1}^{\floor{m\alpha}}\floor{k\frac1\alpha} = m\floor{m\alpha} \]
\end{thrm}
\begin{proof} Let $x = 1 + \alpha$, $y = 1 + \frac1\alpha$. By Lemma \ref{frang}
(with $n = \floor{mx}$), we have
\begin{align*}
\sum_{\floor{kx}\leq\floor{mx}}\floor{kx} + \sum_{\floor{ky}\leq\floor{mx}}\floor{ky}
&= \frac12\floor{mx}(\floor{mx} + 1) \\
&= \frac12(m + \floor{m\alpha})(m + \floor{m\alpha} + 1) \\
&= \frac12m(m + 1) + \frac12\floor{m\alpha}(\floor{m\alpha} + 1) + m\floor{m\alpha}.
\end{align*}
On the other hand, by Lemma \ref{prokofiev},
\begin{align*}
\sum_{\floor{kx}\leq\floor{mx}}\floor{kx} + \sum_{\floor{ky}\leq\floor{mx}}\floor{ky}
&= \summ{\floor{kx}} + \sum_{k=1}^{\floor{m\alpha}}\floor{ky} \\
&= \summ{k + \floor{k\alpha}} + \sum_{k=1}^{\floor{m\alpha}}\left(k + \floor{k\frac1\alpha}\right) \\
&= \summ{\floor{k\alpha}} + \sum_{k=1}^{\floor{m\alpha}} \floor{k\frac1\alpha} + \frac12m(m + 1) + \frac12\floor{m\alpha}(\floor{m\alpha} + 1)
\end{align*}
Lerch's formula follows.
\end{proof}

\section{An Application}

Let $\alpha = \frac{1+\sqrt5}2$, and let $F_0 = 0$, $F_1 = 1$, $F_{n+1} = F_{n+1} + F_n$,
$n \geq 0$. When $n > 1$ and $i = 1,2,3,$ we have the well-known identities
\[ \floor{F_n\alpha^i} = F_{n+i} - \frac12((-1)^n + 1) \]
\[ \floor{F_{n+1}\frac1{\alpha^i}} = F_n - \frac12\left((-1)^{n+1} + 1\right) \]
These, together with Lerch's formula, give
\[ \sum_{k=1}^{F_n}\floor{k\alpha} + \sum_{k=1}^{F_{n+1}}\floor{k\frac1{\alpha}} = F_nF_{n+1} \]
\[ \sum_{k=1}^{F_n}\floor{k\alpha^2} + \sum_{k=1}^{F_{n+2}}\floor{k\frac1{\alpha^2}} = F_nF_{n+2} \]
\[ \sum_{k=1}^{F_n}\floor{k\alpha^3} + \sum_{k=1}^{F_{n+3}}\floor{k\frac1{\alpha^3}} = F_nF_{n+3} \]
Adding the first two equations, and equating the resulting right hand side with
the right hand side of the third equation, gives the following pleasing identity,
valid for $n > 1$:
\[ \sum_{k=1}^{F_n}(\floor{k\alpha} + \floor{k\alpha^2}) +
\sum_{k=1}^{F_{n+1}}\floor{k\frac1{\alpha}} +
\sum_{k=1}^{F_{n+2}}\floor{k\frac1{\alpha^2}} =
\sum_{k=1}^{F_n}\floor{k\alpha^3} + \sum_{k=1}^{F_{n+3}}\floor{k\frac1{\alpha^3}} \]


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}

