Lemma 32 (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] | + | 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] | + | x[0] | | x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n] | <= | x[-1] | + | x[0] | | -x[n - 1] + x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n] | <= | x[-1] | + | x[0] | | x[n - 1] + x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n + 1] | <= | x[-1] | + | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n] | <= | x[-1] | + | x[0] | | 1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + | 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] | + | 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] | + | x[0] | | x[n + 1] | <= | x[-1] | + | x[0] | | x[n] - x[n + 1] | <= | x[-1] | + | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n] | <= | x[-1] | + | x[0] | | -1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + | x[0] | | 1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + | 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] | + | x[0] | | 1/2 x[n - 1] + 1/2 x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n] | <= | x[-1] | + | x[0] | | -x[n - 1] + x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n + 1] | <= | x[-1] | + | x[0] | | x[n] + x[n + 1] | <= | x[-1] | + | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n - 1] | <= | x[-1] | + | x[0] | | x[n] | <= | x[-1] | + | x[0] | | -x[n - 1] + x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n] | <= | x[-1] | + | x[0] | | x[n - 1] + x[n] | <= | x[-1] | + | 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] | + | x[0] | | x[n + 1] | <= | x[-1] | + | x[0] | in terms of x[n-1],x[n], we have to prove that | x[n] | <= | x[-1] | + | x[0] | | x[n - 1] + x[n] | <= | x[-1] | + | 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