Functions, Induction: Definitions, Proofs, and Real-World Models

TAKEAWAYS:

• Functions are mappings between sets with rules for injectivity (one-to-one), surjectivity (onto), and bijectivity (both), visualized via arrows and Venn diagrams.
• Mathematical induction proves statements for all natural numbers by verifying a base case and an inductive step, critical for algorithms and recursive definitions.
• Real-world functions model eSewa’s transaction hashing (injective), Daraz’s order queue (surjective), and Ncell’s billing cycles (recursive).
• Proof techniques include strong induction (for nested dependencies) and structural induction (for recursive data like trees).
• Common pitfalls: assuming induction works without a base case, misapplying surjectivity in finite sets, and conflating recursive definitions with iterative ones.

1. Functions: Definitions and Classifications

A function $f:A\to B$ assigns each element of set $A$ (domain) to exactly one element of set $B$ (codomain). Functions are the backbone of algorithms, data mappings, and real-world systems like user authentication (hashing) or inventory tracking.

Key Properties

Worked Example: eSewa Transaction Hashing

eSewa uses a hash function $h:\text{Transaction}\to \text{HashCode}$ that is injective (no two transactions produce the same hash). If Alice and Bob both pay ₹1000 to a merchant, their hashes must differ:

• Domain $A$: All possible transactions (user, amount, timestamp).
• Codomain $B$: 256-bit hash strings.
• Proof of injectivity: If $h(t_1)=h(t_2)$, the system flags a collision (rare but possible in practice).

Trace:

1. User inputs: {"user": "Alice", "amount": 1000, "time": "10:00"}.
2. Hash function computes: h(t) = "a1b2c3...".
3. Check: No other transaction in the database has this hash → injective.

2. Function Composition and Inverses

• Composition $(f\circ g)(x)=f(g(x))$: Combining functions (e.g., applying a discount then tax).
• Inverse $f^{-1}$: Reverses $f$ if $f$ is bijective. Used in encryption (e.g., RSA) and decryption.

Mermaid Diagram: Function Composition

flowchart LR
    A["Domain (X)"] -->|"g"| B["Intermediate (Y)"]
    B -->|"f"| C["Codomain (Z)"]
    A -->|"f∘g"| C

Real-World Tie: Ncell Billing Cycle Ncell’s billing function $f:\text{UsageMinutes}\to \text{BillAmount}$ is not injective (same minutes → same bill), but the inverse $f^{-1}$ (predicting usage from bill) is not well-defined because multiple usage patterns can yield the same bill.

3. Mathematical Induction: Principle and Proofs

Induction proves statements $P(n)$ for all natural numbers $n$. It’s used in algorithm analysis (e.g., proving a sorting algorithm works for $n$ items) and recursive definitions (e.g., Fibonacci sequence).

Weak vs. Strong Induction

Worked Example: Sum of First $n$ Natural Numbers

Statement: $P(n)=1+2+\cdots +n=\frac{n(n+1)}{2}$.

Proof by Weak Induction:

1. Base Case ($n=1$): $P(1)=1=\frac{1(1+1)}{2}$. ✅
2. Inductive Step: Assume $P(k)=1+\cdots +k=\frac{k(k+1)}{2}$ holds. Prove $P(k+1)$: $$1+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}.$$ Thus, $P(k+1)$ holds. By induction, $P(n)$ is true for all $n$.

Real-World Tie: Daraz Order Queue Daraz’s order processing can be modeled recursively:

• Base Case: 1 order is delivered in 1 day.
• Inductive Step: If $k$ orders take $k$ days, then $k+1$ orders take $k+1$ days (assuming linear processing).
• Limitation: Real queues have parallel processing (strong induction needed for multi-worker systems).

4. Structural Induction

Used for recursive data structures like trees or linked lists. Prove a property holds for:

1. The base case (smallest structure, e.g., empty tree).
2. Any structure built from smaller ones (inductive step).

Example: Sum of Nodes in a Binary Tree Statement: The sum of all nodes in a binary tree $T$ is $\text{sum}(T)=\text{root.value}+\text{sum(left subtree)}+\text{sum(right subtree)}$.

Proof:

