91Ó°ÊÓ

Nonnegative integers are the set of whole numbers that include zero and all positive integers. They are 0, 1, 2, 3, and so on. In recursive functions, nonnegative integers often serve as the domain, meaning that the function will produce values based on these inputs.
For example, in part (a) of the given exercise, the function is defined for all nonnegative integers starting from zero: \( f(0) = 1 \), and for \( n \geq 1 \), \( f(n) = -f(n-1) \). The nature of nonnegative integers ensures there's always a clear starting point (usually zero) and a sequence of increments by 1.

Recursion is a method of defining functions where the function calls itself with a modified argument. This allows complex problems to be broken down into simpler, more manageable sub-problems. In many recursive definitions, the function is expressed in terms of smaller instances of the same function.
For example, in part (a) of the exercise, recursion is evident: if \(f(0) = 1\) and \( f(n) = -f(n-1) \), the function is being defined by referring back to itself with a smaller argument (\( n-1 \)). By breaking problems into smaller parts, recursion simplifies the solution process but also requires clear base cases to terminate the recursive calls.

A well-defined function means that for every input, the function produces exactly one output, and this output is consistent with the definition. In recursive functions, this means that the base cases and recursive steps must logically cover all possible inputs and always yield a single, definite value.
In the exercise, function (c) is not well-defined because the recursive formula \(f(n) = 2f(n+1)\) for \(n \geq 2\) refers to future values rather than earlier ones. This creates an infinite loop without reaching any of the base cases, violating the well-defined requirement. On the contrary, part (d) is well-defined since \( f(n) = 2f(n-1) \) consistently produces a unique output for every nonnegative integer based on established base cases.

An explicit formula gives a direct way to compute the function value for any input, without requiring iterative or recursive steps. In other words, it provides a closed-form expression that directly maps any given input from the domain to an output.
For example, in part (a) of the exercise, the recursive definition \( f(n) = -f(n-1) \) results in an explicit formula: \( f(n) = (-1)^n \). This formula allows us to calculate \( f(n) \) directly for any nonnegative integer \(n\), without needing to reference previous values.

Base cases are essential in recursive definitions. They establish the starting points of recursion and ensure that every recursive call eventually terminates. Base cases are the simplest instances of the function, not defined recursively, and directly give a result.
In the exercise, each function has its base cases. For example, in part (b), the base cases are \( f(0) = 1 \), \( f(1) = 0 \), and \( f(2) = 2 \). These base values are referenced to calculate values for \( n \geq 3 \) using the recursive rule \( f(n) = 2f(n-3) \). Each valid recursive function must have clear base cases to avoid infinite recursion and to make computation feasible.