QUESTION:
f(f(x)) = x4 - 4*x3 + 8*x + 2. What is f(x)?
ANSWERS:
It is easy to show that for any polynomial f(x),
f(x) - x divides f(f(x)) - x. (A fixed point argument
is nearly, but not quite enough.)
The polynomial (x^4 - 4x^3 + 8x + 2) - x factors as
(x - 2)(x + 1)(x^2 - 3x - 1). From there, we can
check cases to get f(x) = x^2 - 2x - 1.
Naoki Sato
-------------------------------------------------------------------------------
Ed,
I came across mention of a 'similar' problem in Cedric Smith's article
Early Reminiscences to celebrate the sixtieth birthday of Professor W.
T. Tutte. Smith recounted how Tutte asked Smith, Stone and Brooks (his
collaborators on 'Squaring the Square") to find "...a semiexponential
function S(x), that is, one satisfying S(S(x)) = exp x. We tried our
hands, without success, and told Tutte that we could not solve the
problem. Indeed no self-respecting mathematician could be expected to
solve an impossible problem like that, or so we thought. Whereupon he
replied "But I have a solution." He explained , as follows,.
Suppose that @ is a number such that S(@) = @, then clearly exp @ =
S(S(@)) = S(@) = @. By solving (numerically) the equation exp @ = @ we
find possible values for @, such as 0.318 + 1.337i.
Now differentiate repeatedly the defining equation S(S(x)) = exp x, to
get a sequence of equations. Substitute x = @ in these equations; we
find in turn the values of the successive derivatives S'(@),S''(@),...,
and hence the Taylor series for S(x) expanded around @.
After this, the real mathematicians looked at Tutte, the chemist, with
considerable respect.(We could not prove the Taylor series convergent.
Several years later we found out that in fact it was easy to do so,
using methods explained in E. Piccard's book, "Lecons sur Quelques
Equations Functionelles.")"
Stuart Anderson
-------------------------------------------------------------------------------
Ed,
thank you for posting my analysis of the Doppleganger Maze.
I hope the joint PDF file on the problem "f(f(x)) =...." goes in the
direction you asked for; it takes less than two pages, but 47K are needed. Of
course plain text format was unadequate to the subject; I wrote my results
using TeX, that gave a DVI file of just 10K, and I translated it into a PDF
file: I know in fact that DVI format is not so known...
(He also sent a Revised version in DVI format)
Best regards, Claudio Baiocchi
-------------------------------------------------------------------------------
Hi Ed,
Thanks for the interesting puzzle regarding the equation f(f(x)) = x^4 - 4*x^3 + 8*x + 2.
Assuming a quadratic solution for f(x) leads to three solutions (one
real, two complex) :
f(x) = w*x^2 - 2*w*x + 1 - 2*w
where w is one of the cube roots of 1.
It seems like formal power series and/or derivatives could be used to
find other solutions or rule out their existence.
Googling around, it seems most research has focused on f(f(x)) = e^x,
but a few other relevant articles are
http://www.newton.dep.anl.gov/newton/askasci/1993/math/MATH023.HTM
http://ijmms.hindawi.com/volume-30/S0161171202107150.html
http://mathforum.org/epigone/sci.math.research/swooflolglyr/Pine.GSO.4.33.0304110946150.513-100000@u52.math.uiuc.edu
Thanks,
Michael Brundage
Software Design Engineer
Xbox System Software
Microsoft
-------------------------------------------------------------------------------
Hi,
You can find some information about solving f(f(x)) = g(x) on the
following post on the Mathlinks board (you might need to register to
see the .tex attachment mentioned) :
http://www.mathlinks.ro/Forum/viewtopic.php?t=14151
(there are pointers to an article in French about the general problem
and a reference to the fact that the problem has no solution when g(x) is a
quadratic polynomial)
François Glineur
-------------------------------------------------------------------------------
Ed:
If f(f(x)) = x^4-4x^3+8x+2, then f(x)=x^2-2x-1.
There has been a lot of discussion of functional equations of this type
on sci.math. You can search sci.math from http://groups.google.com/ .
Do a search on the term f(f(x)) and you will turn up a lot of interesting
threads.
John A. Shonder
Oak Ridge National Laboratory
-------------------------------------------------------------------------------
f(f(x)) = x^4 - 4*x^3 + 8*x + 2
If f(x) is a polynomial, it is of the form f(x) = x^2 + a*x + b.
Then f(f(x)) = (x^2 + a*x + b)^2 + a*(x^2 + a*x + b) + b
= x^4 + 2a*x^3 + 2b*x^2 + a^2 * x^2 + 2ab*x + b^2 + a*x^2 + a^2 * x +
ab + b
= x^4 + 2a*x^3 + (2b + a^2 + a)*x^2 + (2ab + a^2)*x + (b^2 + ab + b)
This gives a system of equations:
2a = -4
2b + a^2 + a = 0
2ab + a^2 = 8
b^2 + ab + b = 2
From the first equation, a = -2. Then 2b = -2 so b = -1. The last two
equations say 4 + 4 = 8 and 1 + 2 - 1 = 2. So f(x) = x^2 - 2x - 1.
For any nontrivial cases this is going to give more equations than
variables, so it is likely that most problems of this sort (for random
polynomials) are not going to lead to solutions. For the case of
f(f(x)) = a quartic polynomial, the coefficients of x^4, x^3, and x^2
lead to a unique solution for the polynomial, so the coefficient of x
and the constant term need to be some specific values for this to
work.
It may be possible for there to be nonpolynomial solutions where the
nonpolynomial parts cancel out when the function is iterated, but it
doesn't seem likely.
Joseph Devincentis
-------------------------------------------------------------------------------
Howdy, Ed
For this problem, one solution can be found pretty easily. By inspection
one can assume f(x) is of the form x^2 + ax + b, equate f(f(x)) to the given
polynomial, and find f(x) = x^2 - 2x - 1.
I think there will usually be infinitely many solutions for problems of the
sort f(f(x)) = some given g(x), though of course the most interesting
solutions will have a simple form. Several years ago I played around
with various forms and found the form f(x) = (ax+b)/(cx+d) was pretty
interesting. Composition of functions of this form is the same as 2x2
matrix multiplication.
Bob Harris
-------------------------------------------------------------------------------
If f(f(x)) = x^4-4x^3+8x+2, then the only polynomial solution for f(x) is
f(x)=x^2-2x-1, which can be found easily in Mathematica, by guessing
that f must be a quadratic and solving for coefficients.
I think there would be an infinite number of solutions if you allowed
any analytic function for f.
There is a lot of research on iterated functions, but I think in
general these problems are not solvable.
I can find other solutions if I use complex numbers. Three equations to be
exact.
Chris Lomont
-------------------------------------------------------------------------------
An f(x) such that f(f(x)) is x^4 - 4*x^3 + 8*x + 2 is x^2 - 2x - 1.
I found it by supposing that it was of the form x^2+a^x+b, noticing
that a=-2 and substituting it (I worked with paper and pen, so I
wanted to reduce computation).
I do not know how to solve such equations: for example, f(f(x))=x has
at least solutions x and -x ...
--
ciao, maurizio codogno
-------------------------------------------------------------------------------
Quick answer to the problem:
f(f(x)) = x^4 - 4x^3 + 8x + 2;
f(x) = x^2 - 2x -1.
Maybe I'm overlooking something, but for this type of problem, you can
assume it's a polynomial of degree 2. So, f(x) will be of the form:
a(x^2) + b(x) + c.
Then, it's a matter of solving
a(x^2) + b(x) + c, and with x = a(x^2) + b(x) + c, it's then
(a(x^2) + b(x) + c)^2 + b(a(x^2) + b(x) + c) + c.
Expanding all of this out, set it equal to x^4 - 4x^3 + 8x + 2, and
then immediately 'a' = 1, and then 'b' = -2, and c = -1 from that. So
it seems to be just a matter of careful algebra.
I'm sure that doesn't help with the general question of solving
problems like this!
Thanks very much,
Corey Maley
University of Nebraska-Lincoln
-------------------------------------------------------------------------------
Notice the 4th degree polynomial. It seems reasonable that f(x) is
quadratic.
So try f(x)=ax^2 + bx + c
f(f(x)) = a(ax^2 + bx + c)^2 + b(ax^2 + bx + c) + c
Simplify to a polynomial in x
[a^3]x^4 + [2a^2b]x^3 + [2a^2c + ab^2 + ab]x^2 + [2abc + b^2]x + [ac^2
+
bc + c]
Coefficients must be equal, so
a^3 = 1 (From which a=1)
2a^b = -4 (From which, since a=1, b=-2)
2a^2c + ab^2 + ab = 0 (Using a=1 and b=-2, c=-1)
2abc + b^2 = 8 (which it does using a=1, b=-2, c=-1)
ac^2 + bc + c = 2 (which also does)
It seems any problem 'of this type' can be solved in this way, but I
would
hope f(f(x)) is 4th degree or less!
-Jeremy Galvagni
-------------------------------------------------------------------------------
I got this possible solution: f(x)=x^2-2x-1
I got it by turning the polynomial into this form:
(x^2-2x-1)^2-2(x^2-2x-1)-1
Are there more solutions?
Carlos Ueno.
Las Palmas de Gran Canaria
SPAIN
---------------------------------------------------------------------------------------------
I assumed f(x) = Ax^2 + Bx + C
f(f(x)) = A(Ax^2 + Bx + C)^2 + B(Ax^2 + Bx + C) + C
= (A^3)x^4 + (2BA^2)x^3 + (2CA^2 + AB^2 + AB)x^2 + (2ABC +
B^2)x + AC^2 + BC + C
A^3 = 1
A=1
2BA^2 = -4
B=-2
2CA^2 + AB^2 + AB = 0
C=-1
f(x) = x^2 - 2x - 1
--
Nathan Stohler
Member of Technical Staff
Lucent Technologies, Inc.
-----------------------------------------------------------------------------------------------
I spent longer thinking about this problem then I planned to, so it's a
good thing that it's Thanksgiving break and I don't need to wake up
particularly early:
f(f(x)) = x^4 - 4x^3 + 8x + 2; what is f(x)?
First off, I assumed that, because we have a nice polynomial with
integer exponents and the highest power is x^4, f(x) can be expressed
as f(x) = ax^2 + bx + c, so:
f(f(x)) = a(ax^2 + bx + c)^2 + b(ax^2 + bx + c) + c
f(f(x)) = a(a^2*x^4 + abx^3 + acx^2 + abx^3 + b^2*x^2 + bcx + acx^2 +
bcx + c^2) + b(ax^2 + bx + c) + c
f(f(x)) = a^3*x^4 + a^2*bx^3 + a^2*cx^2 + a^2*bx^3 + ab^2*x^2 + abcx +
a^2*cx^2 + abcx + ac^2 + abx^2 + b^2*x + bc + c
f(f(x)) = a^3*x^4 + (a^2*b+a^2*b)x^3 + (a^2*c + ab^2 + a^2*c + ab)x^2 +
(abc + abc + b^2)x + (ac^2 + bc + c)
f(f(x)) = Dx^4 + Ex^3 + Fx^2 + Gx + H, where D = a^3, E = 2a^2*b, F =
2a^2*c + ab^2 + ab, G = 2abc + b^2, and H = ac^2 + bc + c.
Since f(f(x)) = x^4 - 4x^3 + 8x + 2 is given, equating coefficients
gives a system of five equations with three variables:
a^3 = 1
2a^2*b = -4
2a^2*c + ab^2 + ab = 0
2abc + b^2 = 8
ac^2 + bc + c = 2
Solving the first equation gives a = 1 (which was pretty obvious from
the given coefficients, but I wanted to be thorough), putting a = 1
into the second equation gives b = -2, and putting both a = 1 and b =
-2 into the third equation gives c = -1, so:
f(x) = x^2 - 2x - 1
The other two equations also check out with the values of a, b, and c,
and evaluating f(f(x)) with f(x) = x^2 - 2x - 1 gives the correct
answer of x^4 - 4x^3 + 8x + 2.
Ili Butterfield
------------------------------------------------------------------------------
This was surprisingly easy for someone who remembers his high-school
algebra. I assumed the equation desired was of the form (x^2) + (Y * x) +
Z. If f(x) = (x^2) + (Y * x) + Z, then
f(f(x)) = (((x^2) + (Y * x) + Z) ^ 2) + Y * ((x^2) + (Y * x) + Z) + Z
= ((x^4) + (2Y * (x^3)) + (((Y^2) + 2Z) * (x^2)) + (2YZ * x) +
(Z^2)) + ((Y * (x^2)) + ((Y^2) * x) + 2Y) + Z
= (x^4) + (2Y * (x^3)) + (((Y^2) + Y + 2Z) * (x^2)) + (2YZ +
(Y^2) + Z) * x) + ((Z^2) + 2Y + Z)
Since we have f(f(x)) = (x^4) - (4 * (x^3)) + (8 * x) + 2, then 2Y = -4,
whence Y = -2.
Simplifying the above equation,
f(f(x)) = (x^4) - (4 * (x^3)) + ((2 + 2Z) * (x^2)) + ((4 - 4Z) * x) + ((Z^2) - Z)
From the coefficient of 0 for (x^2) in the given equation, 2 + 2Z = 0, whence Z = -1.
Checking the other coefficients, we should have 4 - (4*(-1)) = 8 and
((-1^2) - (-1)) = 2. Since they check, the solution is f(x) = (x^2) - (2 * x) - 1.
I'd like to add, I came up with the general equation for f(f(x)) if
f(x) is a quadratic equation. If f(x) = (x^2) + Ax + B, then
f(f(x)) = (x^4) + 2A(x^3) + ((A^2) + A + 2B)(x^2)) + (2AB + (A^2))x +
((B^2) + AB + B).
From the coefficient of x^3, you can always find A, and use that and
the coefficient of x^2 to find B. The coefficient of x and the constant, of
course, should check if your values of A and B are a solution.
Darrel C Jones
------------------------------------------------------------------------------
f(x) = x^2 - 2x - 1
Attached is the explanation as well as some discussion regarding these types of problems.
Please let me know what you think. I have a passion for mathematics but have little
time to explore it. I have a degree in mathematics but have been working as a software
engineer for the last ten years.
Thanks,
Will Smith
------------------------------------------------------------------------------
Hi Ed
The solution to the f(f(x)) puzzle is F(x) = x^2 - 2x - 1
Starting with F(x) = ax^2 +bx + c
ffx becomes Px^4 + Qx^3 + Rx^2 + Sx + T
where
P = a^3
Q = 2ba^2
R = 2ca^2+ab^2 + ab
S = 2abc + b^2
T = ac^2 + bc + c
equating PQRST to the terms in ffx = x^4 - 4x^3 + 8x + 2 it is simple
to show that
a = 1
b = -2
c = -1
Rgdz
Pete Kogel
------------------------------------------------------------------------------
Hi!
If you assume the solution is f(x)=ax^2+bx+c, doing the math leads to f(x)=x^2-2x-1,
but I found an easier (?) way.
Differentiating with regard to x, we get f'(f(x)).f'(x)= 4x^3-12x^2+8= (x^2-2x-2)(x-1).
Since f(x) seemed to be a quadratic, f'(x) could be proportional to (x-1), and thus f(x)
proportional to x^2-2x+c. Since it is obvious that the coefficient of the leading term
should be 1 (so f(f(x)) gets an x^4 term), all that remains is finding c. Setting x=0,
f(f(0))= f(c)= 2, so c^2-2c+c=2, and c=2 or c=-1; the second value produces the
correct answer.
Best regards,
Federico Kereki
--------------------------------------------------------------------------------
f(x) = x^2 - 2*x - 1
I found this by observing that the leading term had to be x^2,
so I set f(x) = x^2 + b*x + c and expanded f(f(x)), then matched
coefficients of each power of x from highest order down to
determine the parameters b and c.
Doug Gwyn
--------------------------------------------------------------------------------
Hi,
I'm sending you the solution for composite function based problem;
Given that f(f(x)) = x^4 - 4*x^3 + 8*x + 2; we have to find f(x);
By seeing f(f(x)) we can assume that f(x) is polynomial of degree n.
say f(x) = sum (Pi * x^i) | where i varies from 0 to n.
then f((fx)) will also be a polynomial of degree n^n.
In our case f(f(x)) is of degree 4, hence n^n = 4 => n =2;
Hence we can assume that f(x) = P0*x^2 + P1*x + P2;
Now we can express f(f(x)) in terms of P0,P1 and P2;
After expressing f(f(x)) in terms of P0, P1 and P2 we can compare it
with the given function and hence find the solution.
I guess this is a generic method of finding solutions for such problems
Any comments on this will be fully accepted and analyzed.
Regards
Punit Kishore
--------------------------------------------------------------------------------
Hi Ed,
With regard to the puzzle
f(f(x)) = x^4-4*x^3+8*x+2, I think that f(x)=x^2-2*x-1.
Mark Hudson
------------------------------------------------------------------------------
The function f(x) such that f(f(x)) = x^4 - 4x^3 + 8x + 2 is :
x^2 - 2x -1
I'm not sure about anything wrote about the subject since I came up
with my own method, If your interested about my method, I'd be happy to explain
:)
many thanks Leigh Shepperson
-------------------------------------------------------------------------------
Hi,
It's just a series of N equations with N unknowns as far as I can see.
Answer: X^2 - 2x -1.
Pierre Baillargeon
-------------------------------------------------------------------------------
f(x)=x^2-2x-1
Thanks for mentioning Google Scholar, it's wonderful! Earl Gose
-------------------------------------------------------------------------------
FROM SCI.MATH
From: Zdislav V. Kovarik
Subject: Re: "Halfway-functions"
View: Complete Thread (15 articles)
Original Format
Newsgroups: sci.math
Date: 2002-07-06 15:50:07 PST
Punchline: Suppose a>=0, then for f(x) = a * x + b, a half-way
function is
h(x) = x*sqrt(a) + b/(1+sqrt(a))
Explanation below.
On 6 Jul 2002, Joona I Palaste wrote:
: Here is a simple question which can be very
: difficult to answer. Is there, for every
: function f: R->R, a "halfway function" h: R->R,
: so that h(h(x))=f(x)?
This is quite classical (Abel worked on this); a
discussion can be found in
Marek Kuczma: Functional Equations in a Single
Variable
Polish Scientific Publishers, Warsaw 1968
and other, newer books, one written by Kuczma
as a co-author (I don't have it here).
: And furthermore, if the
: answer is yes, then, for every function that is
: expressible as a combination of elementary
: operations and functions, is the "halfway
: function" also expressible as a combination of
: elementary operations and functions?
:
Very unlikely: even something like f(x) = x + x^3
refuses to have an elementary "compositional
square root" (I don't have a proof, but I tried
hard :-(), although a real-analytic solution
is possible.
: I have myself tested some very trivial cases.
: If f(x)=x+a, then h(x)=x+a/2.
: If f(x)=x*a, where a is non-negative, then
: h(x)=x*sqrt(a).
: If f(x)=x*a, where a is negative, we can't easily
: have h: R->R, but we can have h: C->C,
: h(x)=x*sqrt(a), and f(x) ends up being in
: R if x is in R, even if h(x) is not in R.
: But if f(x)=x*a+b, where a is neither 0 or 1, and
: b is not 0, then h(x) is too difficult to find in
: the short time it took me to write this article.
: I haven't even been able to prove such a function
: exists.
:
: Can anyone help me on this? Any answers will be
: appreciated, thanks.
So: if a is not 1 then the function the function
f(x)=a*x+b has a fixed point w, that is, w satisfies
w = a * w + b
Namely, w = b / (1 - a).
Next, when in trouble, change the variable. In our
situation, set x = y(0) + w, f(x) = y(1) + w
(where the index (0) and (1) "counts" the iterations)
so
y(1) + w = a * (y(0) + w) + b
and simplify, remembering that w is a fixed point:
y(1) = a * y(0)
Now the half-way iteration offers itself (and you knew it):
y(1/2) = sqrt(a) * y(0)
Put into original variables: h(x) = y(1/2) + w becomes
h(x) = (x - w) * sqrt(a) + w
and after simplification, you end up with what I wrote on top
of my reply. The simplification actually allows to drop
the restriction that a be not 1.
Kuczma's book has answers and references to fractional
iterations of many other functions, such as exp(x).
Cheers, ZVK(Slavek).