Functions, Induction: Definitions, Proofs & Real-World Uses

TAKEAWAYS:

• Functions map inputs to outputs uniquely, and their properties (injective, surjective, bijective) determine reversibility and uniqueness.
• Mathematical induction proves statements for all natural numbers by verifying a base case and an inductive step (weak) or assuming all prior cases hold (strong).
• Recursive functions (e.g., power(a, n)) rely on induction to prove correctness, breaking problems into smaller subproblems.
• Real-world ties: eSewa’s user-ID mapping (bijective), Daraz’s order-processing queue (injective), and Ncell’s billing cycles (recurrence relations).
• Exam traps: Confusing onto (surjective) with one-to-one (injective), misapplying induction hypotheses, or ignoring domain restrictions.
• Visual proofs: Truth tables for logical statements, step-by-step induction trees, and function property diagrams.

---

1. Functions: Definitions and Properties

Functions are the backbone of discrete mathematics, modeling relationships where each input has exactly one output. They appear in algorithms, databases, and real-world systems like user authentication (e.g., eSewa’s login system).

1.1 Core Definitions

A function $f:A\to B$ assigns each element $a\in A$ (domain) to one and only one element $b\in B$ (codomain).

• Notation: $f(a)=b$ or $a\mapsto b$.
• Example: $f(x)=x^2$ maps integers to non-negative integers.

1.2 Types of Functions

1.3 Worked Example: Proving Function Properties

Question: Determine if $f:\mathbb{Z}\to \mathbb{Z}$ defined by $f(x)=x^2$ is injective, surjective, or bijective. Solution:

1. Injective?
   • Test $f(2)=4$ and $f(-2)=4$. Since $2\ne -2$, $f$ is not injective.
2. Surjective?
   • Codomain $\mathbb{Z}$ includes negative numbers, but $f(x)\ge 0$. Thus, not surjective.
3. Bijective? No (requires both injective and surjective).

Real-World Tie: Daraz’s order queue is injective (each order ID maps to one unique order), but not surjective (not all possible IDs are used).

---

2. Mathematical Induction

Induction proves statements for all natural numbers by leveraging a "domino effect": if the first piece stands (base case) and each piece topples the next (inductive step), the whole sequence falls.

2.1 Weak vs. Strong Induction

2.2 Proof Structure

1. Base Case: Verify $P(1)$ (or $P(0)$).
2. Inductive Step: Assume $P(k)$ holds, then prove $P(k+1)$.
3. Conclusion: By induction, $P(n)$ holds for all $n$.

Visual Proof Trace:

2.3 Worked Example: Recursive Algorithm Proof

Question: Prove the correctness of power(a, n) using induction.

int power(int a, int n) {
    if (n == 0) return 1;
    else return a * power(a, n - 1);
}

Solution:

1. Base Case ($n=0$): $\text{power}(a,0)=1=a^0$. ✅
2. Inductive Step:
   • Assume $\text{power}(a,k)=a^k$ holds.
   • Then, $\text{power}(a,k+1)=a\cdot \text{power}(a,k)=a\cdot a^k=a^{k+1}$. ✅
3. Conclusion: By induction, $\text{power}(a,n)=a^n$ for all $n\ge 0$.

Real-World Tie: Ncell’s billing cycles use recurrence relations (e.g., "this month’s charge = last month’s charge + new usage"). Induction proves the total cost formula works for any number of months.

---

3. Applications in Nepali Contexts

---

4. Common Pitfalls and Exam Tips

4.1 Function Misconceptions

• Not injective ≠ not a function: A function can fail to be injective (e.g., $f(x)=x^2$) but still be valid.
• Surjective ≠ onto in all contexts: In computer science, "onto" often implies the codomain equals the range (e.g., hashing functions).

4.2 Induction Mistakes

• Forgetting the base case: Always verify $P(1)$ or $P(0)$.
• Weak vs. strong confusion: Use strong induction for statements like "every number ≥ 8 is a sum of 3’s and 5’s."
• Inductive hypothesis misuse: Only use $P(k)$ to prove $P(k+1)$; never assume $P(k+1)$ holds.

4.3 Exam Strategy

1. For function questions:
   • Draw a mapping diagram (like the Mermaid example above).
   • Test specific values (e.g., $f(0)$, $f(1)$) to check injectivity/surjectivity.
2. For induction proofs:
   • Write the base case first.
   • Clearly state the inductive hypothesis before using it.
   • Use bullet points for each step (examiners love clarity).

---

5. Practice Problems (Exam-Style)

1. Functions:

   • Let $f:\mathbb{R}\to \mathbb{R}$ be $f(x)=3x-2$. Is $f$ bijective? Justify.
   • Define a function $g:\{1,2,3\}\to \{a,b\}$ that is injective but not surjective.

2. Induction:

   • Prove $1^2+2^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$ for all $n\ge 1$.
   • Show that $5^n-2^n$ is divisible by 3 for all $n\ge 0$.

3. Real-World:

   • Pathao’s ride-matching system uses injective functions (each ride ID maps to one driver-passenger pair). Explain why surjectivity isn’t required here.

---

Exam Tip

• Functions: Always pair definitions with visual mappings (even in text exams, describe them clearly).
• Induction: If stuck, start with small values (e.g., $n=1,2,3$) to spot patterns.
• Recursive proofs: Trace the algorithm step-by-step (like the power example) to see the induction in action.
• Nepali context: Relate proofs to local systems (e.g., "This is like how eSewa verifies your ID before login"). Examiners appreciate relevance!