.fp 4 SC
.PH ""
.nr Pt 1
.EQ
delim $$
gsize 12
define cD % "\o'|\(sl'" %
define scrJ % font 4 size +2 J %
define aA % {size 16 /} %
.EN
.am DE
.sp
..
.ds HP 12 12 12 12 12
.ds HF 3 3 3 3 3
.ls 1
.ce 99
.S 12
.B
The asymptotic behavior of a family of sequences
.R
.sp
.I
P. Erdo\*:s
.R
Hungarian Academy of Sciences
Budapest, Hungary
.sp
.I
A. Hildebrand$"" sup *$
.R
University of Illinois
Urbana, Illinois
.sp
.I
A. Odlyzko
.R
AT&T Bell Laboratories
Murray Hill, New Jersey
.sp
.I
P. Pudaite
B. Reznick$"" sup **$
.R
University of Illinois
Urbana, Illinois
.ce 0
.FS *
Supported by
a grant from the Deutsche Forschungsgemeinschaft.
.FE
.FS **
Supported by the National Science Foundation, by an Alfred P. Sloan
Fellowship, and by an Arnold O. Beckman Fellowship at the UIUC Center
for Advanced Study.
.FE
.sp
.ce
.I
ABSTRACT
.R
.sp
.ls 2
.P
A class of sequences defined by nonlinear recurrences involving
the greatest integer function is studied, a typical member of
the class being
.DS 3
.EQ
a(0) ~=~ 1, ~~~a (n) ~=~ a ( left floor n/2 right floor ) ~+~ a ( left floor
n/3 right floor ) ~+~ a ( left floor n/6 right floor ) ~roman for ~ n ~>=~ 1~.
.EN
.DE
For this sequence, it is shown that lim $a(n)/n$ as $n ~->~ inf$ exists
and equals $12/( log ~432)$.
More generally, for any sequence defined by
.DS 3
.EQ
a(0) ~=~ 1, ~~~a(n) ~=~ sum from i=1 to s ~r sub i ~a( left floor n/m sub i
right floor ) ~roman for ~ n ~>=~ 1~,
.EN
.DE
where the $r sub i ~>~ 0$ and the $m sub i$ are integers $>=~ 2$,
the asymptotic behavior of $a(n)$ is determined.
.bp
.ls 1
.ce 99
.B
The asymptotic behavior of a family of sequences
.R
.sp
.I
P. Erdo\*:s
.R
Hungarian Academy of Sciences
Budapest, Hungary
.sp
.I
A. Hildebrand$"" sup *$
.R
University of Illinois
Urbana, Illinois
.sp
.I
A. Odlyzko
.R
AT&T Bell Laboratories
Murray Hill, New Jersey
.sp
.I
P. Pudaite
B. Reznick$"" sup **$
.R
University of Illinois
Urbana, Illinois
.ce 0
.FS *
Supported by
a grant from the Deutsche Forschungsgemeinschaft.
.FE
.FS **
Supported by the National Science Foundation, by an Alfred P. Sloan
Fellowship, and by an Arnold O. Beckman Fellowship at the UIUC Center
for Advanced Study.
.FE
.ls 2
.H 1 "Introduction"
Rawsthorne [R] recently asked whether the limit $a(n)/n$ exists
for the sequence $a(n)$ defined by
.pn 2
.PH "''- \\\\nP -''"
.nr Eq 1
.DS 3
.EQ (1.1)
a(0) ~=~ 1, ~~~a(n) ~=~ a( left floor n/2 right floor ) ~+~ a(
left floor n/3 right floor ) ~+~ a( left floor n/6 right floor ),
~~n ~>=~ 1 ~,
.EN
.DE
where $left floor x right floor$ denotes the greatest integer
$<= ~x$.
If the limit exists, Rawsthorne also asked for its value.
We have answered these questions [EHOPR]: the limit exists and equals
$12/ log ~432$, where, as in the rest of the paper, log denotes
the natural logarithm.
Our method leads to a more general result about such recursively
defined sequences.
.P
Let $a(n)$ be the sequence defined by
.DS 3
.EQ (1.2)
a(0) ~=~ 1, ~~~a(n) ~=~ sum from i=1 to s ~r sub i a( left floor n/{m sub i}
right floor ), ~~n ~>=~ 1~,
.EN
.DE
where $r sub i ~>~ 0$ and the $m sub i$'s are integers $>= ~2$.
Let $tau$ be the (unique) solution to
.DS 3
.EQ (1.3)
sum from i=1 to s ~{r sub i} over {m sub i sup tau} ~=~ 1~.
.EN
.DE
We distinguish two cases: if there is an integer $d$ and integers
$u sub i$ such that $m sub i ~=~ d sup {u sub i}$, we are in
the \f2lattice\f1 case, otherwise we are in the \f2ordinary\f1 case.
In the ordinary case, $lim ~a(n)/ n sup tau$ exists; in the lattice
case, $lim ~a(n)/n sup tau$ does not exist, but
$lim from {k ~->~ inf} ~a( d sup k ) / d sup {k tau}$ exists.
The limit in either case is readily computable.
The proof involves transforming (1.2) into a renewal equation and
using the standard limit theorems for that equation.
For a precise statement of our results, see Theorem 2.14 below.
.P
We are interested also in the rapidity of convergence.
We prove that $(a(n) ~-~ a(n-1))/n sup tau$ is greater than
$gamma ~cdot~ ( log n ) sup -(s-1)/2$ for some $gamma ~>~ 0$ and
infinitely many $n$.
In Rawsthorne's original sequence (1.1), this result can
be strengthened (see Theorem 3.46).
For $n ~=~ 432 sup t$,
.DS 3
.EQ (1.4)
{a(n) ~-~ a(n-1)} over n ~wig~ left ( 6 over {5 pi t} right ) sup half
~~roman as ~~t ~->~ inf ~,
.EN
.DE
and this is, asymptotically, an upper bound.
The numbers $J(m ^,^ r) ~: =~ a( 2 sup m 3 sup r ) ~-~ a( 2 sup m 3 sup r -1)$
satisfy the so-called ``square'' functional equation; we use the
work of Stanton and Cowan and others to help in the asymptotic
analysis.
.P
A somewhat different functional equation was studied by Erdo\*:s
[E1], [E2]: for $2 ~<=~ a sub 1 ~<=~ a sub 2 ~<= ^...$
a sequence of integers, let
.DS 3
.EQ
F(0) ~mark =~ 0, ~~F(1) ~=~ 1~,
.EN
.sp
.EQ
F(n) ~lineup =~ sum from k=1 to inf ~F( left floor n/ a sub k right floor )
~+~ 1 ~~roman for ~~ n ~>~ 1~.
.EN
.DE
Both the methods and results are different from ours.
.H 1 "An application of renewal theory"
We fix the following notation.
Let integers $m sub i , ~2 ~<=~ m sub i ~<=~ M$, and positive
real numbers $r sub i$ be given.
Define the sequence $a(n)$ recursively by
.DS 3
.EQ (2.1)
a(0) ~=~ 1, ~~~a(n) ~=~ sum from i=1 to s ~r sub i a ( left floor n/ m sub i
right floor ), ~~n ~>=~ 1~.
.EN
.DE
For $x ~>=~ 0$ define
.DS 3
.EQ (2.2)
A(x) ~=~ a( left floor x right floor )~.
.EN
.DE
Since $left floor x/mn right floor ~=~ left floor left floor x/m right floor /n right floor$
for positive integers $m$ and $n$, we may define $A(x)$ directly
and, in effect, extend the sequence to a function on the positive reals:
.DS 3
.EQ (2.3)
A(x) ~=~ 1 ~roman for ~0 ~<=~ x ~<~ 1, ~~~A(x) ~=~ sum from i=1 to s ~r sub i
A left ( x/ m sub i right ) ~roman for~ x ~>=~ 1~.
.EN
.DE
Note that the function $phi (u) ~=~ sum ~r sub i / m sub i sup u$
decreases strictly on the real line from $inf$ to 0 so there exists
a unique $tau ~>~ 0$ satisfying
.DS 3
.EQ (2.4)
phi ( tau ) ~=~ sum from i=1 to s ~{r sub i} over {m sub i sup tau} ~: =~
sum from i=1 to s ~p sub i ~=~ 1~.
.EN
.DE
Now let
.DS 3
.EQ (2.5)
f(x) ~=~ A(x)/ x sup tau
.EN
.DE
so that we may rewrite (2.3) as
.DS 3
.EQ (2.6)
f(x) ~=~ x sup {- tau} , ~~0 ~<~ x ~<~ 1; ~~f(x) ~=~ sum from i=1 to s
~{r sub i} over {m sub i sup tau} f left ( x over {m sub i} right )
~~roman for ~ x ~>=~ 1~.
.EN
.DE
Since $p sub i ~>~ 0$ and $sum ~p sub i ~=~ 1, ~f(x)$ is a convex
combination of previous values of $f$ for $x ~>=~ 1$.
It is thus unsurprising that $f$ tends to a limit.
.P
It is now appropriate to review some well-known (to probabilists)
results about the renewal equation.
We paraphrase Feller [F, v. 2, pp. 358-362].
Suppose $h$ is a Riemann integrable function with compact support
and $F "{" dy "}"$ is a probability measure with finite expectation
and suppose $g$ satisfies the renewal equation
.DS 3
.EQ (2.7)
g(u) ~=~ h(u) ~+~ int sub 0 sup u ~g(u-v) F "{" dv "}" ~~,~~ u ~>=~ 0~.
.EN
.DE
If the mass of $F "{" dv "}"$ is concentrated on a set of the
form $"{" 0, lambda , 2 lambda ^,... "}"$, we are in the \f2lattice\f1
case; otherwise we are in the \f2ordinary\f1 case.
The following limit theorem for $g$ is due to
Erdo\*:s, Feller, and Pollard in the lattice case and Blackwell
in the ordinary case.
.sp
\f2Renewal Limit Theorem\f1 (see [F, v. 2, p. 362]).
.br
.I
(i) In the ordinary case,
.DS 3
.EQ (2.8)
lim from {u ~->~ inf} ~g(u) ~=~ {int sub 0 sup inf h(u) du} over
{int sub 0 sup inf y F "{" dy "}" }
~.
.EN
.DE
(ii) In the lattice case, let $lambda$ be chosen to be maximal;
then $g$ does not converge, but for any fixed $x ~epsilon~ [0, lambda )$,
.DS 3
.EQ (2.9)
lim from {n ~->~ inf} ~g(x+ n lambda ) ~=~ {lambda ~sum from k=0 to inf
h(x+ k lambda )} over {int sub 0 sup inf ~yF "{" dy "}" } ~,
.EN
.DE
where the limit in (2.9) is taken over integral $n$.
.R
.P
We now return to our problem.
Let
.DS 3
.EQ (2.10)
g(u) ~=~ f( e sup u )~.
.EN
.DE
Then (2.6) can be rewritten as
.DS 3
.EQ (2.11)
g(u) ~=~ e sup {- tau u} , ~~u ~<=~ 0 ; ~~g(u) ~=~ sum from i=1 to s
~p sub i g(u - log ^ m sub i ), ~~u ~>=~ 0~.
.EN
.DE
Let $F "{" dv "}"$ be the probability measure with mass $p sub i$
at $log ~m sub i$.
Then $g$ satisfies an equation of the form (2.7),
where $h$ measures the discrepancy between the full recurrence
of (2.11) and that portion provided by the convolution in (2.7).
This discrepancy arises from a negative argument of $g$.
Hence,
.DS 3
.EQ (2.12)
h(u) ~=~ sum from {u ~<~ log ^m sub i} ~p sub i ~e sup {- tau (u- log ^m sub i )}
~=~ sum from {u ~<~ log ^m sub i} ~p sub i m sub i sup tau e sup {- tau u} ~,
.EN
.DE
and so
.DS 3
.EQ (2.13)
h(u) ~=~ sum from i=1 to s ~p sub i m sub i sup tau e sup {- tau u} ~chi
sub {[0, log ^m sub i )} (u) ~.
.EN
.DE
Having now transformed (1.2) into a renewal equation we must decide
which case we are in.
The mass of $F$ is concentrated at $"{" log ^m sub i "}"$, which is
a subset of $"{" 0, lambda , 2 lambda ^,... "}"$ for some $lambda$
(the lattice case) if and only if $m sub i ~=~ d sup {u sub i}$ for
some integers $d$ and $u sub i$.
Alternatively, we are in the ordinary case if and only if
$( log ^m sub i ) ^/^( log ^m sub j )$ is irrational
for some $( m sub i , m sub j )$.
.P
We now combine these discussions into a theorem.
.sp
\f2Theorem 2.14\f1.
.I
Let $a(n)$ be defined by (2.1) and let $tau$ be defined as above.
.br
(i) If $tau ~=~ 0$ then $a(n) ~==~ 1$.
.br
(ii) If $tau ~!=~ 0$ and $( log ^m sub i ) ^/^ ( log ^m sub j )$ is
irrational
for some $(m sub i , m sub j )$ (the ordinary case), then
.DS 3
.EQ (2.15)
lim from {n ~->~ inf} ~{a(n)} over {n sup tau} ~=~ {sum from i=1 to s ~
p sub i (m sub i sup tau -1) / tau} over {sum from i=1 to s ~p sub i
~ log m sub i}
~.
.EN
.DE
(iii) If $tau ~!=~ 0$ and $m sub i ~=~ d sup {u sub i}$, where
$d$ and the $u sub i$'s are integers and $d$ is maximal (the lattice
case), then
.DS 3
.EQ (2.16)
lim from {k ~->~ inf} ~{a( d sup k )} over {d sup {k tau}} ~=~
{sum from i=1 to s ~p sub i (m sub i sup tau -1)} over {sum from i=1 to s ~
p sub i ~ log ^m sub i} ~cdot~ {d sup tau log ^d} over {d sup tau -1}
~.
.EN
.DE
.R
\f2Proof\f1.
(i) If $tau ~=~ 0$, then $sum ~r sub i ~=~1$ and it is easy to see
from (2.1) that $a(n) ~==~ 1$ by induction.
As $u sup tau ~-~ 1 ~approx~ tau ~ log ~ u$ for $tau$ near 0, this result
is consistent with the limiting behavior in (2.15) and (2.16).
.br
(ii) From our definitions,
.DS 3
.EQ (2.17)
a(n) over {n sup tau} ~=~ f(n) ~=~ g( log ^n)~,
.EN
.DE
so that information about the limiting behavior of $g(u)$
from the Renewal Limit Theorem can be translated into information
about $a(n)/ n sup tau$.
In either the ordinary or lattice case,
.DS 3
.EQ (2.18)
int sub 0 sup inf ~yF "{" dy "}" ~=~ sum from i=1 to s ~p sub i log ^m sub i ~.
.EN
.DE
.P
In the ordinary case, as $tau ~!=~ 0$, we have by (2.13),
.DS 3
.EQ (2.19)
int sub 0 sup inf ~h(u) du ~mark =~ sum from i=1 to s ~p sub i m sub i sup tau
~int sub 0 sup {log ^m sub i} ~e sup {- tau u} du
.EN
.sp
.EQ
~lineup =~ sum from i=1 to s ~p sub i m sub i sup tau (1- m sub i sup {- tau}
)/ tau~.
.EN
.DE
Equation (2.15) follows from the foregoing discussion, (2.8),
(2.18), and (2.19).
.br
(iii) The period of the lattice is $lambda ~=~ log ^d$, and
taking $x ~=~ 0$ in (2.9),
.DS 3
.EQ (2.20)
sum from k=0 to inf ^ h(k lambda ) ~=~ sum from k=0 to inf ^ h(k log ^d)
~=~ sum from k=0 to inf left ( sum from i=1 to s ~p sub i m sub i sup tau
e sup {- tau k log ^d} chi sub {[0, log ^m sub i )} (k log ^d) right )
~.
.EN
.DE
Since $m sub i ~=~ d sup {u sub i}$,
.DS 3
.EQ (2.21)
sum from k=0 to inf ~e sup {- tau k log ^d} chi sub {[0, log ^m sub i )} ^
(k log ^d) ~=~ sum from k=0 to {u sub i -1} ~e sup {- tau k log d}
.EN
.sp
.EQ
=~ (1 ~-~ d sup {- u sub i tau} )/(1- d sup {- tau} ) ~=~ (1- m sub i sup
{- tau} ) d sup tau /( d sup tau -1) ~.
.EN
.DE
We now exchange the order of summation in (2.20) to obtain
.DS 3
.EQ (2.22)
sum from k=0 to inf ^h(k lambda ) ~=~ sum from i=1 to s ~p sub i m sub i
sup tau (1- m sub i sup {- tau} ) d sup tau /(d sup tau -1) ~,
.EN
.DE
and (2.16) follows from (2.18), (2.22), and (2.9).
$blot$
.P
In the lattice case, it is easy to show by induction that
the sequence $a(n)$ is constant on intervals of the form
$[ d sup k , ~d sup k+1 -1)$.
For any rational $x ~=~ j/ d sup r$, $d sup t ~<~ x ~<~ d sup t+1$,
$a( x d sup k )$ is defined for $k ~>=~ r$, and
$a( x d sup k ) ~=~ a( d sup t-r+k )$.
Using (2.16), one can compute $lim ~a(d sup k x)/ (d sup k x) sup tau$;
we omit the details.
.P
As a check of Theorem 2.14, consider the following simple lattice
example with $s ~=~ 1$:
.DS 3
.EQ (2.23)
a(0) ~=~ 1; ~~~a(n) ~=~ d sup alpha a ( left floor n/d right floor ) ~~,~~
n ~>=~ 1~.
.EN
.DE
It is easy to see in this case that $tau ~=~ alpha$ and
$a( d sup k ) ~=~ d sup {(k+1) alpha}$, so that
$a(d sup k ) / d sup {k tau} ~==~ d sup alpha$.
Substituting $p sub 1 ~=~ 1, ~m sub 1 ~=~ d$, and
$tau ~=~ alpha$ into (2.16) returns $d sup alpha$, as predicted.
.P
It is perhaps worth mentioning that the existence of
$lim from {n ~->~ inf} ~f(n)$ can be proved without recourse
to the Renewal Limit Theorem.
Here is a sketch of the argument, without proofs.
First, from (2.6), $alpha ~>=~ f(x) ~>=~ beta$ for
$x ~epsilon~ [y, My]$, where $y ~>=~ 1$ and $M ~>=~ max ^m sub i$
implies that $alpha ~>=~ f(x) ~>=~ beta$ for all $x ~>=~ y$.
Thus $L ~=~ lim bar ~f(x)$ and $scrL ~=~ lim under ~f(x)$ are positive
and finite.
Pick sequences $r sub k ~->~ inf$ and $s sub k ~->~ inf$ with
$f( r sub k ) ~->~ L, ~f( s sub k ) ~->~ scrL$ and
$r sub k ~<~ s sub k ~<~ M r sub k$.
The next step in the argument is proved as in Section 3;
$a(n) ~!=~ a(n-1)$ if and only if $n ~=~ m sub 1 sup {e sub 1} ^...^ m sub s sup {e sub s}$
for some integers $e sub i$ and $tau ~!=~ 0, ~a(n) ~>=~ a(n-1)$ if 
$tau ~>~ 0$ and $a(n) ~<=~ a(n-1)$ if $tau ~<~ 0$.
There is a dichotomy depending on which case arises.
In the lattice case, $a(n)$ is constant on intervals
$[d sup k , ~d sup k+1 -1]$ and the substitutions $m = d sup {u sub i}$,
$b(k) ~=~ a( d sup k )$ show that $"{" b(k) "}"$ satisfies a linear
difference equation for $k$ sufficiently large.
By the standard method for solving linear difference equations
(see [T, Ch. 4]), for example)
$a( d sup k ) ~=~ b (k) ~=~ c ~cdot~ beta sup k ~+~ o( beta sup k ) ~=~ c d sup {k tau} ~+~ o (d sup {k tau} )$
for appropriate constants.
(See the discussion following Corollary 3.12 for more details.)
.P
In the ordinary case, suppose $( log ^m sub i ) ^/^ ( log ^m sub j ) ~nomem~ Q$
and let $m = m sub i$ and $m bar = m sub j$.
For any $epsilon ~>~ 0$ there exists $E$ so that every $x$ in
$[M sup -1 , M]$ is contained in an interval $[w, w( 1+ epsilon )]$,
where $w ~=~ m sup {e sub 1} / m bar sup {e sub 2}$ and $e sub 1$
and $e sub 2$ are positive integers $<= ~E$.
Let $W$ be any finite set of integers of the form
$m sub 1 sup {f sub 1} ^...^ m sub s sup {f sub s}$; for $k$ sufficiently
large and any $w ~epsilon~ W$, $f(r sub k /w)$ is close to $L$ and
$f( s sub k /w)$ is close to $scrL$.
(This is proved by induction; basically, if a weighted average like
(2.6) is close to the maximum then its components can't be too
far off.)
Now suppose $tau ~>~ 0$ and $L ~>~ scrL$ and let $x ~=~ s sub k / r sub k$,
where $k$ is sufficiently large, let $w ~=~ m sup {e sub 1} / m bar sup {e sub 2}$
be chosen so that $x ~epsilon~ [w, w(1+ epsilon )]$.
Then $r prime ~=~ r sub k / m bar sup {e sub 2}$ is a little less
than $s prime ~=~ s sub k / m sup {e sub 1}$, but $f( r prime )$ is
close to $L$ and $f( s prime )$ is close to $scrL$.
As $tau ~>~ 0, ~a( s prime ) ~>=~ a( r prime )$, and this gives a contradiction
to $L ~>~ scrL$.
(More precisely, $epsilon$ is chosen so that $L ~-~ epsilon ~>~ (1+ epsilon ) sup tau ~( scrL + epsilon )$.)
A similar contradiction can be wrought when $tau ~<~ 0$.
In either case, $L ~=~ scrL$ so the limit exists.
This method, although self-contained, gives no hint about the
actual value of the limit.
.H 1 "Rates of convergence"
We retain the notation of the last section and continue to
assume that $a(n)$ is defined by (2.1).
Let
.DS 3
.EQ (3.1)
J(n) ~=~ a(n) ~-~ a(n-1)
.EN
.DE
denote the jump of the sequence at $n$.
In this section we derive closed forms for $a(n)$ and $J(n)$ and
use them to given an indication of the rate of convergence of $f$.
Ideally, one would discuss the behavior of $| f(x) ~-~ lim ~f(x) |$.
As a step in that direction, we consider the ``jumps'' of $f$.
It is clear from (2.2) and (2.5) that $f$ is everywhere continuous
from the right and $f$ is continuous from the left except possibly
at certain integers.
Let
.DS 3
.EQ (3.2)
z(n) ~=~ f(n) ~-~ lim from {epsilon ~->~ 0 sup +} f(n- epsilon ) ~=~
{a(n) - a(n-1)} over {n sup tau} ~=~ {J(n)} over {n sup tau} ~.
.EN
.DE
We shall show in this section that, in the ordinary case,
$| z(n) | ~>~ c ( log n) sup {- (s-1) /2}$ for some $c ~>~ 0$
and infinitely many integers $n$.
In Rawsthorne's original problem, (1.1), the exponent of $log ^n$
may be improved from -1 to -1/2.
.P
In finding a closed form for $a(n)$, the following notation is useful.
Let $i under ~=~ (i sub 1 ^,...,^ i sub scrL ) ~,~ scrL ~>=~ 1$, be
an $scrL$-tuple of integers, $1 ~<=~ i sub j ~<=~ s$.
Let $I( i under )$ be the associated interval:
.DS 3
.EQ (3.3)
I( i under ) ~=~ [ m sub i ^...^ m sub {i sub {scrL -1}} ~,~
m sub i ^...^
m sub {i sub {scrL -1}} ~ m sub {i sub scrL} )~.
.EN
.DE
(If $scrL ~=~ 1$ in (3.3), take the left-hand endpoint to be 1.)
As an inverse function to $I$, for $x ~>=~ 1$, let
.DS 3
.EQ (3.4)
B(x) ~=~ "{" i under : ~x ~epsilon~ I ( i under ) "}"
~.
.EN
.DE
\f2Theorem 3.5\f1.
.I
For $x ~>=~ 1$,
.DS 3
.EQ (3.6)
A(x) ~=~ sum from {i under ~epsilon~ B(x)} ~r sub {i sub 1} ^...^ r sub {i sub scrL}~.
.EN
.DE
.R
\f2Proof\f1.
Recall the basic recurrence (2.3):
.DS 3
.EQ
A(x) ~=~ sum from i=1 to s ~r sub i A left ( x/ m sub i right )~.
.EN
.DE
Consider the infinite tree with root ``$x$'' and valence $s$
so that each node ``$y$'' on the k-th level is connected to the
nodes ``$y/m sub i$'', $1 ~<=~ i ~<=~ s$ on the $(k+1)st$ level.
We use this tree to iterate the recurrence (2.3) until the
argument of $A$ goes below 1 for the first time.
In this way, the path from $x$ to $x/ m sub {i sub 1} ^,...$ to
$x/(m sub {i sub 1} ^...^ m sub {i sub scrL} )$ acquires the coefficient
$r sub {i sub 1} ^...^ r sub {i sub scrL}$.
Since $i under ~=~ (i sub 1 ^,...,^ i sub scrL )$ is in $B(x)$
by construction and $A(x/ prod m sub {i sub j} ) ~=~ 1$, (3.6) is established.
$blot$
.P
We now derive a recurrence for $J(n) ~=~ a(n) - a(n-1)$ and find
a closed form for $J(n)$.
.sp
\f2Theorem 3.7\f1.
.P
(i) $J(n) ~=~ sum from {m sub i | n} ~r sub i J left ( n/ m sub i right )$.
.P
(ii) $J(n) ~=~ ( sum from i=1 to s ~r sub i ~-~1) ~sum from {m sub 1 sup {e sub 1} ^...^ m sub s sup {e sub s} ^=^n}$
${(e sub 1 ^+...+^ e sub s )!} over {e sub 1 ! ^...^ e sub s !} ~r sub 1 sup {e sub 1} ^...^ r sub s sup {e sub s}~.$
.sp
\f2Proof\f1.
(i) We have from (2.3)
.DS 3
.EQ (3.8)
J(n) ~=~ sum from i=1 to s ~r sub i ^ left ( A left ( n over {m sub i} right )
~-~ A left ( n-1 over {m sub i} right ) right )
~.
.EN
.DE
If $m sub i ~cD~ n$ then $left floor n/ m sub i right floor ~=$
$left floor (n-1) / m sub i right floor$ so the i-th term is zero;
if $m sub i | n$, then by definition, the i-th term is
$r sub i J(n/ m sub i )$.
.sp
(ii) Observe that $J(1) ~=~ a(1) - a(0) ~=~ sum from i=1 to s ~r sub i ~-~ 1$.
Then, consider each representation of $n$ as a product
$m sub 1 sup {e sub 1} ^...^ m sub s sup {e sub s}$.
The formula (ii) follows by induction from (i) and the well-known
multinomial recurrence:
.DS 3
.EQ
{(e sub 1 ^+...+^ e sub s )!} over {e sub 1 ! ^...^ e sub s !} ~=~
sum from {e sub i ~>=~ 1} ~{( e sub 1 ^+...+^ e sub s -1)!} over
{e sub 1 ! ^...^ (e sub i -1)! ^...^ e sub s !}
~.~~~blot
.EN
.DE
.P
We note that (ii) can also be derived from Theorem 3.5 and a
consideration of $B(n) ~-~ B(n-1)$ and $B(n-1) ~-~ B(n)$.
If we consider the representations
$n ~=~ m sub 1 sup {e sub 1} ^...^ m sub s sup {e sub s}$ as formally
distinct, we may let $j( f sub 1 ^,...,^ f sub s )$ denote that
portion of the jump $J(n)$ contributed by the representation
$n ~=~ m sub 1 sup {f sub 1} ^...^ m sub s sup {f sub s}$.
In view of Theorem 3.7 we have the following recurrences and
generating function.
.DS 3
.EQ (3.9)
left {
matrix {
lcol {j (e sub 1 ^,...,^ e sub s ) ~=~ sum from {e sub i ~>=~ 1} ~r sub i
j (e sub 1 ^,...,^ e sub i -1 ^,...,^ e sub s ), above j(0 ^,...,^ 0) ~=~
sum from i=1 to s ~r sub i -1~.}
}
.EN
.DE
.DS 3
.EQ (3.10)
j( e sub 1 ^,...,^ e sub s ) ~=~ ( sum from i=1 to s ~r sub i -1 ) ~
{( e sub 1 ^+...+^ e sub s )!} over {e sub 1 ! ^...^ e sub s !} ~r sub 1
sup {e sub 1} ^...^ r sub s sup {e sub s}~.
.EN
.DE
.DS 3
.EQ (3.11)
scrJ ( z sub 1 ^,...,^ z sub s ) ^=^ sum j ( e sub 1 ^,...,^ e sub s ) z sub 1
sup {e sub 1} ^...^ z sub s sup {e sub s} ^=^ ( sum from i=1 to s ^r sub i
-1 ) (1 ^-^ sum from i=1 to s ~r sub i z sub i ) sup -1 ~.
.EN
.DE
\f2Corollary 3.12\f1.
.I
If $tau ~>~ 0$ then $J(n) ~>~ 0$ at all $n$ of the form
$m sub 1 sup {e sub 1} ^...^ m sub s sup {e sub s}$; if
$tau ~<~ 0$ then $J(n) ~<~ 0$ at all such $n$.
.R
.sp
\f2Proof\f1.
From Theorem 3.7 (ii), the sign of $J(n)$ is the sign of
$sum from i=1 to s ~r sub i -1$, which equals $phi (0) ~-~ phi ( tau )$
in the notation of (2.4).
Since $phi$ is strictly decreasing, the conclusions follow immediately.
$blot$
.P
We now turn our attention to the size of $z(n)$.
It is convenient to dispose of the lattice case.
As $f(d sup k )$ converges to a limit $scrL$ and $A(x)$
is constant on $[ d sup k-1 , ~d sup k ), ~z( d sup k ) ~wig~ scrL (1- d sup {- tau} )$.
It is more interesting to look at
$f( d sup k+1 ) ~-~ f( d sup k )$.
Let $m sub i ~=~ d sup {u sub i}$ and let $u ~=~ max ~ u sub i$.
Then from (2.6),
.DS 3
.EQ (3.13)
f( d sup k ) ~=~ sum from i=1 to s ~p sub i f( d sup {k- u sub i} ) ~.
.EN
.DE
Let $psi (t) ~=~ t sup u ~-~ sum p sub i t sup {u- u sub i}$ be
the characteristic equation of the linear recurrence satisfied
by $f( d sup k )$.
Clearly $psi (1) ~=~ 0$ and, as $lim | f ( d sup k ) | ~<~ inf$,
it follows that the other roots of $psi$ have moduli less than one.
Hence there exists a polynomial $q$ of degree at most $s-1$ and
$lambda , ~0 ~<=~ lambda ~<~ 1$ so that
.DS 3
.EQ (3.14)
| f ( d sup k ) ~-~ 1 ~ | ~<=~ q(k) lambda sup k ~+~ o ( lambda sup k )~.
.EN
.DE
It follows that $| f(d sup k+1 ) ~-~f( d sup k ) | ~<=~ c k sup r lambda sup k$
for sufficiently large $k, ~r ~<=~ s-1$ and some $c ~>~ 0$.
.P
Henceforth we assume the ordinary case and $tau ~!=~ 0$.
We first need two approximation lemmas.
The first follows directly from the Stirling approximation
$GAMMA (w+1) ~wig~ w sup w e sup -w ~{sqrt {2 pi w}}$ and
we omit the proof.
The second allows us to adjust from real numbers to integers
in our asymptotic analysis.
.sp
\f2Lemma 3.15\f1.
.I
Fix $alpha sub i ~>~ 0 ~,~ sum from i=1 to s ~alpha sub i ~=~ 1$
and define
.DS 3
.EQ (3.16)
F( x sub 1 ^,...,^ x sub s ) ~=~ {GAMMA ( sum from i=1 to s x sub i +1)}
over {prod from i=1 to s ~GAMMA~ (x sub i +1)}
~.
.EN
.DE
Then, as $q ~->~ inf$,
.DS 3
.EQ (3.17)
F( alpha sub 1 q ^,...,^ alpha sub s q) ~wig~ (2 pi q) sup {- s-1 over 2}
~prod from i=1 to s ~alpha sub i sup {-( alpha sub i q + 1/2 )}
~.
.EN
.DE
\f2Lemma 3.18\f1.
.I
Fix $alpha sub i ~>~ 0, ~sum from i=1 to s ~alpha sub i ~=~ 1$
and define
.R
.DS 3
.EQ (3.19)
phi (q ; ~t sub 1 ^,...,^ t sub s ) ~=~ {F( alpha sub 1 q +t sub 1 ^,...,^
alpha sub s q + t sub s )} over {F( alpha sub 1 q ^,...,^ alpha sub s q)} ~.
.EN
.DE
.I
Then there exists $c~>~0$ so that for all sufficiently large $q$
and all choices of $t sub i$ with $| t sub i | ~<~ 1$ and
$sum from i=1 to s ~t sub i ~=~ 0$,
.R
.DS 3
.EQ (3.20)
c sup -1 ~<~ phi (q; ~t sub 1 ^,...,^ t sub s ) ~<~ c
~.
.EN
.DE
.R
\f2Proof\f1.
From (3.16) we have
.DS 3
.EQ
phi (q; ~t sub 1 ^,...,^ t sub s ) ~mark =~ {GAMMA (q+1)} over
{prod from i=1 to s GAMMA ( alpha sub i q+ t sub i +1)} ~aA~
{GAMMA (q+1)}
over {prod from i=1 to s GAMMA ( alpha sub i q+1)}
.EN
.sp
.EQ (3.21)
~~~~~
.EN
.sp
.EQ
~lineup =~ prod from i=1 to s ~{GAMMA ( alpha sub i q+1)} over
{GAMMA ( alpha sub i q+ t sub i +1)} ~.
.EN
.DE
Let
.DS 3
.EQ (3.22)
H( alpha , q, t) ~=~ log ~ GAMMA ( alpha q + t +1) ~-~ log ~GAMMA ( alpha
q +1) ~.
.EN
.DE
As $log ~ GAMMA$ is convex, for $| t | ~<~ 1, ~t ~!=~ 0$ we have
.DS 3
.EQ (3.23)
log ^ GAMMA ( alpha q +2) ^-^ log ~GAMMA ( alpha q+1) ~>=~ {H( alpha , q,t)}
over {t} ~>=~ log ~ GAMMA ( alpha q+1) ~-~ log ~ GAMMA ( alpha q)~,
.EN
.DE
hence $H( alpha , q,t) ~=~ t log ( alpha q +p)$,
$0 ~<=~ p ~<=~ 1$, and
.DS 3
.EQ
- log phi ( q; t sub 1 ^,...,^ t sub s ) ~mark =~ sum from i=1 to s ~H
( alpha sub i , q, t sub i )
.EN
.sp
.EQ (3.24)
~lineup =~ sum from i=1 to s ~t sub i log ( alpha sub i q+ p sub i )
.EN
.DE
.DS 3
.EQ
=~ sum from i=1 to s ~t sub i log ^ alpha sub i ~+~ sum from i=1 to s
~t sub i log ^ q ~+~ sum from i=1 to s ~t sub i log (1 ^+^ {p sub i} over
{alpha sub i q} )~.
.EN
.DE
Since $sum t sub i ~=~ 0 ~,~ | t sub i | ~<~ 1$ and
$| p sub i | ~<~ 1$,
.DS 3
.EQ (3.25)
| log ~ phi (q; ~t sub 1 ^,...,^ t sub s ) | ~<=~ sum from i=1 to s ~t sub i
log ~ alpha sub i ~+~ sum from i=1 to s 1 over {alpha sub i q}
~,
.EN
.DE
from which (3.20) follows.
$blot$
.sp
\f2Theorem 3.26\f1.
.I
In the ordinary case with $tau ~!=~ 0$ there exists $gamma ~>~ 0$
so that
.DS 3
.EQ (3.27)
| z(n) | ~>~ gamma ~cdot~ ( log ~ n) sup {- s-1 over 2} 
.EN
.DE
for infinitely many $n$.
.R
.sp
\f2Proof\f1.
The main idea is to let $n ~=~ ( m sub i sup {p sub i} ^...^ m sub s sup {p sub s} ) sup q$
for large $q$.
Large in this case means that (3.17) is a good approximation.
Since $p sub i q$ is not an integer in general, we need the
approximation of Lemma 3.18.
.P
To be specific, choose $q$ large and choose integers
$e sub i , ~sum from i=1 to s ~e sub i ~=~ q$ such that
$| e sub i ~-~ p sub i q | ~<~ 1$ for all $i$.
By Theorem 3.7 (ii), we may ignore other representations of $n$ and
.DS 3
.EQ (3.28)
| J(n) | ~>=~ alpha ~cdot~ {( e sub 1 ^+...+^ e sub s )!} over {e sub 1 !
^...^ e sub s !} ~r sub 1 sup {e sub 1} ^...^ r sub s sup {e sub s} ~,
.EN
.DE
where $alpha ~=~ | sum from i=1 to s ~r sub i ~-~ 1 | ~=~ | phi ( tau ) ~-~ phi (0) | ~>~ 0$.
We now replace $e sub i$ by $p sub i q$ in (3.28): $prod r sub i sup {e sub i}$
changes by a bounded factor, and by Lemma 3.18 we have
.DS 3
.EQ (3.29)
| J (n) | ~>=~ beta ~cdot~ {GAMMA (q+1)} over {prod from i=1 to s (p sub i q+1)}
~cdot~ prod from i=1 to s ~r sub i sup {p sub i q} ~,
.EN
.DE
where $beta$ has absorbed all other constants.
Finally, by Lemma 3.16,
.DS 3
.EQ
| J(n) | ~mark >=~ beta ~cdot~ (2 pi q) sup {- s-1 over 2} ~prod from i=1
to s ~p sub i sup {- (p sub i q + 1/2 )} ~r sub i sup {p sub i q}
~(1- epsilon )
.EN
.sp
.EQ (3.30)
~lineup =~ gamma q sup {- s-1 over 2} ~prod from i=1 to s ~( r sub i / p
sub i ) sup {p sub i q}
.EN
.sp
.EQ
~lineup =~ gamma q sup {- (s-1) over 2} ~prod from i=1 to s ~m sub i sup
{tau p sub i q} ~=~ gamma q sup {- (s-1) over 2} ~n sup tau ~.
.EN
.DE
Since $z(n) ~=~ J(n)/ n sup tau$ and $q ~=~ ( log ~ n)/ ( sum p sub i log ~m sub i )$,
(3.27) follows.
$blot$
.P
It is possible to sharpen the constant slightly by noting
that for any $epsilon ~>~ 0$ there are infinitely many $q$
such that $p sub i q$ is within $epsilon$ of an integer for all $i$.
(Standard pigeonhole principle argument.)
If $s$ were to equal 1 then (3.27) would violate the convergence
of $f$, except that $s=1$ is always a lattice case.
.P
We conclude this paper by returning to Rawsthorne's original problem:
.DS 3
.EQ
a(0) ~=~ 1 ~,~~~ a(n) ~=~ a( left floor n/2 right floor ) ~+~ a
( left floor n/3 right floor ) ~+~ a( left floor n/6 right floor )~.
.EN
.DE
By Theorem 3.7 we know that $a(n)$ jumps only at numbers of the
form $2 sup {e sub 1} ^ 3 sup {e sub 2} ^ 6 sup {e sub 3}$; that is,
products of 2 and 3.
Let
.DS 3
.EQ (3.31)
J(m,r) ~= :~ J( 2 sup m 3 sup r )~.
.EN
.DE
Then $m ~=~ e sub 1 + e sub 3$, $r ~=~ e sub 2 + e sub 3$,
and by both parts of Theorem 3.7,
.DS 3
.EQ (3.32)
J(m,r ) ~=~ 2 sum from i {(m+r-i)!} over {(m-i)! (r-i)! i!} ~=~
2 sum from i ~left ( {pile {m+r-i above m-i}} right ) ^ left (
{pile {r above i}} right )
~,
.EN
.sp
.EQ (3.33)
left {
matrix {
lcol {J(m^,^r) ~=~ J(m^,^r-1) ~+~ J(m-1^,^r) ~+~ J(m-1^,^ r-1), ~m^,^r ~>=~ 1
~,
above J(0^,^0) ~=~ J(m ^,^ 0) ~=~ J(0 ^,^ r) ~=~ 2~.}
}
.EN
.DE
.P
Unsurprisingly, such a simply defined recurrence has a large literature;
(3.33) is called the ``square'' functional equation and arises
as a natural generalization of Pascal's triangle.
(Actually, $1 over 2 J$ is the standard form.)
The first problem on the 19th Putnam Competition was to show
that $S(n) ~=~ 1 over 2 ~sum from i ^ J(i, n-i)$ satisfies
the recurrence $S(n+2) ~=~ 2S(n+1) ~+~ S(n)$ [GGK, p. 53].
This recurrence then
arose in Golomb's study of sphere packing
in the Lee metric [Go].
Stanton and Cowan [SC] considered (3.32) in its own right and were
the first to prove Lemma 3.34 below.
A. K. Gupta [Gu1] [Gu2] gave different proofs and generalized
these numbers further, as did Carlitz [Ca] and Alladi and Hoggatt
[AH].
The function $1 over 2 J$ has a natural interpretation as the number
of ways to go from (0,0) to $(m,r)$ with steps of size (1,0), (0,1) or
(1,1); see Fray and Roselle [FR] or Handa and Mohanty [HM].
Greene and Knuth [GK; pp. 111-113] discuss the asymptotics of $J(m,m)$.
.P
Our analysis of $z( 2 sup m 3 sup r )$ relies crucially on the following
combinatorial lemma.
.sp
\f2Lemma 3.34\f1.
.DS 3
.EQ (3.35)
J(m,r) ~=~ 2 sum from i ~left ( {pile {m above i}} right ) ^ left (
{pile {r above i}} right ) 2 sup i ~=~ 2 sum from i ~left (
{pile {m+r-i above m-i}} right ) ^ left ( {pile {r above i}} right )
~.
.EN
.DE
\f2Proof\f1.
Consider the coefficient of $x sup m$ in
$2(1+x) sup m (1+2x) sup r ~=$
$2(1+x) sup m (1+x+x) sup r ~=$
$2 sum from i left ( {pile {r above i}} right ) x sup i (1+x) sup m+r-i$.
$blot$
.P
Stanton and Cowan originally proved this lemma by a sequence of
standard combinatorial substitutions.
Gupta used a number of methods, including the following hypergeometric
representation [Gu1, Lemma 4]:
.DS 3
.EQ (3.36)
1 over 2 J(m,r) ~=~ "" sub 2 F sub 1 (-m, ^ -r; ^ 1, ^2)~.
.EN
.DE
.P
Lemma 3.34 leads to a natural probabilistic interpretation of
$J(m,r)$.
Let
.DS 3
.EQ (3.37)
alpha (m,i) ~=~ {left ( {pile {m above i}} right )} over {2 sup m} ~,~
beta (r,i) ~=~ {left ( {pile {r above i}} right ) 2 sup i} over {3 sup r} ~.
.EN
.DE
These denote the probabilities of $i$ successes in $m$ and $r$ Bernoulli
trials with $p ~=~ 1/2$ and $2/3$ respectively.
As
.DS 3
.EQ (3.38)
z( 2 sup m 3 sup r ) ~=~ {J(m,r)} over {2 sup m 3 sup r} ~=~ 2 sum from i
~alpha (m,i) beta (r,i) ~,
.EN
.DE
one expects $z( 2 sup m 3 sup r )$ to be largest when the probability
distributions peak simultaneously; that is, when $m/2 ~approx~ 2r/3$,
cf. Proposition 3.41.
As a preliminary bound, note that $alpha ( m,i) ~<=~ alpha (m, m/2)$
and $beta (r,i) ~<=~ beta (r, 2r/3)$, replacing factorials by $GAMMA$
as necessary.
By Lemma 3.15, $alpha (m,i) ~<=~ gamma sub 0 m sup -1/2$ and
$beta (r,i) ~<=~ gamma sub 1 r sup -1/2$ for appropriate $gamma sub i ~>~ 0$.
Hence
.DS 3
.EQ (3.39)
z( 2 sup m 3 sup r ) ~<=~ min ( gamma sub 0 m sup -1/2 , gamma sub 1 r sup -1/2 )~.
.EN
.DE
Since $log ( 2 sup m 3 sup r ) ~=~ m log ^2 ~+~ r log ^3$,
(3.39) implies that $z(n) ~<=~ gamma ( log ^n ) sup -1/2$ for
some $gamma ~>~ 0$ and all $n$.
.P
Consider now the normal approximation to the binomial distribution,
see e.g. [F, v. 1, p. 170].
For fixed $k$,
.DS 3
.EQ (3.40)
left {
matrix {
lcol {alpha (m, m over 2 ~+~ k {sqrt m} over 2 ) ~wig~ 2 over {sqrt m} ~1
over {sqrt {2 pi}} e sup {- 1 over 2 k sup 2 }~, above beta (r, 2r over 3
~+~ k {sqrt 2r} over 3 ) ~wig~ 3 over {sqrt 2r} ~1 over {sqrt {2 pi}}
~e sup {- 1 over 2 k sup 2}~.}
}
.EN
.DE
Let $DELTA (m,r) ~=~ | m over 2 ~-~ 2r over 3 |$.
We now show that if $DELTA (m,r)$ is comparable to $sqrt m$
and $sqrt r$,
then $z( 2 sup m 3 sup r )$ is quite a bit smaller than
$gamma ( log n ) sup -1/2$.
.sp
\f2Proposition 3.41\f1.
.I
Fix $k, epsilon ~>~ 0$ and suppose
.DS 3
.EQ (3.42)
DELTA (m,r) ~=~ | m over 2 ~-~ 2r over 3 | ~>~ k ~left ( {sqrt m} over 2
~+~ {sqrt 2r} over 3 right ) ~.
.EN
.DE
Then for sufficiently large $m$ and $r$,
.DS 3
.EQ (3.43)
z(2 sup m 3 sup r ) ~<=~ 2(1+ epsilon ) ~left ( 2 over {sqrt m} ~+~
3 over {sqrt 2r} right ) ~1 over {sqrt {2 pi}} e sup {- 1 over 2 k sup 2}
~.
.EN
.DE
.R
\f2Proof\f1.
If (3.42) holds, then for each $i$ at least one of the inequalities
.DS 3
.EQ (3.44)
| m over 2 ~-~ i | ~>~ {k sqrt m} over 2 ~~roman or~~ | 2r over 3 ~-~ i |
~>~ {k sqrt 2r} over 3
.EN
.DE
is valid.
Suppose that $m$ and $r$ are large enough that the approximation
in (3.40) becomes an inequality after multiplication by $1+ epsilon$.
Let $I ~=~ "{" i: ~ | m over 2 ~-~ i | ~>~ {k sqrt m} over 2 "}"$; then
.DS 3
.EQ
z(2 sup m 3 sup r ) ~mark <=~ 2(1+ epsilon ) ~( sum from {i member I}
alpha (m,i)) ~2 over {sqrt m} ~1 over {sqrt {2 pi}} e sup {- 1 over 2 k sup 2}
.EN
.sp
.EQ (3.45)
+~ 2 (1+ epsilon ) ~( sum from {i nomem I} ~beta (r,i)) ~3 over {sqrt 2r}
~1 over {sqrt {2 pi}} e sup {-^ 1 over 2 k sup 2}
.EN
.sp
.EQ
~lineup <=~ 2(1+ epsilon ) ~( 2 over {sqrt m} ~+~ 3 over {sqrt 2r} )
~1 over {sqrt {2 pi}} e sup {- 1 over 2 k sup 2} ~.~blot
.EN
.DE
.P
We remark that, if $r ~wig~ alpha m$, where $alpha ~!=~ 3/4$, then
this proposition implies that
.DS 3
.EQ
z(n) ~=~ z( 2 sup m 3 sup r ) ~<=~ h sub 1 ( alpha ) ( log ~ n ) sup -1/2 ~
n sup {- h sub 2 ( alpha )} ~,
.EN
.DE
where $h sub 1 ( alpha )$ and $h sub 2 ( alpha )$ are complicated
positive algebraic functions of $alpha$.
We spare the reader the gory details.
The asymptotic behavior of
.DS 3
.EQ
sum ~left ( {pile {c above i}} right ) ^ left ( {pile {alpha c above i}} right ) ~x sup i
.EN
.DE
has been studied by Laquer [La]; more precise information than
Proposition 3.41 can be found there, as can our final estimate,
whose proof we sketch.
.sp
\f2Theorem 3.46\f1.
.I
For $n ~=~ 432 sup t ~=~ 2 sup 4t 3 sup 3t$,
.R
.DS 3
.EQ (3.47)
z(n) ~wig~ left ( 6 over {5 pi t} right ) sup half ~=~ left (
{6 ~ log ~ 432} over {5 pi ~ log ~ n} right ) sup half ~.
.EN
.DE
\f2Proof\f1.
After a reindexing, (3.38) becomes
.DS 3
.EQ (3.48)
z(n) ~=~ sum from i ~alpha (4t, ^ 2t+i) ~beta~ (3t, ^2t+i)
~.
.EN
.DE
By Feller [v. 1, p. 170], the estimates (3.40) are valid for
$| i | ~<=~ t sup {2/3 - epsilon}$, so the tails can be ignored.
These approximations reduce to a Riemann sum:
.DS 3
.EQ (3.49)
z(n) ~wig~ {sqrt {3 over 2}} ~1 over pi ~1 over {sqrt t} ~{size 14 sum} from i
e sup {- 5 over 4 {i sup 2} over t} ~wig~ {sqrt {6 over {5 pi t}}} ~.~blot
.EN
.DE
.P
As a measure of the slowness of convergence of $f$ and the
accuracy of (3.47), let $n ~=~ 432 sup 5 ~-wig~ 1.5 times 10 sup 13$.
Then $f(n-1) ~-wig~ 1.8430, ~f(n) ~-wig~ 2.1175$, so
$z(n) ~-wig~ .2745$, whereas $(6/(25 pi ) ) sup half ~-wig~ .2764$.
.bp
.ls 1
\f3Bibliography\f1
.sp
[AH] K. Alladi and V. Hoggatt, Jr., ``On Tribonacci Numbers and
Related Functions,'' \f2Fib. Quart.\f1 \f215\f1 (1977), pp. 42-45.
.sp
[Ca] L. Carlitz, ``Some $q$-analogues of Certain Combinatorial
Numbers,'' \f2SIAM J. Math. Anal.\f1 \f24\f1 (1973), pp. 433-436.
.sp
[E1] P. Erdo\*:s, ``On some Asymptotic Formulas in the Theory of `Factorisatio
Numerorum','' \f2Annals Math. 42\f1 (1941), pp. 989-993.
.sp
[E2] P. Erdo\*:s, ``Corrections to two of my Papers,'' (with an appendix
by E. Hille), \f2Annals Math. 44\f1 (1943), pp. 647-651.
.sp
[EHOPR] P. Erdo\*:s, A. Hildebrand, A. Odlyzko, P. Pudaite, and
B. Reznick, ``A Very Slowly Converging Sequence,'' \f2Math. Mag. 58\f1
(1985), pp. 51-52.
.sp
[F] W. Feller, \f2An Introduction to Probability Theory and its Applications\f1,
2nd ed., Wiley, New York, vol. I, 1957, vol. II, 1971.
.sp
[FR] R. D. Fray and D. Roselle, ``Weighted Lattice Paths,'' \f2Pacific
J. Math.\f1 \f237\f1 (1971), pp. 85-96.
.sp
[GGK] A. M. Gleason, R. E. Greenwood, and L. M. Kelly, \f2The
William Lowell Putnam Mathematical Competition\f1, Math. Assn. of
America, 1980.
.sp
[Go] S. Golomb, ``Sphere Packing, Coding Metrics and Chess Puzzles,''
in \f2Proc. 2nd Chapel Hill Conference on Combinatorial Mathematics,\f1
1970, pp. 176-189.
.sp
[GK] D. H. Greene and D. E. Knuth, \f2Mathematics for the Analysis of
Algorithms\f1, 2nd ed., Birkha\*:user, Boston, 1982.
.sp
[Gu1] A. K. Gupta, ``On a `Square' Functional Equation,''
\f2Pacific J. Math.\f1 \f250\f1, (1974), pp. 449-454.
.sp
[Gu2] A. K. Gupta, ``Generalisation of a `Square' Functional
Equation,'' \f2Pacific J. Math.\f1 \f257\f1 (1975), pp. 419-422.
.sp
[HM] B. R. Handa and S. G. Mohanty, ``Higher Dimensional Lattice Paths
with Diagonal Steps,'' \f2Discr. Math.\f1 \f215\f1 (1976), pp. 137-140.
.sp
[La] H. D. Laquer, ``Asymptotic Limits for a Two-Dimensional Recursion,''
\f2Stud. Appl. Math.\f1 \f264\f1 (1981), pp. 271-277.
.sp
[R] D. Rawsthorne, Problem 1185, \f2Math. Mag. 57\f1 (1984), p. 42.
.sp
[SC] R. G. Stanton and D. D. Cowan, ``Note on a `Square' Functional
Equation,'' \f2SIAM Review\f1 \f212\f1 (1970), pp. 277-279.
.sp
[T] A. Tucker, \f2Applied Combinatorics,\f1 Wiley, New York, 1980.