Lemma 20 (by Shalosh B. Ekhad):
Let F be the recurrence x[n+1]=F(x[n],x[n-1]) where
if x[n-1] and x[n] mod 2 are, 1, 1, respectively then
x[n + 1] = 1/2 x[n - 1] - 1/2 x[n]
if x[n-1] and x[n] mod 2 are, 1, 0, respectively then
x[n + 1] = -x[n - 1] - x[n]
if x[n-1] and x[n] mod 2 are, 0, 1, respectively then
x[n + 1] = -x[n - 1] + x[n]
if x[n-1] and x[n] mod 2 are, 0, 0, respectively then
x[n + 1] = -1/2 x[n - 1] - 1/2 x[n]
----------------------------------------------------
The following inequality holds: , | x[n] | <= | x[-1] | + 2 | x[0] |
---------------------------------------------------------
Proof (by S. B. Ekhad): To facilitate an inductive argument, we need
the following stronger statement.
Stronger Lemma:
If x[n-1] and x[n] mod 2 are , 1, 1, resp.
then the following inequalities are true
| x[n - 1] | <= | x[-1] | + 2 | x[0] |
| x[n] | <= | x[-1] | + 2 | x[0] |
-------
If x[n-1] and x[n] mod 2 are , 1, 0, resp.
then the following inequalities are true
| x[n - 1] | <= | x[-1] | + 2 | x[0] |
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n - 1] + x[n] | <= | x[-1] | + 2 | x[0] |
| 2 x[n] + x[n - 1] | <= | x[-1] | + 2 | x[0] |
-------
If x[n-1] and x[n] mod 2 are , 0, 1, resp.
then the following inequalities are true
| x[n - 1] | <= | x[-1] | + 2 | x[0] |
| x[n] | <= | x[-1] | + 2 | x[0] |
| -x[n - 1] + x[n] | <= | x[-1] | + 2 | x[0] |
-------
..................
Proof of the Stronger Lemma:
If right now x[n-1] and x[n] mod 2 are, resp., 1, 1
The induction hypothesis tells us that
| x[n - 1] | <= | x[-1] | + 2 | x[0] |
| x[n] | <= | x[-1] | + 2 | x[0] |
--------------------------------------
After applying F, we arrive at one of the following states
x[n],x[n+1] mod 2 are, resp. , 1, 1
x[n],x[n+1] mod 2 are, resp. , 1, 0
If x[n] and x[n+1] mod 2 are, resp., 1, 1, we have to prove
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n + 1] | <= | x[-1] | + 2 | x[0] |
in terms of x[n-1],x[n], we have to prove that
| x[n] | <= | x[-1] | + 2 | x[0] |
| -1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + 2 | x[0] |
removing those inequalities that we already know, this means that we have to\
prove
| -1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + 2 | x[0] |
abbreviating , a = x[n - 1], b = x[n]
Let M1 be, a, Let M2 be , b, and let M3 be , a/2 - b/2
Since
M1 M2
M3 = ---- - ----
2 2
we have by the triangle inequality
since the sum of , 1/2, and , 1/2, is <= 1
that if |M1| and |M2| are both <=A
it follows that
|M3| <= A
If x[n] and x[n+1] mod 2 are, resp., 1, 0, we have to prove
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n + 1] | <= | x[-1] | + 2 | x[0] |
| x[n] + x[n + 1] | <= | x[-1] | + 2 | x[0] |
| 2 x[n + 1] + x[n] | <= | x[-1] | + 2 | x[0] |
in terms of x[n-1],x[n], we have to prove that
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n - 1] | <= | x[-1] | + 2 | x[0] |
| 1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + 2 | x[0] |
| -1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + 2 | x[0] |
removing those inequalities that we already know, this means that we have to\
prove
| 1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + 2 | x[0] |
| -1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + 2 | x[0] |
abbreviating , a = x[n - 1], b = x[n]
Let M1 be, a, Let M2 be , b, and let M3 be , - a/2 - b/2
Since
M1 M2
M3 = - ---- - ----
2 2
we have by the triangle inequality
since the sum of , 1/2, and , 1/2, is <= 1
that if |M1| and |M2| are both <=A
it follows that
|M3| <= A
Let M1 be, a, Let M2 be , b, and let M3 be , a/2 - b/2
Since
M1 M2
M3 = ---- - ----
2 2
we have by the triangle inequality
since the sum of , 1/2, and , 1/2, is <= 1
that if |M1| and |M2| are both <=A
it follows that
|M3| <= A
This concludes the proof of the case where x[n-1] and x[n] mod 2 are,resp., 1,
1
..........
If right now x[n-1] and x[n] mod 2 are, resp., 1, 0
The induction hypothesis tells us that
| x[n - 1] | <= | x[-1] | + 2 | x[0] |
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n - 1] + x[n] | <= | x[-1] | + 2 | x[0] |
| 2 x[n] + x[n - 1] | <= | x[-1] | + 2 | x[0] |
--------------------------------------
After applying F, we arrive at the following state
x[n],x[n+1] mod 2 are, resp. , 0, 1
If x[n] and x[n+1] mod 2 are, resp., 0, 1, we have to prove
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n + 1] | <= | x[-1] | + 2 | x[0] |
| x[n] - x[n + 1] | <= | x[-1] | + 2 | x[0] |
in terms of x[n-1],x[n], we have to prove that
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n - 1] + x[n] | <= | x[-1] | + 2 | x[0] |
| 2 x[n] + x[n - 1] | <= | x[-1] | + 2 | x[0] |
But these are all repeats of the already known inequalities
This concludes the proof of the case where x[n-1] and x[n] mod 2 are,resp., 1,
0
..........
If right now x[n-1] and x[n] mod 2 are, resp., 0, 1
The induction hypothesis tells us that
| x[n - 1] | <= | x[-1] | + 2 | x[0] |
| x[n] | <= | x[-1] | + 2 | x[0] |
| -x[n - 1] + x[n] | <= | x[-1] | + 2 | x[0] |
--------------------------------------
After applying F, we arrive at the following state
x[n],x[n+1] mod 2 are, resp. , 1, 1
If x[n] and x[n+1] mod 2 are, resp., 1, 1, we have to prove
| x[n] | <= | x[-1] | + 2 | x[0] |
| x[n + 1] | <= | x[-1] | + 2 | x[0] |
in terms of x[n-1],x[n], we have to prove that
| x[n] | <= | x[-1] | + 2 | x[0] |
| -x[n - 1] + x[n] | <= | x[-1] | + 2 | x[0] |
But these are all repeats of the already known inequalities
This concludes the proof of the case where x[n-1] and x[n] mod 2 are,resp., 0,
1
..........
Quod Erat Demonstrandum