%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-29/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{rmrk}{Remark}
\newtheorem{lmma}{Lemma}
\newtheorem*{prop}{Proposition}

\title{Powers of Digital Sums}
\author{T. C. Brown\footnote{Department of Mathematics and Statistics, ¶¡ÏãÔ°AV, Burnaby, British Columbia, V5A 1S6, Canada. \texttt{tbrown@sfu.ca}}}
\date{}

\newcommand{\floor}[1]{{\left[{#1}\right]}}
\newcommand{\ceil}[1]{{\left[{#1}\right]}}

\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Powers of digital sums}, Fib. Quart. \textbf{32} (1994),
  207--210.}\bigskip\end{center}

\section{Introduction}

Let $s(n)$ denote the sum of the base 10 digits of the nonnegative integer $n$,
and let $\log x$ denote the base 10 logarithm of $x$. R. E. Kennedy and C.
Cooper have shown \cite{cooper+kennedy1992} that for any positive integer
$k$,
\[ \frac1x\sum_{n\leq x}s(n)^k = \left(\frac92\right)^k\log^kx + O(\log^{k-\frac13}x), \]
and they conjectured that for any positive integer $k$,
\[ \frac1x\sum_{n\leq x}s(n)^k = \left(\frac92\right)^k\log^kx + O(\log^{k-1}x). \]

Recently \cite{cooper+kennedy1993} the same authors have shown, providing
some evidence for the truth of this conjecture, that for each fixed positive
integer $k$,
\[ \frac1{10^n}\sum_{i=0}^{10^n-1}s(i)^k = \left(\frac92\right)^kn^k + O(n^{k-1}). \]

In this note, we extend the result just mentioned. When $k$ is a fixed
positive integer, we show that for each $m$ it is true that
\[ \frac1x\sum_{n\leq x}s(n)^k = \left(\frac92\right)^k\log^kx + O(\log^{k-1}x), \]
provided that $x$ is restricted to the set of those positive integers having
at most $m$ nonzero digits in their base 10 representations. (Thus, the
Kennedy \& Cooper result is exactly the case $m = 1$.) We use the Kennedy
\& Cooper result in the course of our proof.

We state our result in the following form.

\begin{prop} Let $m\geq1$ and $k\geq1$ be fixed integers. Then there is a
constant $A = A(k,m)$ such that if $x$ is a positive integer with at most
$m$ nonzero digits in its base 10 representation,
\[ \left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^k(\log x)^k\right| < A(\log x)^{k-1}. \]
\end{prop}

\section{Remarks and Lemmas}

\begin{rmrk}\label{r1} It is easy to check that if $m,k$ are fixed positive
integers and
\[ \left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^k\ceil{\log x}^k\right| < c\ceil{\log x}^{k-1}, \]
then
\[ \left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^k(\log x)^k\right| < d(\log x)^{k-1}, \]
where $\ceil{\cdot}$ denotes the greatest integer function and $d$ is a
constant that depends only on $c$ and $k$.\end{rmrk}

To see this, suppose $10^n\leq x\leq 10^{n+1}$, so that $n =\ceil{\log x}$. Let
$\log x = n + \alpha$, where $0 \leq \alpha < 1$. Then
\begin{align*}
\left|\frac1x\sum_{i=0}^{x-1}\right.&\left.s(i)^k - \left(\frac92\right)^k(n+\alpha)^k\right| \\
&< \left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^kn^k\right| + \left|\left(\frac92\right)^kn^k - \left(\frac92\right)^k(n+\alpha)^k\right| \\
&= \left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^kn^k\right| + \left(\frac92\right)^k\fp{k\alpha n^{k-1} + \binom{k}2\alpha^2n^{k-2} + \cdots + \binom{k}k\alpha^k} \\
&< cn^{k-1} + c'n^{k-1} = dn^{k-1} \leq d(n+\alpha)^{k-1}.
\end{align*}

\begin{rmrk}\label{r2} In view of Remark \ref{r1}, to prove the Proposition
above, it is sufficient (and convenient) to prove the following statement,
which will be done by induction on $m$.\end{rmrk}

For fixed positive integers $m$, $k$, there is an $A = A(k,m)$ such that
if $10^n\leq x<10^{n+1}$ and $x$ has at most $m$ nonzero digits in its
base 10 representation, then
\[ \left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^kn^k\right| < An^{k-1}. \]

In the following three lemmas, $k,n,p,y$ and $t$ all denote integers.

\begin{lmma}\label{l1} For each $k\geq1$, there is an $A(k)$ such that
\[ \frac{n\cdot10^{p+1}}{10^n + 10^{p+1}}\left(1 - \left(\frac{p}{n}\right)^k\right) < A(k)\text{ for all }n,p\text{ with }1\leq p\leq n. \]
\end{lmma}\begin{proof} Let $s = n - p - 1$. Then $-1\leq s \leq n - 2$
and
\begin{align*}
\frac{n\cdot10^{p+1}}{10^n + 10^{p+1}}\left(1 - \left(\frac{p}{n}\right)^k\right)
&= \frac{n}{10^s + 1}\left(1 - \left(1 - \frac{s+1}n\right)^k\right) \\
&= \frac{n}{10^s + 1}\left(k\cdot\frac{s+1}{n} - \binom{k}2\frac{(s+1)^2}{n^2} + \binom{k}2\frac{(s+1)^3}{n^3} - \cdots - (-1)^k\binom{k}k\frac{(s+1)^k}{n^k}\right) \\
&= \frac{k\cdot(s+1)}{10^s+1} + o(1) < A(k).
\end{align*}\end{proof}

Note that for $i\geq2$,
\[ \frac{n}{10^s + 1} \frac{(s+1)^i}{n^i} \leq \left(\max_{-1\leq s<\infty} \frac{(s+1)^i}{10^s + 1}\right)\cdot\frac1{n^{i-1}}\to0\text{ as }n\to\infty. \]

\begin{lmma}\label{l2} Fix $k\geq1$. Let $A(k)$ be as in Lemma \ref{l1}.
Then for any $y$ in the interval $10^p\leq y\leq 10^{p+1}\leq 10^n$ and
any $t\geq1$,
\[ \left|\frac{t\cdot10^n}{t\cdot10^n+y}\left(\frac92\right)^kn^k + \frac{y}{t\cdot10^n + y}\left(\frac92\right)^kp^k - \left(\frac92\right)^kn^k\right|
< \left(\frac92\right)^kA(k)n^{k-1}. \]
\end{lmma}\begin{proof}
\begin{align*}
\left|\frac{t\cdot10^n}{t\cdot10^n + y}n^k + \frac{y}{t\cdot10^n+y}p^k - n^k\right|
&= n^k\frac{y}{t\cdot10^n+y}\left(1 - \left(\frac{p}n\right)^k\right) \\
&< n^k\frac{10^{p+1}}{t\cdot10^n + 10^{p+1}}\cdot\left(1 - \left(\frac{p}n\right)^k\right) \\
&\leq n^{k-1}\frac{n\cdot10^{p+1}}{10^n + 10^{p+1}}\left(1 - \left(\frac{p}n\right)^k\right) \\
&< A(k)\cdot n^{k-1},
\end{align*}
where the last inequality is given by Lemma \ref{l1}.
\end{proof}

\begin{lmma}\label{l3} Let $t\geq1$ and $k\geq1$ be fixed. Then
\[ \frac1{t\cdot10^n}\sum_{i=0}^{t\cdot10^n-1} s(i)^k = \left(\frac92\right)^kn^k + O(n^{k-1}). \]
In other words, there is $B(t,k)$ with
\[ \left| \frac1{t\cdot10^n}\sum_{i=0}^{t\cdot10^n-1} s(i)^k - \left(\frac92\right)^kn^k\right| < B(t,k)n^{k-1}. \]
\end{lmma}

To prove the Proposition, we will only need this lemma for $t = 1,2,\ldots,9$.

\begin{proof} We use induction on $t$. For $t = 1$, this is the result of Kennedy
\& Cooper mentioned above. Now fix $t\geq1$ and assume the result for this $t$.
Then, using the fact that $s(t\cdot10^n + i) = s(t) + s(i)$, $0\leq i\leq 10^n-1$,
\begin{align*}
\left| \frac1{(t+1)\cdot10^n}\sum_{i=0}^{t\cdot10^n-1} s(i)^k - \left(\frac92\right)^kn^k\right|
&\leq \left|\frac{t}{t+1}\left(\frac1{t\cdot10^n}\sum_{i=0}^{t\cdot10^n-1} s(i)^k - \left(\frac92\right)^k\right)\right| \\
&+ \left|\frac{1}{t+1}\left(\frac1{\cdot10^n}\sum_{i=0}^{t\cdot10^n-1} s(i)^k - \left(\frac92\right)^k\right)\right| \\
&+ \frac1{t+1}\cdot\frac1{10^n}\sum_{i=0}^{t\cdot10^n-1} (c_1s(i)^{k-1} + c_2s(i)^{k-2} + \cdots + c_k) \\
&< \frac{t}{t+1}B(t,k)n^{k-1} + \frac1{t+1}B(1,k)n^{k-1} + Cn^{k-1} \\
&< B(t+1,k)n^{k-1}.
\end{align*}
\end{proof}

Note that we used the result of Kennedy \& Cooper a second time. Here $c_1,\ldots,c_k$,
$C$ are constants that depend only on $k$ and $t$.

\section{Proof of the Proposition}

According to Remark \ref{r2}, we need to show that, for each $m\geq1$ and $k\geq1$,
there is a constant $A(k,m)$ such that if $10^n\leq x<10^{n+1}$ and $x$ has at
most $m$ nonzero digits in its base 10 representation, then
\[ \left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^k\right| < A(k,m)n^{k-1}. \]

If $m=1$, this follows from Lemma \ref{l3} (for all $k$), since then $x = t\cdot10^n$,
$1\leq t\leq 9$.

Now assume the result for a given $m\geq1$, and let $x$ have $m+1$ nonzero digits,
say,
\[ 10^n\leq x<10^{n+1}, x = t\cdot10^n + y, 1\leq t\leq 9, 10^p\leq y<10^{p+1}\leq 10^n, \]
where $y$ has $m$ nonzero digits. Then, using $s(t\cdot10^n + i) = t + s(i)$,
\begin{align*}
\left|\frac1x\sum_{i=0}^{x-1}s(i)^k - \left(\frac92\right)^k\right|
&\leq \left|\frac{t\cdot10^n}{t\cdot10^n + y}\left(\frac1{t\cdot10^n}\sum_{i=0}^{t\cdot10^n-1} s(i)^k - \left(\frac92\right)^k\right)\right| \\
&+ \left|\frac{y}{t\cdot10^n+y}\left(\frac1y\sum_{i=0}^{y-1}s(i)^k - \left(\frac92\right)^k\right)\right| \\
&+ \frac{y}{t\cdot10^n + y}\cdot\frac1y\sum_{i=0}^{y-1}(c_1s(i)^{k-1} + c_2s(i)^{k-2} + \cdots + c_k) \\
&< A(k,1)n^{k-1} + A(k,m)p^{k-1} + Dp^{k-1} \\
&< A(k,m+1)n^{k-1}.
\end{align*}
Here $c_1,\ldots,c_k,D$ are constants that depend on $k$ and $t$, but since
$1\leq t\leq 9$, they in fact depend only on $k$. For the second equality,
we used Lemma \ref{l3} as well as the induction hypothesis.


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