Problem 68 - Discrete Mathematics with Applications

Question

Let \(a, b, n \in \mathbb{N}, b \geq 2, c, d \in \mathbb{R}^{+}, f(1)=d,\) and \(n\) is a power of \(b .\) Let \(f\) be a non decreasing function such that \(f(n)=a f(n / b)+c n^{2} .\) Prove each. If \(a \neq b^{2},\) then \(f(n)=A n^{2}+B n^{\log _{b} a},\) where \(A=\frac{b^{2} c}{b^{2}-a}\) and \(B=d+\frac{b^{2} c}{a-b^{2}}\)

Step-by-Step Solution

Answer

For the case \(a \neq b^2\), the function \(f(n)\) can be expressed as \(f(n)= An^2 + Bn^{\log_ba}\), where \(A=\frac{b^2c}{b^2-a}\) and \(B=d+\frac{b^2c}{a-b^2}\). This is proved by deriving a general expression for the function using the given recursive formula, and comparing the coefficients of each term in the two expressions. The constants A and B are then determined by substituting the values and conditions provided in the problem.

Step 1: Understand the Problem

We have a nondecreasing function \(f(n)\) defined recursively as \(f(n)=af(n/b)+cn^2,\) where \(n\) is a power of \(b\), \(a, b, n \in \mathbb{N}, b \geq 2, c, d \in \mathbb{R}^{+}\). We have to express the function \(f(n)\) for the case \(a \neq b^2\) and find the constants A and B.

Step 2: Derive the Expression for f(n) in Terms of A and B

We will start by deriving the general expression for a given \(k\). We know that \(n=b^k\) for some \(k \in \mathbb{N}\). Therefore, we can rewrite the recursive function for \(f(n)\) as \(f(b^k) = af(b^{k-1}) + cb^{2k}\). Applying the recursion k times, we can obtain the following expression: \[f(b^{k}) = a^k f(1) + \sum_{i=1}^{k} a^{k-i} c b^{2i}\] For \(a \neq b^2\), we can simplify the expression further as: \[f(b^{k}) = a^k d + cb^2\sum_{i=1}^{k} \left(\frac{a}{b^2}\right)^{k-i} \] Now, we rewrite the expression in terms of \(A, B\) as given in the exercise: \[f(n) = An^2 + Bn^{\log_ba} \]

Step 3: Determine the Constants A and B

To find the constants A and B, we will compare the coefficients of each term in the two expressions of \(f(n)\) obtained in steps 2 and 3. For the coefficient of \(n^2\), we have \(A=\frac{b^2c}{b^2-a}\) from the statement in the exercise. Comparing this with the \(n^2\) term in step 2, we have \(cb^2 = \frac{b^2c}{b^2-a}\), which gives us the correct value of \(A\) as \(\frac{b^2c}{b^2-a}\). For the coefficient of \(n^{\log_ba}\), we have \(B=d+\frac{b^2 c}{a-b^{2}}\) from the statement in the exercise. Comparing this with the \(n^{\log_ba}\) term in step 2, we have \(a^kd = d+\frac{b^2 c}{a-b^{2}}\). By substituting the value of \(A\) and using the given condition \(a \neq b^{2}\), we can also obtain the correct value of \(B\) as \(d+\frac{b^{2} c}{a-b^{2}}\). Thus, we have proved that for \(a \neq b^{2}\), the function \(f(n)\) indeed has the form provided in the exercise with constants \(A=\frac{b^{2} c}{b^{2}-a}\) and \(B=d+\frac{b^{2} c}{a-b^{2}}\).

Key Concepts

Nondecreasing Functions

A nondecreasing function is a type of function where the output value does not decrease as the input value increases. This means if you have two inputs, say \(n_1\) and \(n_2\), with \(n_1 < n_2\), then the function value at \(n_1\) will not be greater than the function value at \(n_2\). In mathematical terms, if \(f(n_1) \leq f(n_2)\) for all \(n_1 < n_2\), the function is nondecreasing.

Nondecreasing functions are crucial in recurrence relations because they often simplify the proving process. They allow us to apply various induction techniques to demonstrate certain properties or solve for the general terms. In the given problem, this was essential to ensure that applying the recursive step maintains a certain order in the function values, which helped in deriving specific expressions for \(f(n)\) for the given conditions.

Asymptotic Analysis

Asymptotic analysis is a method used to describe the behavior of functions as their inputs get very large. It is a crucial tool in computer science and mathematics for analyzing algorithms and recurrence relations. The central idea is to find the "order of growth" or the dominant term that dictates how the function behaves in the limit.

In the context of the recursive relation \(f(n) = a f(n/b) + cn^2\), asymptotic analysis helps us express \(f(n)\) in terms of more understandable, asymptotic terms. By identifying the dominant terms in the function, such as \(An^2\) and \(Bn^{\log_b a}\), it provides a clearer insight into how \(f(n)\) behaves as \(n\) becomes very large. Asymptotic terms like these directly relate to the performance or complexity of algorithms, particularly in understanding time or space complexities.

• Terms like \(n^2\) and \(n^{\log_b a}\) indicate polynomial growth rates.
• The constants \(A\) and \(B\) derived showcase the input dependencies and recursion impact on growth.

Asymptotic analysis, therefore, gives us a powerful tool to predict and understand the long-term behavior of recurrence-related calculations.

Mathematical Proofs

Mathematical proofs provide a rigorous way to substantiate statements or formulas we derive from recurrence relations and other mathematical concepts. In our exercise, the primary aim was to prove the expression for \(f(n) \) when \(a eq b^2\). The task here focused on demonstrating that the derived formula holds true under the stipulated conditions.

The process typically involves several key steps:

• Identifying and Understanding the Problem: The first step is clearly understanding what needs to be proven. For instance, in this exercise, recognizing our need to express \(f(n)\) for \(a eq b^2\) was crucial.
• Derivation and Calculation: Once you identify the problems, use logical steps to derive the needed expressions. This usually involves breaking down complex problems into smaller parts.
• Verification: After deriving potential solutions or expressions, compare them to known results or initial conditions, ensuring all parts of the equation fit perfectly.

In proving the formula for \(f(n)\), we combined recursive expressions, asymptotic terms, and coefficients to derive values for \(A\) and \(B\), thus confirming the relationship was correctly represented. Mathematical proofs, like these, help verify the correctness of complex computations and relationships.