Problem 28 - Discrete Mathematics with Applications

Question

The 91 -function \(f\), invented by John McCarthy, is defined recursively on \(\mathbf{W}\) as follows.$$f(x)=\left\\{\begin{array}{ll}x-10 & \text { if } x>100 \\\f(f(x+11)) & \text { if } 0 \leq x \leq 100\end{array}\right.$$ Compute each $$f(98)$$

Step-by-Step Solution

Answer

The value of McCarthy's 91-function at x = 98 is \(f(98) = 91\).

Step 1: Set up the 91-function definition for f(x)

Given the 91-function, we have: \[f(x)=\left\{\begin{array}{ll}{x-10} & {\text { if } x > 100} \\ {f(f(x+11))} & {\text { if } 0 \leq x \leq 100}\end{array}\right.\] Now, let's evaluate f(98):

Step 2: Plug in x = 98

Since x = 98 falls within the 0 ≤ x ≤ 100 range, we'll use the second part of the function definition: \[f(98) = f(f(98 + 11))\]

Step 3: Perform arithmetic operations

Now, let's compute the inside part: \begin{align*} f(98) &= f(f(98 + 11)) \\ &= f(f(109)) \end{align*}

Step 4: Evaluate f(109)

Since x = 109 is greater than 100, we can use the first part of the function definition for this value of x: \begin{align*} f(109) &= 109 - 10 \\ &= 99 \end{align*} Now, substitute the value back into the equation: \[f(98) = f(99)\]

Step 5: Evaluate f(99)

Similarly to the previous step, we start with the recursive part of the function definition again since x = 99 is in the 0 ≤ x ≤ 100 range: \[f(99) = f(f(99 + 11))\] Now, compute the operation inside the function: \begin{align*} f(99) &= f(f(99 + 11)) \\ &= f(f(110)) \end{align*}

Step 6: Evaluate f(110)

Since x = 110 is greater than 100, we can use the first part of the function definition: \begin{align*} f(110) &= 110 - 10 \\ &= 100 \end{align*} Now, substitute the value back into the equation: \[f(99) = f(100)\]

Step 7: Evaluate f(100)

Lastly, we need to evaluate f(100). Since x = 100 is at the upper bound of the 0 ≤ x ≤ 100 range, we still have to use the recursive part of the function definition one more time: \[f(100) = f(f(100 + 11))\] Now, compute the operation inside the function: \begin{align*} f(100) &= f(f(100 + 11)) \\ &= f(f(111)) \end{align*}

Step 8: Evaluate f(111)

Since x = 111 is greater than 100, we can use the first part of the function definition: \begin{align*} f(111) &= 111 - 10 \\ &= 101 \end{align*} Now, substitute the value back into the equation: \[f(100) = f(101)\]

Step 9: Final evaluation of f(101)

At last, we need to evaluate f(101). Since x = 101 is greater than 100, we can now use the first part of the function definition: \begin{align*} f(101) &= 101 - 10 \\ &= 91 \end{align*}

Step 10: Conclude result

Now, we can trace back our results to get the answer to f(98): \[f(98) = f(99) = f(100) = 91\] So, the value of McCarthy's 91-function at x = 98 is: \[f(98) = 91\]

Key Concepts

McCarthy 91-function

The McCarthy 91-function is a fascinating recursive function, devised by computer scientist John McCarthy, that serves as an exemplary study in recursion. This function is known not just for its mathematical curiosity but also for its applications in understanding recursive processing. The function is defined as:

• If \(x > 100\), \(f(x) = x - 10\).
• For \(0 \leq x \leq 100\), \(f(x) = f(f(x + 11))\).

This two-part definition creates a looping behavior that intriguingly returns a fixed result, typically 91, for inputs of 100 or less. The McCarthy 91-function is often used to teach principles of recursion due to its seemingly counterintuitive yet patterned result. Despite what might be expected, no matter how many recursive calls are made under certain conditions, the function usually stabilizes to yield 91 as the output.

Recursive Function Definition

Recursive functions are those that define their results in terms of themselves, allowing a problem to turn smaller and smaller until it reaches a base case. With the McCarthy 91-function, recursion is used in the following way:

• The function calls itself with an altered argument, such as \(f(x + 11)\)
• This recursive call further triggers another recursion until specific conditions (e.g., \(x > 100\)) are met, where the simple arithmetic computation \(x - 10\) provides a direct answer.

The essence of recursion lies in these continued calls with smaller input values or reduced problems. This process mirrors breaking down a large problem into more manageable parts. Recursive functions need base cases to prevent infinite looping; for this particular function, the base case is reached when \(x\) exceeds 100.

Arithmetic Operations in Recursion

Arithmetic operations within recursive functions play a critical role in reaching a base case or transitioning between recursive calls. In the McCarthy 91-function, arithmetic operations are crucial:

• They reduce \(x\) by 10 when \(x > 100\), hastening the process to reach a base value.
• They adjust \(x\) by adding 11, which further propagates the recursion loop in the other condition \(0 \leq x \leq 100\).

These operations ensure that recursive functions do not endlessly loop, but rather, progress toward a conclusive end. Understanding how arithmetic manipulations assist recursion helps to comprehend multipart output scenarios and the eventual termination of recursive algorithms.

Problem-Solving with Recursion

Recursion is a powerful tool in problem-solving that allows you to tackle complex issues by decomposing them into simpler subproblems. The McCarthy 91-function is a classic example of how seemingly repetitive logic can solve a complex problem efficiently. Here's how it works:

• The function starts by identifying which condition of its definition applies to the input.
• From there, it continually breaks down the problem using recursive calls, simplifying the input with each function evaluation.
• By leveraging recursion, the function eventually converges on a solution, even if it appears roundabout initially.

This method of iterative breakdown allows complex calculations to be structured in a linear narrative, easy to trace back once the final result is obtained. The use of recursion in problem-solving not only resolves the issue at hand but often leads to elegant, efficient solutions that are easy to translate into programmatic contexts.