all possible values of function

[David G.]

Let N be the set of nonnegative integers. Functions f, g: N -> N satisfy condition:
g(f(x)) = g(x) - x:
Determine all possible values of f(0).

Any suggestions gratefully received.
Thanks,
David

[Patrick Coilland]

David G. a écrit :

g(f(f(x))=g(f(x))-f(x)=g(x)-x-f(x)
g(f(f(f(x)))=g(f(x))-f(x)-f(f(x))=g(x)-x-f(x)-f(f(x))

and so on :

g(f^[n+1](x))=g(x)-x-f(x)-f(f(x))- ... - f^[n](x)

And since LHS>=0, RHS is >=0 too and so, for all x, exists n0 such that
f^[n](x)=0 for all n>n0

And so f(0)=0

[Dan Cass]

Here's another proof. Rewrite the assumption
[*] g(f(x)) = g(x) - x
in the form g(x) = x + g(f(x)).
Iterate this once and get
g(x) = x + f(x) + g(f(f(x))).
One can keep going with this iteration, and obtain that
for any x, g(x) is the sum of the iterates of f at x.
In other words
[**] g(x) = x + f(x) + f(f(x)) + f(f(f(x))) + ...
One knows that the partial sums of the series on the
right of [**] are bounded (by g(x) in fact).
Since the terms are nonnegative, they are eventually all
zero.

This shows that the function g(x) is completely determined by the function f(x).

Ex: Let f(x)=0 if x is even, and f(x)=2x if x is odd.
Then g(x) turns out to be x when x is even, and 3x
when x is odd.

Now note we must have f(0)=0, since otherwise the series
on the right of [**] when x = 0 has a positive term at
f(0) and each time an iterate hits 0 the series of terms
repeats, collecting another summand of f(0), which
makes g(0) (the left of [**]) infinite.

In fact the function f may be chosen to be any function
satisfying f(0) = 0 and satisfying that for any x
the sequence of iterates
x, f(x), f(f(x)), etc
is eventually all zeros. Then the companion function g(x)
may be determined from [**].

At first I thought there might not even be such f and g
satisfying the original relation[*]. Now I see there are
actually lots of such examples.