Navigation Panel: (IMAGE)(IMAGE)(IMAGE)(IMAGE) (SWITCH TO TEXT-ONLY VERSION) (IMAGE)(IMAGE) (These buttons explained below)


Question Corner and Discussion Area

Solution to a Functional Equation

Asked by Aryan Ghirati, student, Kherad on October 6, 1997:
Is there a function f from N (the set of natural numbers) to itself, such that such that  (IMAGE) (the composition of f with f) sends every n to  (IMAGE) ?
Yes, there is such a function. All such functions arise through the following type of construction:

Let C denote the set  (IMAGE) . Subdivide the rest of the natural numbers (those that are not in C) into two disjoint sets A and B, in any way you like, except that you need to have infinitely many numbers in each of the two sets. (For example, you could list the numbers that are not in C: 2,3,5,6,7,. . . . Then let the set A consist of the first number in this list, the third number in this list, and so on, while B consists of the second number in this list, the fourth number in this list, and so on).

Enumerate the numbers in A, calling them  (IMAGE) . Similarly, enumerate the numbers in B, calling them  (IMAGE) .

Now define f on the sets A and B by defining  (IMAGE) and  (IMAGE) . (Note that f maps A to B and maps B to C).

Define f on the set C by setting f(1)=1 and, for all n>1, define  (IMAGE) .

If n is in A or B, this definition is well-defined, for we have already defined f(n), and the above formula tells us how to define  (IMAGE) .

If n is in C, the way we make this definition correct is to think of it as an inductive definition: assume we have already defined  (IMAGE) for all m < n and are now trying to define  (IMAGE) . In the case in which n happens to be in C, that means  (IMAGE) and it is easy to verify that m < n, hence  (IMAGE) has already been defined, and we get an inductive definition of  (IMAGE) in terms of it.

The function f has now been defined for all natural numbers. It remains to show that  (IMAGE) for all n. There are three cases.

Case 1: n is in A. Then  (IMAGE) for some i. We then have  (IMAGE) as required.

Case 2: n is in B. Then  (IMAGE) for some i. We then have  (IMAGE) as required.

Case 3: To prove that  (IMAGE) for all n in C, suppose to the contrary that there are some n in C for which  (IMAGE) . Let n=N be the smallest of these. We know N>1, since  (IMAGE) We also know N is in C, so  (IMAGE) for some m, and clearly m < N (the only time  (IMAGE) is when m=1, and we know that our number N is greater then 1).

Either m is in A, or it is in B, or it is in C but is smaller than N, and in all three of these cases we already know  (IMAGE) It follows that  (IMAGE) . This contradicts our choice of N as being the smallest counterexample to  (IMAGE) , showing that no counterexample exists, and hence f has the desired property.

You can also prove that all functions with this property are given by a construction of the above form. Assume we have such a function f. The first thing to note is that f must satisfy the property  (IMAGE) for all n, since  (IMAGE)

Now, let C be the same set as above, and divide the numbers that are not in C into two classes, A and B, where A is the set of x not in C for which f(x) is not in C, and B is the set of x not in C for which f(x) is in C.

One can prove that f sets up a one-one correspondence from A to B, as follows: if x is in A, we know f(x) is not in C, but  (IMAGE) which is in C, proving that f(x) is in B. This proves that f maps A into B.

This mapping is one-to-one: if f(x)=f(y), then f(f(x))=f(f(y)), so  (IMAGE) , and it's easy to verify that for natural numbers this only happens when x=y.

This mapping is onto: every element  (IMAGE) is obtained as f(a) for some  (IMAGE) . This is because f(b) is in C, so  (IMAGE) for some a, and  (IMAGE) from which it follows that b=f(a).

So, if you label the elements of A as  (IMAGE) and define  (IMAGE) , then f is precisely the function defined above, since  (IMAGE) (by definition),  (IMAGE) (by the argument of the previous paragraph), and for every element  (IMAGE)  (IMAGE) . This is precisely the definition given above.

[ Submit Your Own Question ] [ Create a Discussion Topic ]

This part of the site maintained by (No Current Maintainers)
Last updated: April 19, 1999
Original Web Site Creator / Mathematical Content Developer: Philip Spencer
Current Network Coordinator and Contact Person: Joel Chan -


(IMAGE) Go backward to Solving a Quadratic with Non-Constant Coefficients
(IMAGE) Go up to Question Corner Index
(IMAGE) Go forward to Largest Possible Number?
 (SWITCH TO TEXT-ONLY VERSION) Switch to text-only version (no graphics)
(IMAGE) Access printed version in PostScript format (requires PostScript printer)
(IMAGE) Go to University of Toronto Mathematics Network Home Page