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