In One Sequence Or Another (counter-intuitive?)

[Leroy Quet]

I have found a visual and more intuitive way of showing the result below.

But first I must say that floor(f(1)) need not necessarily be 1, so it IS 
possible to represent every sequence of distinct positive integers by 
either
{floor(f(k)) + k}
or
{ceiling(g(k)) + k -1}

for an infinite number of functions f (or g).


Basic idea behind visual proof:

First, f is a monotonically increasing function
where 0 < f(w) < 1 for some w, 0 < w < 1.

Overlay f on a grid (of unit-distance between consecutive grid-lines), 
and then shade in each grid-square in which f passes through.
Call the chain of squares which approximates f's shape a "grid-path".

So, if we were to label, in order starting from the square nearest the 
origin, the squares in the grid-path with 1, 2, 3, 4, 5, 6,...

then all integers of the form

floor(f(k)) + k

would be at the top-most squares of each vertical section of the 
grid-path;

and all integers of the form

ceiling(g(k) + k - 1

would be a the right-most squares of each horizontal section of the 
grid-path.

(I am assumming that the path is tending up and to the right.)

Since every square in the path is either a right-most square or an 
upper-most square, but not both, every positive integer is either

floor(f(k)) +k
or 
ceiling(g(k)) +k-1.

(Unrigorous, yes.)

thanks,
Leroy Quet


>[Based upon a post to sci.math] 
>
>I came up with the following result, which must be well known, today.
>If we let f and g be certain functions, we can get 2 integer sequences 
>for each f (and g), where every positive integer is in one of these 
>sequences or the other, but not in both.
>(a possible source for sequences...)
>
>
>Let f(x) be ANY real -> real function which is defined for all x >= 1, is 
>continuous, is strictly monotonically increasing, and where floor(f(1)) = 
>1.
>
>Let g(x) the inverse of f(x) -- ie. g(x) is subject to the same 
>conditions as f(x), ceiling(g(1)) = 1, 
>and f(g(x)) = x for all x >= 1.
>
>
>Then:
>
>EVERY positive integer m is representable as either
>(but not as both):
>
>
>m = floor(f(k)) + k
>
>or  
>
>m = ceiling(g(k)) + k - 1
>
>
>for some k.
>
>(One k for each integer.
>So each m is represented once and only once by either of the above.)
>
>
>(And if g(k) is not an integer, we can replace the latter with:
>
>m = floor(g(k)) +  k,
>
>obviously.)  
> 
>
>(I find the general result counter-intuitive and {although simple and not 
>too advanced} amazing.)
> 
>
>-
>
>For example, this result is a generalization of that relating to Beatty 
>sequences, which can be found at:
>
>http://mathworld.wolfram.com/BeattySequence.html
>
>(A Beatty sequence has f(k) = (y-1)*k for an irrational y {y>1}.)
>
>-
>
>Another example:
>
>f(k) = sqrt(k) *(sqrt(5)+1)/2,
>g(k) = k^2 *(3 -sqrt(5))/2.
>
>floor(f(k)) +k : 2, 4, 5, 7, 8, 9,...
>
>floor(g(k)) +k : 1, 3, 6, 10, 14,...
>
>Are either of these in the EIS?
>
>I wonder which sequences can be represented as resulting from a specific 
>f or g.
>
>We can not find a function for any positive integer sequence of distinct 
>terms, because 1 is automatically in the g-sequence,
>and 2 is automatically in the f-sequence.
>But WHICH sequences can be represented by SOME f and g?
>
>
>Thanks,
>Leroy Quet