Problem 66 - Discrete Mathematics with Applications

Question

Let \(a, b \in \mathbb{N}\) and \(c, d \in \mathbb{R}^{+}\) with \(b \geq 2 .\) Let \(f\) be a non decreasing function such that \(f(n)=a f(n / b)+c\) and \(f(1)=d .\) Prove each. $$\text { If } a \neq 1, \text { then } f(n)=\mathrm{O}\left(n^{\log _{b} a}\right)$$

Step-by-Step Solution

Answer

In summary, using induction, we have shown that for \(a \neq 1\), \(f(n) \leq K n^{\log_b{a}}\) for all \(n \in \mathbb{N}\) and \(K \geq d\). Therefore, we conclude that if \(a \neq 1\), then \(f(n) = O(n^{\log_b{a}})\).

Step 1: Understanding the function

Consider the function \(f(n)\). Since \(f\) is nondecreasing, as \(n\) increases, \(f(n)\) either stays the same or increases. The function involves a recursive step, as the value of \(f(n/b)\) is used to compute \(f(n)\). However, for the base case, \(f(1)=d\).

Step 2: Proving the relation for the base case

First, let's analyze the function at the base case \(n=1\). We have that \(f(1)=d\). Since \(1^{\log_b{a}} = 1\), we know that \(K \cdot 1^{\log_b{a}} = K\), and for \(K=d\), the relation holds true when \(n=1\).

Step 3: Induction on the function relation

Now, we will use induction to prove the relation \(f(n) = O(n^{\log_b{a}})\), when \(a \neq 1\). Assume \(f(m) \leq K m^{\log_b{a}}\) for all \(m \leq n\), where \(m, n \in \mathbb{N}\) and \(K \geq d\). We want to show that this claim holds for \(f(n+1)\). Now, since \(b \geq 2\), we know that \(m \leq n < bm\). Thus: \[f(n+1) \leq af\left(\frac{n+1}{b}\right) + c \leq aK\left(\frac{n+1}{b}\right)^{\log_b{a}}+c\]

Step 4: Simplify the inequality

We will simplify the expression obtained in the previous step: \[aK\left(\frac{n+1}{b}\right)^{\log_b{a}}+c = aK\left(\frac{n+1}{b}\right)^{\log_b{a}}+K\frac{c}{K} \leq aK\left(\frac{n+1}{b}\right)^{\log_b{a}}+K\left(\frac{n+1}{b}\right)^{\log_b{a}}\] \[= K(n+1)^{\log_b{a}}\] This implies: \[f(n+1) \leq K(n+1)^{\log_b{a}}\]

Step 5: Conclude the proof

We have proven, by induction, that \(f(n) \leq K n^{\log_b{a}}\) for all \(n \in \mathbb{N}\) and \(K \geq d\), when \(a \neq 1\). Therefore, \(f(n) = O(n^{\log_b{a}})\) when \(a \neq 1\).

Key Concepts

Recursive Functions

When discussing recursive functions, we're exploring a powerful concept in mathematics and computer science where a function repeatedly refers to itself in order to solve a problem. Recursive functions comprise a base case to end the recursion and a rule to reduce all other cases towards the base case.

In the provided exercise, the function defined by the relation f(n) = a f(n / b) + c is recursive, since it expresses f(n) in terms of f at a smaller input size n/b. The base case is given as f(1) = d, which anchors the recursion. Understanding recursive functions is crucial, as they can simplify complex problems into smaller, manageable sub-problems, particularly when analyzing algorithms' running times or behaviors.

Induction

Induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers. It consists of two main parts: the base case and the inductive step.

In our base case, we validate that the statement holds for the initial value, here when n = 1. The inductive step involves assuming the statement for a natural number n and then proving it for n+1. The exercise demonstrates induction by assuming a hypothesis for all values up to n and extending the argument to n+1, showing that the inequality f(n+1) ≤ K(n+1)^{log_b(a)} holds true. This technique is fundamental because it assures the correctness of the statements for an infinite sequence of natural numbers.

Big O Notation

Big O notation is a mathematical concept used to describe the upper bound of the growth rate of functions, especially in the context of computer science to classify algorithms according to how their runtime or space requirements grow as the input size grows.

The expression O(n^{log_b(a)}) in the problem setting denotes that f(n) grows at most as quickly as n^{log_b(a)} for some constant multiplicative factor, when n gets large. Particularly when a ≠ 1, the notation encapsulates the efficiency of the recursive function. Communicating algorithm complexities with Big O notation allows for quick comparisons and understanding of algorithmic efficiency without delving into implementation details.

Mathematical Proofs

Mathematical proofs are rigorous arguments used to show the truth of a mathematical statement. In our textbook solution, the proof involves demonstrating that f(n) = O(n^{log_b(a)}) when a ≠ 1.

Proofs may employ various strategies, such as direct proof, proof by contradiction, and as seen here, proof by induction. Crafting proofs requires a deep understanding of the relevant concepts, in this case, recursive functions and Big O notation. The goal is to build a logical sequence of statements leading from known truths to the conclusion we seek to establish – in this case, the asymptotic behavior of the recursive function defined.