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:
“There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
—François, Duc De La Rochefoucauld (1613–1680)
“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)
“a meek humble Man of modest sense,
Who preaching peace does practice continence;
Whose pious life’s a proof he does believe,
Mysterious truths, which no Man can conceive.”
—John Wilmot, 2d Earl Of Rochester (1647–1680)