Theorem: Let F(n) be the maximum number of 1's that an n-letter word in the alphabet {0,1} avoiding the generalized patterns {[1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 2, 1, 2, 2, 1]} may have , i.e. any n-letter word in {0,1} with F(n)+1 1's MUST contain at least one of these patterns. [Here 2 denotes either 0 or 1]. We have the following explicit expression for F(n) as a piece-wise linear discrete function F(8 m + 1) = 4 m + 1 F(8 m + 2) = 4 m + 2 F(8 m + 3) = 4 m + 2 F(8 m + 4) = 4 m + 3 F(8 m + 5) = 4 m + 4 F(8 m + 6) = 4 m + 4 F(8 m + 7) = 4 m + 4 F(8 m + 8) = 4 m + 4 Proof: In order to prove this, by induction, we need , 16 additional statments, regarding the following discrete functions ------------------ Definition , 2, :, Let , F[2](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1, 1], [2, 1, 2, 1], [2, 2, 1, 2, 2, 1]} ------------------ Definition , 3, :, Let , F[3](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1]} ------------------ Definition , 4, :, Let , F[4](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1], [2, 1, 2, 1], [2, 2, 1, 2, 2, 1], [2, 1, 2, 2, 1]} ------------------ Definition , 5, :, Let , F[5](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1, 2, 1], [2, 1, 2, 2, 1]} ------------------ Definition , 6, :, Let , F[6](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1, 2, 2, 1]} ------------------ Definition , 7, :, Let , F[7](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1, 2, 1], [2, 1, 2, 2, 1], [1, 2, 2, 1]} ------------------ Definition , 8, :, Let , F[8](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[2, 2, 1, 2, 2, 1], [2, 1], [1, 2, 2, 1]} ------------------ Definition , 9, :, Let , F[9](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1, 1], [2, 1, 2, 1], [2, 2, 1]} ------------------ Definition , 10, :, Let , F[10](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[2, 1], [1, 2, 2, 1], [2, 2, 1]} ------------------ Definition , 11, :, Let , F[11](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1], [2, 1, 2, 1], [2, 1, 2, 2, 1], [2, 2, 1]} ------------------ Definition , 12, :, Let , F[12](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1], [2, 1, 2, 2, 1]} ------------------ Definition , 13, :, Let , F[13](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1], [2, 2, 1, 2, 2, 1], [2, 1]} ------------------ Definition , 14, :, Let , F[14](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1], [2, 1]} ------------------ Definition , 15, :, Let , F[15](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1, 2, 1], [2, 1]} ------------------ Definition , 16, :, Let , F[16](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1], [2, 1], [2, 2, 1]} ------------------ Definition , 17, :, Let , F[17](n), be the maximum number of possible 1's that an n-letter word in {0,1}, avoiding the above-mentioned generalized patterns and IN ADDITION, avoiding at the VERY BEGINNING, the generalized patterns {[1, 2, 1], [2, 1], [1, 2, 2, 1]} ----------------------------- In order to faciliate the inductive proof we need a more General Statement: We have the following explicit expressions for them as piece-wise linear discrete functions. [For the sake of readability we restate the formulas for F[1](n)=F(n) already given above] --------------------- F[2](8 m + 1) = 4 m + 1 F[2](8 m + 2) = 4 m + 1 F[2](8 m + 3) = 4 m + 2 F[2](8 m + 4) = 4 m + 3 F[2](8 m + 5) = 4 m + 3 F[2](8 m + 6) = 4 m + 3 F[2](8 m + 7) = 4 m + 3 F[2](8 m + 8) = 4 m + 4 --------------------- F[3](8 m + 1) = 4 m F[3](8 m + 2) = 4 m + 1 F[3](8 m + 3) = 4 m + 2 F[3](8 m + 4) = 4 m + 2 F[3](8 m + 5) = 4 m + 3 F[3](8 m + 6) = 4 m + 4 F[3](8 m + 7) = 4 m + 4 F[3](8 m + 8) = 4 m + 4 --------------------- F[4](8 m + 1) = 4 m F[4](8 m + 2) = 4 m + 1 F[4](8 m + 3) = 4 m + 2 F[4](8 m + 4) = 4 m + 2 F[4](8 m + 5) = 4 m + 2 F[4](8 m + 6) = 4 m + 2 F[4](8 m + 7) = 4 m + 3 F[4](8 m + 8) = 4 m + 4 --------------------- F[5](8 m + 1) = 4 m + 1 F[5](8 m + 2) = 4 m + 2 F[5](8 m + 3) = 4 m + 2 F[5](8 m + 4) = 4 m + 3 F[5](8 m + 5) = 4 m + 3 F[5](8 m + 6) = 4 m + 3 F[5](8 m + 7) = 4 m + 4 F[5](8 m + 8) = 4 m + 4 --------------------- F[6](8 m + 1) = 4 m + 1 F[6](8 m + 2) = 4 m + 2 F[6](8 m + 3) = 4 m + 2 F[6](8 m + 4) = 4 m + 2 F[6](8 m + 5) = 4 m + 3 F[6](8 m + 6) = 4 m + 4 F[6](8 m + 7) = 4 m + 4 F[6](8 m + 8) = 4 m + 4 --------------------- F[7](8 m + 1) = 4 m + 1 F[7](8 m + 2) = 4 m + 2 F[7](8 m + 3) = 4 m + 2 F[7](8 m + 4) = 4 m + 2 F[7](8 m + 5) = 4 m + 2 F[7](8 m + 6) = 4 m + 3 F[7](8 m + 7) = 4 m + 4 F[7](8 m + 8) = 4 m + 4 --------------------- F[8](8 m + 1) = 4 m + 1 F[8](8 m + 2) = 4 m + 1 F[8](8 m + 3) = 4 m + 2 F[8](8 m + 4) = 4 m + 2 F[8](8 m + 5) = 4 m + 2 F[8](8 m + 6) = 4 m + 3 F[8](8 m + 7) = 4 m + 3 F[8](8 m + 8) = 4 m + 4 --------------------- F[9](8 m + 1) = 4 m + 1 F[9](8 m + 2) = 4 m + 1 F[9](8 m + 3) = 4 m + 1 F[9](8 m + 4) = 4 m + 2 F[9](8 m + 5) = 4 m + 3 F[9](8 m + 6) = 4 m + 3 F[9](8 m + 7) = 4 m + 3 F[9](8 m + 8) = 4 m + 4 --------------------- F[10](8 m + 1) = 4 m + 1 F[10](8 m + 2) = 4 m + 1 F[10](8 m + 3) = 4 m + 1 F[10](8 m + 4) = 4 m + 1 F[10](8 m + 5) = 4 m + 2 F[10](8 m + 6) = 4 m + 3 F[10](8 m + 7) = 4 m + 3 F[10](8 m + 8) = 4 m + 4 --------------------- F[11](8 m + 1) = 4 m F[11](8 m + 2) = 4 m + 1 F[11](8 m + 3) = 4 m + 1 F[11](8 m + 4) = 4 m + 1 F[11](8 m + 5) = 4 m + 2 F[11](8 m + 6) = 4 m + 2 F[11](8 m + 7) = 4 m + 3 F[11](8 m + 8) = 4 m + 4 --------------------- F[12](8 m + 1) = 4 m F[12](8 m + 2) = 4 m + 1 F[12](8 m + 3) = 4 m + 2 F[12](8 m + 4) = 4 m + 2 F[12](8 m + 5) = 4 m + 2 F[12](8 m + 6) = 4 m + 3 F[12](8 m + 7) = 4 m + 4 F[12](8 m + 8) = 4 m + 4 --------------------- F[13](8 m + 1) = 4 m F[13](8 m + 2) = 4 m F[13](8 m + 3) = 4 m + 1 F[13](8 m + 4) = 4 m + 2 F[13](8 m + 5) = 4 m + 2 F[13](8 m + 6) = 4 m + 2 F[13](8 m + 7) = 4 m + 3 F[13](8 m + 8) = 4 m + 4 --------------------- F[14](8 m + 1) = 4 m F[14](8 m + 2) = 4 m F[14](8 m + 3) = 4 m + 1 F[14](8 m + 4) = 4 m + 2 F[14](8 m + 5) = 4 m + 2 F[14](8 m + 6) = 4 m + 3 F[14](8 m + 7) = 4 m + 4 F[14](8 m + 8) = 4 m + 4 --------------------- F[15](8 m + 1) = 4 m + 1 F[15](8 m + 2) = 4 m + 1 F[15](8 m + 3) = 4 m + 1 F[15](8 m + 4) = 4 m + 2 F[15](8 m + 5) = 4 m + 3 F[15](8 m + 6) = 4 m + 3 F[15](8 m + 7) = 4 m + 4 F[15](8 m + 8) = 4 m + 4 --------------------- F[16](8 m + 1) = 4 m F[16](8 m + 2) = 4 m F[16](8 m + 3) = 4 m F[16](8 m + 4) = 4 m + 1 F[16](8 m + 5) = 4 m + 2 F[16](8 m + 6) = 4 m + 2 F[16](8 m + 7) = 4 m + 3 F[16](8 m + 8) = 4 m + 4 --------------------- F[17](8 m + 1) = 4 m + 1 F[17](8 m + 2) = 4 m + 1 F[17](8 m + 3) = 4 m + 1 F[17](8 m + 4) = 4 m + 2 F[17](8 m + 5) = 4 m + 2 F[17](8 m + 6) = 4 m + 3 F[17](8 m + 7) = 4 m + 4 F[17](8 m + 8) = 4 m + 4 Proof: Let F[1](n)=F(n). By considering whether the first letter is a 1 or a 0, chopping it, and figuring out the set of forbidden prefix patterns for the two kinds of chopped words We have the following recursive scheme F[1][n] = max(F[2](n - 1) + 1, F[1](n - 1)) F[2][n] = max(F[4](n - 1) + 1, F[5](n - 1)) F[3][n] = F[1](n - 1) F[4][n] = F[7](n - 1) F[5][n] = max(F[8](n - 1) + 1, F[6](n - 1)) F[6][n] = max(F[1](n - 1), F[9](n - 1) + 1) F[7][n] = max(F[6](n - 1), F[10](n - 1) + 1) F[8][n] = max(F[11](n - 1) + 1, F[12](n - 1)) F[9][n] = max(F[15](n - 1), F[13](n - 1) + 1) F[10][n] = max(F[16](n - 1) + 1, F[14](n - 1)) F[11][n] = F[17](n - 1) F[12][n] = F[6](n - 1) F[13][n] = F[12](n - 1) F[14][n] = F[3](n - 1) F[15][n] = max(F[13](n - 1) + 1, F[3](n - 1)) F[16][n] = F[14](n - 1) F[17][n] = max(F[16](n - 1) + 1, F[3](n - 1)) We have to prove, by induction, that the above explicit expressions for F[i](n) do indeed satisfy this recursive scheme. But this is indeed , true, . Let's see why. Case , 1 We have to prove that F[1](n) = max(F[2](n - 1) + 1, F[1](n - 1)) spelling-out according to cases, we have to prove Subcase , [1, 1] F[1](8 m + 1) = 4 m + 1 Now , F[2](8 m) + 1 = 4 m + 1 and , F[1](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [1, 2] F[1](8 m + 2) = 4 m + 2 Now , F[2](8 m + 1) + 1 = 4 m + 2 and , F[1](8 m + 1) = 4 m + 1 and of course 4 m + 2 = Max(4 m + 2, 4 m + 1) Subcase , [1, 3] F[1](8 m + 3) = 4 m + 2 Now , F[2](8 m + 2) + 1 = 4 m + 2 and , F[1](8 m + 2) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [1, 4] F[1](8 m + 4) = 4 m + 3 Now , F[2](8 m + 3) + 1 = 4 m + 3 and , F[1](8 m + 3) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [1, 5] F[1](8 m + 5) = 4 m + 4 Now , F[2](8 m + 4) + 1 = 4 m + 4 and , F[1](8 m + 4) = 4 m + 3 and of course 4 m + 4 = Max(4 m + 4, 4 m + 3) Subcase , [1, 6] F[1](8 m + 6) = 4 m + 4 Now , F[2](8 m + 5) + 1 = 4 m + 4 and , F[1](8 m + 5) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Subcase , [1, 7] F[1](8 m + 7) = 4 m + 4 Now , F[2](8 m + 6) + 1 = 4 m + 4 and , F[1](8 m + 6) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Subcase , [1, 8] F[1](8 m + 8) = 4 m + 4 Now , F[2](8 m + 7) + 1 = 4 m + 4 and , F[1](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 2 We have to prove that F[2](n) = max(F[4](n - 1) + 1, F[5](n - 1)) spelling-out according to cases, we have to prove Subcase , [2, 1] F[2](8 m + 1) = 4 m + 1 Now , F[4](8 m) + 1 = 4 m + 1 and , F[5](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [2, 2] F[2](8 m + 2) = 4 m + 1 Now , F[4](8 m + 1) + 1 = 4 m + 1 and , F[5](8 m + 1) = 4 m + 1 and of course 4 m + 1 = Max(4 m + 1, 4 m + 1) Subcase , [2, 3] F[2](8 m + 3) = 4 m + 2 Now , F[4](8 m + 2) + 1 = 4 m + 2 and , F[5](8 m + 2) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [2, 4] F[2](8 m + 4) = 4 m + 3 Now , F[4](8 m + 3) + 1 = 4 m + 3 and , F[5](8 m + 3) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [2, 5] F[2](8 m + 5) = 4 m + 3 Now , F[4](8 m + 4) + 1 = 4 m + 3 and , F[5](8 m + 4) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [2, 6] F[2](8 m + 6) = 4 m + 3 Now , F[4](8 m + 5) + 1 = 4 m + 3 and , F[5](8 m + 5) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [2, 7] F[2](8 m + 7) = 4 m + 3 Now , F[4](8 m + 6) + 1 = 4 m + 3 and , F[5](8 m + 6) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [2, 8] F[2](8 m + 8) = 4 m + 4 Now , F[4](8 m + 7) + 1 = 4 m + 4 and , F[5](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 3 We have to prove that F[3][n] = F[1](n - 1) spelling-out according to cases, we have to prove F[3](8 m + 1) = 4 m F[3](8 m + 2) = 4 m + 1 F[3](8 m + 3) = 4 m + 2 F[3](8 m + 4) = 4 m + 2 F[3](8 m + 5) = 4 m + 3 F[3](8 m + 6) = 4 m + 4 F[3](8 m + 7) = 4 m + 4 F[3](8 m + 8) = 4 m + 4 but this is immediate Case , 4 We have to prove that F[4][n] = F[7](n - 1) spelling-out according to cases, we have to prove F[4](8 m + 1) = 4 m F[4](8 m + 2) = 4 m + 1 F[4](8 m + 3) = 4 m + 2 F[4](8 m + 4) = 4 m + 2 F[4](8 m + 5) = 4 m + 2 F[4](8 m + 6) = 4 m + 2 F[4](8 m + 7) = 4 m + 3 F[4](8 m + 8) = 4 m + 4 but this is immediate Case , 5 We have to prove that F[5](n) = max(F[8](n - 1) + 1, F[6](n - 1)) spelling-out according to cases, we have to prove Subcase , [5, 1] F[5](8 m + 1) = 4 m + 1 Now , F[8](8 m) + 1 = 4 m + 1 and , F[6](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [5, 2] F[5](8 m + 2) = 4 m + 2 Now , F[8](8 m + 1) + 1 = 4 m + 2 and , F[6](8 m + 1) = 4 m + 1 and of course 4 m + 2 = Max(4 m + 2, 4 m + 1) Subcase , [5, 3] F[5](8 m + 3) = 4 m + 2 Now , F[8](8 m + 2) + 1 = 4 m + 2 and , F[6](8 m + 2) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [5, 4] F[5](8 m + 4) = 4 m + 3 Now , F[8](8 m + 3) + 1 = 4 m + 3 and , F[6](8 m + 3) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [5, 5] F[5](8 m + 5) = 4 m + 3 Now , F[8](8 m + 4) + 1 = 4 m + 3 and , F[6](8 m + 4) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [5, 6] F[5](8 m + 6) = 4 m + 3 Now , F[8](8 m + 5) + 1 = 4 m + 3 and , F[6](8 m + 5) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [5, 7] F[5](8 m + 7) = 4 m + 4 Now , F[8](8 m + 6) + 1 = 4 m + 4 and , F[6](8 m + 6) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Subcase , [5, 8] F[5](8 m + 8) = 4 m + 4 Now , F[8](8 m + 7) + 1 = 4 m + 4 and , F[6](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 6 We have to prove that F[6](n) = max(F[1](n - 1), F[9](n - 1) + 1) spelling-out according to cases, we have to prove Subcase , [6, 1] F[6](8 m + 1) = 4 m + 1 Now , F[9](8 m) + 1 = 4 m + 1 and , F[1](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [6, 2] F[6](8 m + 2) = 4 m + 2 Now , F[9](8 m + 1) + 1 = 4 m + 2 and , F[1](8 m + 1) = 4 m + 1 and of course 4 m + 2 = Max(4 m + 2, 4 m + 1) Subcase , [6, 3] F[6](8 m + 3) = 4 m + 2 Now , F[9](8 m + 2) + 1 = 4 m + 2 and , F[1](8 m + 2) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [6, 4] F[6](8 m + 4) = 4 m + 2 Now , F[9](8 m + 3) + 1 = 4 m + 2 and , F[1](8 m + 3) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [6, 5] F[6](8 m + 5) = 4 m + 3 Now , F[9](8 m + 4) + 1 = 4 m + 3 and , F[1](8 m + 4) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [6, 6] F[6](8 m + 6) = 4 m + 4 Now , F[9](8 m + 5) + 1 = 4 m + 4 and , F[1](8 m + 5) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Subcase , [6, 7] F[6](8 m + 7) = 4 m + 4 Now , F[9](8 m + 6) + 1 = 4 m + 4 and , F[1](8 m + 6) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Subcase , [6, 8] F[6](8 m + 8) = 4 m + 4 Now , F[9](8 m + 7) + 1 = 4 m + 4 and , F[1](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 7 We have to prove that F[7](n) = max(F[6](n - 1), F[10](n - 1) + 1) spelling-out according to cases, we have to prove Subcase , [7, 1] F[7](8 m + 1) = 4 m + 1 Now , F[10](8 m) + 1 = 4 m + 1 and , F[6](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [7, 2] F[7](8 m + 2) = 4 m + 2 Now , F[10](8 m + 1) + 1 = 4 m + 2 and , F[6](8 m + 1) = 4 m + 1 and of course 4 m + 2 = Max(4 m + 2, 4 m + 1) Subcase , [7, 3] F[7](8 m + 3) = 4 m + 2 Now , F[10](8 m + 2) + 1 = 4 m + 2 and , F[6](8 m + 2) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [7, 4] F[7](8 m + 4) = 4 m + 2 Now , F[10](8 m + 3) + 1 = 4 m + 2 and , F[6](8 m + 3) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [7, 5] F[7](8 m + 5) = 4 m + 2 Now , F[10](8 m + 4) + 1 = 4 m + 2 and , F[6](8 m + 4) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [7, 6] F[7](8 m + 6) = 4 m + 3 Now , F[10](8 m + 5) + 1 = 4 m + 3 and , F[6](8 m + 5) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [7, 7] F[7](8 m + 7) = 4 m + 4 Now , F[10](8 m + 6) + 1 = 4 m + 4 and , F[6](8 m + 6) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Subcase , [7, 8] F[7](8 m + 8) = 4 m + 4 Now , F[10](8 m + 7) + 1 = 4 m + 4 and , F[6](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 8 We have to prove that F[8](n) = max(F[11](n - 1) + 1, F[12](n - 1)) spelling-out according to cases, we have to prove Subcase , [8, 1] F[8](8 m + 1) = 4 m + 1 Now , F[11](8 m) + 1 = 4 m + 1 and , F[12](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [8, 2] F[8](8 m + 2) = 4 m + 1 Now , F[11](8 m + 1) + 1 = 4 m + 1 and , F[12](8 m + 1) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [8, 3] F[8](8 m + 3) = 4 m + 2 Now , F[11](8 m + 2) + 1 = 4 m + 2 and , F[12](8 m + 2) = 4 m + 1 and of course 4 m + 2 = Max(4 m + 2, 4 m + 1) Subcase , [8, 4] F[8](8 m + 4) = 4 m + 2 Now , F[11](8 m + 3) + 1 = 4 m + 2 and , F[12](8 m + 3) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [8, 5] F[8](8 m + 5) = 4 m + 2 Now , F[11](8 m + 4) + 1 = 4 m + 2 and , F[12](8 m + 4) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [8, 6] F[8](8 m + 6) = 4 m + 3 Now , F[11](8 m + 5) + 1 = 4 m + 3 and , F[12](8 m + 5) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [8, 7] F[8](8 m + 7) = 4 m + 3 Now , F[11](8 m + 6) + 1 = 4 m + 3 and , F[12](8 m + 6) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [8, 8] F[8](8 m + 8) = 4 m + 4 Now , F[11](8 m + 7) + 1 = 4 m + 4 and , F[12](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 9 We have to prove that F[9](n) = max(F[15](n - 1), F[13](n - 1) + 1) spelling-out according to cases, we have to prove Subcase , [9, 1] F[9](8 m + 1) = 4 m + 1 Now , F[13](8 m) + 1 = 4 m + 1 and , F[15](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [9, 2] F[9](8 m + 2) = 4 m + 1 Now , F[13](8 m + 1) + 1 = 4 m + 1 and , F[15](8 m + 1) = 4 m + 1 and of course 4 m + 1 = Max(4 m + 1, 4 m + 1) Subcase , [9, 3] F[9](8 m + 3) = 4 m + 1 Now , F[13](8 m + 2) + 1 = 4 m + 1 and , F[15](8 m + 2) = 4 m + 1 and of course 4 m + 1 = Max(4 m + 1, 4 m + 1) Subcase , [9, 4] F[9](8 m + 4) = 4 m + 2 Now , F[13](8 m + 3) + 1 = 4 m + 2 and , F[15](8 m + 3) = 4 m + 1 and of course 4 m + 2 = Max(4 m + 2, 4 m + 1) Subcase , [9, 5] F[9](8 m + 5) = 4 m + 3 Now , F[13](8 m + 4) + 1 = 4 m + 3 and , F[15](8 m + 4) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [9, 6] F[9](8 m + 6) = 4 m + 3 Now , F[13](8 m + 5) + 1 = 4 m + 3 and , F[15](8 m + 5) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [9, 7] F[9](8 m + 7) = 4 m + 3 Now , F[13](8 m + 6) + 1 = 4 m + 3 and , F[15](8 m + 6) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [9, 8] F[9](8 m + 8) = 4 m + 4 Now , F[13](8 m + 7) + 1 = 4 m + 4 and , F[15](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 10 We have to prove that F[10](n) = max(F[16](n - 1) + 1, F[14](n - 1)) spelling-out according to cases, we have to prove Subcase , [10, 1] F[10](8 m + 1) = 4 m + 1 Now , F[16](8 m) + 1 = 4 m + 1 and , F[14](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [10, 2] F[10](8 m + 2) = 4 m + 1 Now , F[16](8 m + 1) + 1 = 4 m + 1 and , F[14](8 m + 1) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [10, 3] F[10](8 m + 3) = 4 m + 1 Now , F[16](8 m + 2) + 1 = 4 m + 1 and , F[14](8 m + 2) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [10, 4] F[10](8 m + 4) = 4 m + 1 Now , F[16](8 m + 3) + 1 = 4 m + 1 and , F[14](8 m + 3) = 4 m + 1 and of course 4 m + 1 = Max(4 m + 1, 4 m + 1) Subcase , [10, 5] F[10](8 m + 5) = 4 m + 2 Now , F[16](8 m + 4) + 1 = 4 m + 2 and , F[14](8 m + 4) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [10, 6] F[10](8 m + 6) = 4 m + 3 Now , F[16](8 m + 5) + 1 = 4 m + 3 and , F[14](8 m + 5) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [10, 7] F[10](8 m + 7) = 4 m + 3 Now , F[16](8 m + 6) + 1 = 4 m + 3 and , F[14](8 m + 6) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [10, 8] F[10](8 m + 8) = 4 m + 4 Now , F[16](8 m + 7) + 1 = 4 m + 4 and , F[14](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 11 We have to prove that F[11][n] = F[17](n - 1) spelling-out according to cases, we have to prove F[11](8 m + 1) = 4 m F[11](8 m + 2) = 4 m + 1 F[11](8 m + 3) = 4 m + 1 F[11](8 m + 4) = 4 m + 1 F[11](8 m + 5) = 4 m + 2 F[11](8 m + 6) = 4 m + 2 F[11](8 m + 7) = 4 m + 3 F[11](8 m + 8) = 4 m + 4 but this is immediate Case , 12 We have to prove that F[12][n] = F[6](n - 1) spelling-out according to cases, we have to prove F[12](8 m + 1) = 4 m F[12](8 m + 2) = 4 m + 1 F[12](8 m + 3) = 4 m + 2 F[12](8 m + 4) = 4 m + 2 F[12](8 m + 5) = 4 m + 2 F[12](8 m + 6) = 4 m + 3 F[12](8 m + 7) = 4 m + 4 F[12](8 m + 8) = 4 m + 4 but this is immediate Case , 13 We have to prove that F[13][n] = F[12](n - 1) spelling-out according to cases, we have to prove F[13](8 m + 1) = 4 m F[13](8 m + 2) = 4 m F[13](8 m + 3) = 4 m + 1 F[13](8 m + 4) = 4 m + 2 F[13](8 m + 5) = 4 m + 2 F[13](8 m + 6) = 4 m + 2 F[13](8 m + 7) = 4 m + 3 F[13](8 m + 8) = 4 m + 4 but this is immediate Case , 14 We have to prove that F[14][n] = F[3](n - 1) spelling-out according to cases, we have to prove F[14](8 m + 1) = 4 m F[14](8 m + 2) = 4 m F[14](8 m + 3) = 4 m + 1 F[14](8 m + 4) = 4 m + 2 F[14](8 m + 5) = 4 m + 2 F[14](8 m + 6) = 4 m + 3 F[14](8 m + 7) = 4 m + 4 F[14](8 m + 8) = 4 m + 4 but this is immediate Case , 15 We have to prove that F[15](n) = max(F[13](n - 1) + 1, F[3](n - 1)) spelling-out according to cases, we have to prove Subcase , [15, 1] F[15](8 m + 1) = 4 m + 1 Now , F[13](8 m) + 1 = 4 m + 1 and , F[3](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [15, 2] F[15](8 m + 2) = 4 m + 1 Now , F[13](8 m + 1) + 1 = 4 m + 1 and , F[3](8 m + 1) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [15, 3] F[15](8 m + 3) = 4 m + 1 Now , F[13](8 m + 2) + 1 = 4 m + 1 and , F[3](8 m + 2) = 4 m + 1 and of course 4 m + 1 = Max(4 m + 1, 4 m + 1) Subcase , [15, 4] F[15](8 m + 4) = 4 m + 2 Now , F[13](8 m + 3) + 1 = 4 m + 2 and , F[3](8 m + 3) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [15, 5] F[15](8 m + 5) = 4 m + 3 Now , F[13](8 m + 4) + 1 = 4 m + 3 and , F[3](8 m + 4) = 4 m + 2 and of course 4 m + 3 = Max(4 m + 3, 4 m + 2) Subcase , [15, 6] F[15](8 m + 6) = 4 m + 3 Now , F[13](8 m + 5) + 1 = 4 m + 3 and , F[3](8 m + 5) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [15, 7] F[15](8 m + 7) = 4 m + 4 Now , F[13](8 m + 6) + 1 = 4 m + 3 and , F[3](8 m + 6) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 3, 4 m + 4) Subcase , [15, 8] F[15](8 m + 8) = 4 m + 4 Now , F[13](8 m + 7) + 1 = 4 m + 4 and , F[3](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) Case , 16 We have to prove that F[16][n] = F[14](n - 1) spelling-out according to cases, we have to prove F[16](8 m + 1) = 4 m F[16](8 m + 2) = 4 m F[16](8 m + 3) = 4 m F[16](8 m + 4) = 4 m + 1 F[16](8 m + 5) = 4 m + 2 F[16](8 m + 6) = 4 m + 2 F[16](8 m + 7) = 4 m + 3 F[16](8 m + 8) = 4 m + 4 but this is immediate Case , 17 We have to prove that F[17](n) = max(F[16](n - 1) + 1, F[3](n - 1)) spelling-out according to cases, we have to prove Subcase , [17, 1] F[17](8 m + 1) = 4 m + 1 Now , F[16](8 m) + 1 = 4 m + 1 and , F[3](8 m) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [17, 2] F[17](8 m + 2) = 4 m + 1 Now , F[16](8 m + 1) + 1 = 4 m + 1 and , F[3](8 m + 1) = 4 m and of course 4 m + 1 = Max(4 m + 1, 4 m) Subcase , [17, 3] F[17](8 m + 3) = 4 m + 1 Now , F[16](8 m + 2) + 1 = 4 m + 1 and , F[3](8 m + 2) = 4 m + 1 and of course 4 m + 1 = Max(4 m + 1, 4 m + 1) Subcase , [17, 4] F[17](8 m + 4) = 4 m + 2 Now , F[16](8 m + 3) + 1 = 4 m + 1 and , F[3](8 m + 3) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 1, 4 m + 2) Subcase , [17, 5] F[17](8 m + 5) = 4 m + 2 Now , F[16](8 m + 4) + 1 = 4 m + 2 and , F[3](8 m + 4) = 4 m + 2 and of course 4 m + 2 = Max(4 m + 2, 4 m + 2) Subcase , [17, 6] F[17](8 m + 6) = 4 m + 3 Now , F[16](8 m + 5) + 1 = 4 m + 3 and , F[3](8 m + 5) = 4 m + 3 and of course 4 m + 3 = Max(4 m + 3, 4 m + 3) Subcase , [17, 7] F[17](8 m + 7) = 4 m + 4 Now , F[16](8 m + 6) + 1 = 4 m + 3 and , F[3](8 m + 6) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 3, 4 m + 4) Subcase , [17, 8] F[17](8 m + 8) = 4 m + 4 Now , F[16](8 m + 7) + 1 = 4 m + 4 and , F[3](8 m + 7) = 4 m + 4 and of course 4 m + 4 = Max(4 m + 4, 4 m + 4) QED. This took, 0.291, seconds