x f(y) + y f(x) = (x+y) f(x^2 + y^2)
Boyagida
N = {0,1,2,3 , ..... }.
Let's consider the following problem.
Prove that:
If f : N -> N is a function such that:
x f(y) + y f(x) = (x+y) f(x^2 + y^2)
then f is constant.
The proof of this is :
Assume f is not constant. and suppose f(b) - f(a) is the minimal value among
all values f(y) - f(x) > 0 .
then
(a+b) f(b) > a f(b) + b f(a) > (a+b) f(a)
Dividing by (a+b), we have,
f(b) > f(a^2+b^2) > f(a)
then, 0 < f(a^2 + b^2) - f(a) < f(b) - f(a).
This contradicts the minimality of f(b) - f(a)
QED
I can follow the logic of this proof, but I don't know how he could
construct this simple proof.
I look at this proof, and I see just the _result_ of his effort to prove it.
What do you think led him to find this proof?
[ If some sentence is incorrect in grammar or semantic or spelling, you may
correct me, it will help me to improve my English ]
Jon Haugsand
> N = {0,1,2,3 , ..... }.
>
> Let's consider the following problem.
>
> Prove that:
> If f : N -> N is a function such that:
> x f(y) + y f(x) = (x+y) f(x^2 + y^2)
> then f is constant.
>
> The proof of this is :
>
> Assume f is not constant. and suppose f(b) - f(a) is the minimal value among
> all values f(y) - f(x) > 0 .
> then
> (a+b) f(b) > a f(b) + b f(a) > (a+b) f(a)
> Dividing by (a+b), we have,
> f(b) > f(a^2+b^2) > f(a)
> then, 0 < f(a^2 + b^2) - f(a) < f(b) - f(a).
> This contradicts the minimality of f(b) - f(a)
> QED
>
> I can follow the logic of this proof, but I don't know how he could
> construct this simple proof.
> I look at this proof, and I see just the _result_ of his effort to prove it.
> What do you think led him to find this proof?
Well, the first step is obvious. If you want to prove something,
assume the opposite, play around and see if you get into some
contradiction.
Therefore you assume that there are at least two points, a and b that
make the function not constant.
The genious task is to play around with the two values a and b that
make f(a)-f(b) minimal. But this is something often done with
functions (or mappings) on the natural numbers. The rest of the proof
is pure manipulation in order to use the definition of f.
Here is something for you: Given two naturals a and b, both > 1.
Prove that there exists x and y, integers, such that the greatest
common divisor of a and b, called d is equal to ax+by, i.e:
d=gcd(a,b)=ax+by
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 95 21 52
Bill Dubuque
>
> Let N = {0,1,2,3,...}. Consider the following problem.
> Prove that if f : N -> N is a function such that
> x f(y) + y f(x) = (x+y) f(x^2 + y^2) then f is constant.
>
> The proof of this is :
>
> Assume f is not constant. and suppose f(b) - f(a) is
> the minimal value among all values f(y) - f(x) > 0.
> Dividing by (a+b), we have, f(b) > f(a^2+b^2) > f(a)
> This contradicts the minimality of f(b) - f(a) QED
>
> I can follow the logic of this proof, but I don't know
> how he could construct this simple proof. I look at
> this proof, and I see just the _result_ of his effort to
> prove it. What do you think led him to find this proof?
The identity for f shows: if f takes at least two values,
say f(a) < f(b), then f takes a value between the two,
namely (b f(a) + a f(b))/(a+b) = f(a^2+b^2), hence the
values of f are dense, contra to N being discrete. QED
Note that the inequality
b f(a) + a f(b)
f(a) < --------------- < f(b) if f(a) < f(b), a>0, b>0
a + b
is a special case of
X < (1-t) X + t Y < Y, if X < Y, t>0, t<1
i.e. the above middle term is on the "line" between X and Y.
Also, the proof as written fails if a or b is 0, but it is
easily remedied since f(0) = f(1) (put x = 0, y = 1), so
that we may assume a,b nonzero (or set N = {1,2,3,...} ).
That N is discrete and not dense is a nice way to recast many
induction or infinite descent proofs, e.g. irrationality proofs:
From: Bill Dubuque <w...@zurich.ai.mit.edu>
To: historia-...@chasque.apc.org
Subject: Re: [HM] sqrt(2) and reductio
Date: Sat, 16 Jun 2001 19:38:40 -0400
Below is one of my favorite irrationality proofs. It vividly
highlights the importance of the notion of algebraic integer,
and works by contrasting the DISCRETENESS of a ring of integers
versus the DENSENESS of a ring of fractions. I have presented
the proof in a very simple form - high-school algebra suffices.
Has anyone seen this proof before? If so, what is its history?
THEOREM. Let Z denote the integers. If an integer b in Z
has a rational sqrt: sqrt(b) = c/d, then c/d is an integer.
PROOF. Suppose, as hypothesized, w = sqrt(b) = c/d is rational.
d is a common denominator for all elts in the ring R = Z[w]
since if r = m + nw in R, m,n in Z, dr = dm + n(dw) is in Z
via dw = c in Z. So R is a subset of Z/d, i.e. every r in R
has form n/d for an integer n. Suppose r = n/d is nonintegral.
We will show this leads to a contradiction and, hence, that
every r in R = Z[w] must be an integer, including w = sqrt(b).
W.l.o.g we may assume 0 < r < 1 by taking the fractional part
of |r|, since this too lies in R and is nonintegral iff r is.
Since r has form n/d and 0 < r < 1, r is a member of the
finite set { 1/d, 2/d,...,(d-1)/d }. If r is the smallest
elt of R in this set then r^2 is an even smaller such elt
since 1 > r > r^2 > 0, contradicting the minimality of r. QED
This proof works for any algebraic *integer*, i.e. a root of
p(w) = w^n + a w^(n-1) + b w^(n-2) + ... + k, a,b,..,k in Z,
using d^(n-1) versus d as a common denominator for Z[w].
It proves any rational algebraic integer is an integer (in Z).
The proof above is simply the special case p(w) = w^2 - b.
Note the subtlety here. The proof depends crucially on the fact
that w is an algebraic *integer*, which implies that the ring
Z[w] = Z<1,w,w^2,..,w^(n-1)> is a finite dim Z-module, i.e.
w^n, w^(n+1),.. are Z-linear combin's of 1, w, w^2,.., w^(n-1)
This needn't be true if w is a root of a poly p(w) whose leading
coef c is not unity since then w^n = -1/c (a w^(n-1) + ... + k)
so that c may intrude as a nontrivial denominator when using this
equation to rewrite w^n, w^(n+1),... after multiplying two elts.
Essentially the proof shows that if R > Z is an ordered ring
extension which adjoins a new finite element then R is dense,
having infinite descending chains 1 > r > r^2 > r^3 > .. > 0
in a nbhd of 0 (hence everywhere by an additive shift), where
r > 0 is the fractional part of any newly adjoined finite elt.
But Z/d is discrete, not dense, hence the contradiction.
Note that I say "finite" above because it is possible to adjoin
infinite elts alone, e.g. consider Z[x] with x infinite, i.e.
poly's in a nbhd of positive infinity = +oo, ordered by declaring
p(x) > q(x) iff this holds true eventually for all large x > 0,
i.e. in a nbhd of +oo. This is same as declaring p(x) positive
or negative as is its leading coef (the leading term eventually
dwarfs others as x-> +oo), and p > q <=> p - q > 0, as usual.
This ordered ring extension of Z adjoins no new finite elements.
However, if we additionally adjoin the infinitesimal 1/x then
we have 1 > 1/x > 1/x^2 > ... > 0, and adding c shifts this
infinitely descending chain to the nbhd of any elt c in Z[x,1/x].
Source: http://mathforum.org/epigone/historia_matematica/gosneyah/E15BPeK-...@nestle.ai.mit.edu
-Bill Dubuque