Periodicity, Part 1

Today (and, as my title sort of implies, later as well), we’re going to talk about 2 functions and find out if and when they are periodic. And since the data I have available, makes me believe that my thoughts on these issues are ‘different’, in the sense that most people would solve these problems in a rather different way, it would be cool to have some feedback. So if you think that I’m ‘wrong’, because an easier approach is available, do tell. I will use the notation that the n-th iteration of a function is f^n(x), which, recursively defined, is f(f^{n-1}(x)), where f^0(x) = x. If the initial value of the function doesn’t really depend on x, as is true in the function I’ll deal with today, I will just type f^n for the n- th iteration. The two functions I’ll talk about, are the following:

1) f(x) = \displaystyle \frac{2 + x}{1 - 2x}, with initial value 2.
2) f(x) = \displaystyle 1 - \left|1 - 2x\right|, with initial value x \in [0, 1]

And because today I’ll only be talking about the first f(x), there will not be any confusion, hopefully. The problem to prove is: f^n(x) won’t become periodic from some point on. This, btw, is a problem from the PEN-book. Also, since it’s been a while that I thought about this problem, I can’t really recall the things I tried, but didn’t work. So I’ll just present my solution of it in a slightly more formal manner than previous posts. Still, I’ll try to keep things really basic, so that might mean that you’ll encounter stuff that seems trivial. You can then just safely skip those parts.

Theorem. f^a = f^b implies a = b

Proof of Theorem. To proof our Theorem, we first need to show that there is no (nonnegative) integer n for which f^n = 0. To proof this last assumption, we need a few lemma’s.

Lemma 1. f^n \in Q for all n \in \aleph. (Q is the set of rational numbers)

Proof of Lemma 1. Note that f^0 = 2 \in Q. We proceed via induction. Assume f^k = \dfrac{p}{q} for some k \ge 0. Let p' = 2q + p, q' = q - 2p. Then:

f^{k+1} = f(f^k)
= \dfrac{2 + p/q}{1 - 2p/q}
= \dfrac{2q + p}{q - 2p}
= \dfrac{p'}{q'}

Lemma 2. f is injective

Proof of Lemma 2. Assume f(a) = f(b). Then:

\displaystyle \frac{2 + a}{1 - 2a} = \frac{2 + b}{1 - 2b}
(2 + a)*(1 - 2b) = (2 + b)*(1 - 2a)
2 - 4b + a - 2ab = 2 - 4a + b - 2ab
5a = 5b
a = b

Lemma 3. Since we know that f is injective, f must have an inverse. This inverse equals: f^{-1}(x) = \dfrac{x - 2}{1 + 2x}

Proof of Lemma 3. Let \dfrac{x - 2}{1 + 2x} =y. Then:

x - 2 = y + 2xy
x - 2xy = 2 + y
x(1 - 2y) = 2 + y
x = \dfrac{2 + y}{1 - 2y}
= f(y)

Note that we can use this inverse function to calculate f^n, provided we know the value of f^{n+1}. So assume k to be the smallest (nonnegative) integer for which f^{k+1} = f(f^k) = 0. Then: f^k = f^{-1}(f^{k+1})) = f^{-1}(0) = -2 = -f^0.
We’ll generalize this last equation using induction. Assume that, for some i with: k \ge i \ge 0, f^{k-i} = -f^i. Then:

f^{k-(i+1)} = f^{-1}(f(f^{k-(i+1)}))
= f^{-1}(f^{k-i})
= \dfrac{f^{k-i} - 2}{1 + 2f^{k-i}}
= \dfrac{-f^{i} - 2}{1 - 2f^{i}}
= -\dfrac{2 + f^{i}}{1 - 2f^i}
= -f^{i+1}

So we may conclude that, for every i with k \ge i \ge 0, f^{k-i} = -f^i. Now we have to consider 2 cases separately; whether k is even or odd;

Case 1) k = 2m. Then we must have f^m = -f^m, which implies that f^m = 0 and this obviously contradicts the definition of k.

Case 2) k = 2m+1. Then we must have:

f^m = -f^{m+1}
= -f(f^m)
= -\dfrac{2 + f^m}{1 - 2f^m}
f^m(1 - 2f^m) = -(2 + f^m)
f^m - 2(f^m)^2 = - 2 - f^m
2(f^m)^2 - 2f^m - 2 = 0
f^m = \dfrac{1 \pm \sqrt{5}}{2} \notin Q

So we are forced to conclude that there is no (nonnegative) integer k satisfying f^{k+1} = 0. We may now proceed to the proof of our Theorem. For this part of the proof we assume k to be the smallest (nonnegative) integer for which a different integer k’ exists such that: f^k = f^{k'}. Then we must have k = 0, because otherwise we would have: f^{k-1} = f^{-1}(f^k) = f^{-1}(f^{k'}) = f^{k'-1}, which clearly contradicts our (new) definition of k. So f^{k'} = f^k = f^0 = 2. But this too leads to a contradiction if we apply our inverse function one more time;

f^{k'-1} = f^{-1}(f^{k'})
= f^{-1}(2)
= 0

And we already proved that this equation is not solvable for k' \in \aleph. Thus we must conclude that there are no 2 different integers a and b for which: f^a = f^b. In other words: f^a = f^b implies a = b.


One Response to “Periodicity, Part 1”

  1. グッチ 店舗 Says:

    楽天ショップ一覧 グッチ 店舗

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: