Lemma 30 (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] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -3/4 x[n - 1] + 5/4 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/2 x[n] - 1/2 x[n - 1] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n] + 1/2 x[n - 1] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 5/4 x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/2 x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -3/4 x[n - 1] + 5/4 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/2 x[n] - 1/2 x[n - 1] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n] - 5/4 x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -3/2 x[n + 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -1/2 x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -3/4 x[n - 1] + 5/4 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 11/8 x[n] - 5/8 x[n - 1] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 11/8 x[n] - 5/8 x[n - 1] | <= 3/2 | x[-1] | + 3/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 3 a 5 b Let M1 be, a, Let M2 be , --- - ---, and let M3 be , a/2 - b/2 4 4 Since M1 2 M2 M3 = ---- + ---- 5 5 we have by the triangle inequality since the sum of , 1/5, and , 2/5, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 b Let M1 be, a, Let M2 be , --- - a/2, and let M3 be , a/2 - b/2 2 Since M1 M2 M3 = ---- - ---- 3 3 we have by the triangle inequality since the sum of , 1/3, and , 1/3, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 a 5 b Let M1 be, b, Let M2 be , --- - ---, and let M3 be , a/2 - b/2 4 4 Since M1 2 M2 M3 = ---- + ---- 3 3 we have by the triangle inequality since the sum of , 1/3, and , 2/3, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 a 5 b 3 b 11 b 5 a Let M1 be, --- - ---, Let M2 be , --- - a/2, and let M3 be , ---- - --- 4 4 2 8 8 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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] - x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] + 1/2 x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n + 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/8 x[n - 1] + 1/8 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -1/2 x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/2 x[n] - 1/2 x[n - 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n] + 1/4 x[n - 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | removing those inequalities that we already know, this means that we have to\ prove | 3/8 x[n - 1] + 1/8 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -1/2 x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n] + 1/4 x[n - 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | abbreviating , a = x[n - 1], b = x[n] 3 a Let M1 be, a, Let M2 be , b, and let M3 be , - --- - b/8 8 Since 3 M1 M2 M3 = - ---- - ---- 8 8 we have by the triangle inequality since the sum of , 3/8, and , 1/8, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 a 5 b 3 a Let M1 be, a, Let M2 be , --- - ---, and let M3 be , - --- - b/8 4 4 8 Since 9 M1 M2 M3 = - ---- + ---- 20 10 we have by the triangle inequality since the sum of , 9/20, and , 1/10, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 b 3 a Let M1 be, a, Let M2 be , --- - a/2, and let M3 be , - --- - b/8 2 8 Since 5 M1 M2 M3 = - ---- - ---- 12 12 we have by the triangle inequality since the sum of , 5/12, and , 1/12, 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 3 a 5 b Let M1 be, a, Let M2 be , --- - ---, and let M3 be , a/2 - b/2 4 4 Since M1 2 M2 M3 = ---- + ---- 5 5 we have by the triangle inequality since the sum of , 1/5, and , 2/5, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 b Let M1 be, a, Let M2 be , --- - a/2, and let M3 be , a/2 - b/2 2 Since M1 M2 M3 = ---- - ---- 3 3 we have by the triangle inequality since the sum of , 1/3, and , 1/3, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 a 5 b Let M1 be, b, Let M2 be , --- - ---, and let M3 be , a/2 - b/2 4 4 Since M1 2 M2 M3 = ---- + ---- 3 3 we have by the triangle inequality since the sum of , 1/3, and , 2/3, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 b Let M1 be, a, Let M2 be , b, and let M3 be , --- + a/4 4 Since M1 3 M2 M3 = ---- + ---- 4 4 we have by the triangle inequality since the sum of , 1/4, and , 3/4, is <= 1 that if |M1| and |M2| are both <=A it follows that |M3| <= A 3 b 3 b Let M1 be, a, Let M2 be , --- - a/2, and let M3 be , --- + a/4 2 4 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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n] + 1/2 x[n - 1] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] + x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 5/4 x[n] + 1/2 x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/2 x[n] + x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n - 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n] + 1/2 x[n - 1] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 5/4 x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/2 x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/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] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/4 x[n] - 5/4 x[n + 1] | <= 3/2 | x[-1] | + 3/2 | x[0] | | -3/2 x[n + 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 5/4 x[n - 1] + 1/2 x[n] | <= 3/2 | x[-1] | + 3/2 | x[0] | | 3/2 x[n - 1] + x[n] | <= 3/2 | x[-1] | + 3/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