Proof
Here is a proof that the function behaves as expected.
For 90 ≤ n < 101,
M(n) = M(M(n + 11)) = M(n + 11 - 10), where n + 11 >= 101 since n >= 90 = M(n + 1)So M(n) = 91 for 90 ≤ n < 101.
We can use this as a base case for induction on blocks of 11 numbers, like so:
Assume that M(n) = 91 for a ≤ n < a + 11.
Then, for any n such that a - 11 ≤ n < a,
M(n) = M(M(n + 11)) = M(91), by hypothesis, since a ≤ n + 11 < a + 11 = 91, by the base case.Now by induction M(n) = 91 for any n in such a block. There are no holes between the blocks, so M(n) = 91 for n < 101. We can also add n = 101 as a special case.
Read more about this topic: McCarthy 91 Function
Famous quotes containing the word proof:
“Right and proof are two crutches for everything bent and crooked that limps along.”
—Franz Grillparzer (17911872)
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other twoa proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (16941773)
“War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.”
—M.F.K. Fisher (19081992)