req proof regarding A196

[Max A.]

On 8/26/06, Joseph Biberstine <jrbibers at indiana.edu> wrote:

> Begin with t=n and an empty list L and, while, t>0 append
> floor(sqrt(t)) to L and set t=t-floor(sqrt(t)).  This gives the list
> intended.  The request for a proof stands.

[...]

>         Relevant related sequences seem to be A196 (number of runs in L(n)),

The number of runs is simply [sqrt(n)] (that is A196). In other words,
L contains all the integers from floor(sqrt(n)) to 1. That easily
follows from the inequality:
sqrt(n-[sqrt(n)]) >= [sqrt(n)] - 1
meanning that each number in L can be smaller than its predecessor by at most 1.

Indeed, if m = [sqrt(n)] then n >= m^2 >= m^2 - m + 1 implying
n - m >= m^2 - 2m + 1
and
sqrt(n - m) >= m - 1.

> A267 (length of L(n)),

Let a(n) be the length of L(n).
I will show by induction on n that a(n) = A000267(n-1) = [sqrt(4n-3)].

For n=1, the statement is trivial.
Suppose that for all k<n, a(k) = [sqrt(4k-3)].

Let q = [sqrt(4n-3)]. Then [sqrt(n)] = [q/2], except for a special
case of 4n=(q+1)^2 with [sqrt(n)]=(q+1)/2 which we will address
latter.
The definition of q implies
q^2 <= 4n - 3 < q^2 + 2q + 1
Viewing numbers modulo 4 this inequality takes a stronger form:
q^2 <= 4n - 3 < q^2 + 2q - 2             (*)
By the definition of a(n),
a(n) = 1 + a(n-[sqrt(n)]) = 1 + [sqrt(4n-4[q/2]-3)]
and we need to show that
q = 1 + [sqrt(4n-4[q/2]-3)]
or, equivalently,
q-1 <= sqrt(4n-4[q/2]-3) < q,
q^2 - 2q - 1 <= 4n-4[q/2]-3 < q^2,
q^2 - 2(q-2[q/2]) - 1 <= 4n - 3 < q^2 + 4[q/2]
that immediately follows from (*).

Finally, suppose that q is odd and 4n=(q+1)^2. Then [sqrt(n)] = (q+1)/2.
By the definition of a(n),
a(n) = 1 + a(n-[sqrt(n)]) = 1 + [sqrt((q+1)^2-2(q+1)-3)]
= 1 + [sqrt(q^2 - 4)] = 1 + (q - 1) = q
as required.

Max