1. Base Case: Empty tree $T=\varnothing$. Sum is $0$. ✅
2. Inductive Step: Assume all trees with $\le k$ nodes satisfy the property. For a tree $T$ with $k+1$ nodes: $$\text{sum}(T)=\text{root.value}+\text{sum(left)}+\text{sum(right)}.$$ By the inductive hypothesis, the sums of left and right subtrees hold. Thus, $\text{sum}(T)$ holds.

Mermaid Diagram: Binary Tree Sum

5. Common Pitfalls and Exam Traps

1. Forgetting the Base Case:

   • ❌ "Assume $P(k)$ holds" without proving $P(1)$.
   • ✅ Always start with $n=1$ or the smallest valid input.

2. Misapplying Surjectivity:

   • In finite sets, a function $f:A\to B$ with $|A|<|B|$ cannot be surjective.
   • Example: A Daraz warehouse with 100 items ($A$) cannot map surjectively to 200 customers ($B$) if each customer can only receive one item.

3. Confusing Weak and Strong Induction:

   • Weak induction suffices for linear recursion (e.g., Fibonacci).
   • Strong induction is needed for nested dependencies (e.g., proving a sorting network works for all input sizes).

4. Assuming Inverses Exist:

   • Only bijective functions have inverses. Non-injective functions (e.g., $f(x)=x^2$) fail here.

## In the Real World

1. eSewa Transactions (Injective Functions)

   • Idea: Hash functions map transactions to unique codes.
   • How: The system uses SHA-256, an injective (almost) function to prevent duplicate payments. If two transactions hash to the same code, the system detects a collision and rejects one.
   • Why it matters: Ensures no double-spending or fraud in digital payments.

2. Daraz Order Queue (Surjective Functions)

   • Idea: Order status updates must cover all possible states.
   • How: The function $f:\text{OrderID}\to \text{Status}$ (e.g., "Processing," "Shipped," "Delivered") is surjective if every order eventually reaches "Delivered." In practice, failed deliveries create "Returned" as an additional codomain element.
   • Why it matters: Helps customers track orders and Daraz manage logistics.

3. Ncell Billing Cycles (Recursive Definitions)

   • Idea: Billing is calculated recursively over usage periods.
   • How: Monthly bill $B(n)$ depends on usage in the $n$-th month and the previous month’s bill: $$B(n)=\text{BaseCharge}+\text{UsageCharge}(n)+\text{RecurringFees}.$$ This resembles a recurrence relation where each month’s bill builds on prior data.
   • Why it matters: Enables dynamic pricing and usage-based billing.

## Exam Tip

1. For Functions:

   • Always draw arrows to show injectivity/surjectivity. Examiners love visual proofs.
   • Memorize the definitions: Write them out in your own words (e.g., "Injective means no two inputs share the same output").
   • Common question: Given a function $f:A\to B$, determine if it’s injective/surjective. Solution: Check if $f(a)=f(b)⟹a=b$ (injective) or if every $b\in B$ is mapped to (surjective).

2. For Induction:

   • Structure your proof clearly:

     1. Base Case: Show P(1) holds.
     2. Inductive Hypothesis: Assume P(k) holds.
     3. Inductive Step: Prove P(k+1) using P(k).
     4. Conclusion: By induction, P(n) holds for all n.
     

   • Practice with recurrence relations: Questions often ask to prove a closed-form solution (e.g., Fibonacci) using induction.
   • Watch for strong induction: If the problem involves nested cases (e.g., "proving a sorting algorithm works for any input size"), use strong induction.

3. Avoid These Mistakes:

   • ❌ Skipping the base case or assuming it’s trivial.
   • ❌ Using weak induction for problems requiring strong induction (e.g., recursive algorithms).
   • ❌ Forgetting to define the domain and codomain explicitly in function questions.

4. Real-World Applications:

   • eSewa/Khalti: Expect questions on injective functions (e.g., "Why can’t two transactions have the same hash?").
   • Daraz/Nepse: Surjective functions (e.g., "Can all orders be delivered? What if the warehouse is full?").
   • Banks/Ncell: Recurrence relations (e.g., "Model the monthly interest on a loan using a recurrence relation").

Final Note: Discrete functions and induction are the "glue" between theory and real-world systems. Master these, and you’ll ace problems on algorithms, cryptography, and system design—key topics in IT235 and beyond.