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