PGDDSA Study · Semester 1

Core Titles

Key headlines and terms for quick recall

Principle of Mathematical Induction
Base case $P(1)$
Inductive hypothesis assume $P(k)$
Inductive step prove $P(k+1)$
Strong (complete) induction
Common applications: sums, divisibility, inequalities, recursion

Basic Idea

What it is, why it matters, how it works

The idea

To prove a statement $P(n)$ for every natural number $n$ , induction lets us replace infinitely many proofs with two steps:

Base case — show $P(1)$ (or whichever smallest $n$ ).
Inductive step — assume $P(k)$ (induction hypothesis) and prove $P(k+1)$ .

If both succeed, $P(n)$ holds for all $n \ge 1$ — like dominoes falling.

Strong induction

Sometimes proving $P(k+1)$ needs all of $P(1), \dots, P(k)$ , not just $P(k)$ . Strong induction assumes all previous cases hold. It is equivalent in power to ordinary induction.

Standard worked examples

Sum of first $n$ naturals. Claim: $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ .

Base $n=1$ : LHS = 1, RHS = $\tfrac{1 \cdot 2}{2} = 1$ . ✓
Step: assume $\sum_{i=1}^k i = \tfrac{k(k+1)}{2}$ . Then $\sum_{i=1}^{k+1} i = \tfrac{k(k+1)}{2} + (k+1) = \tfrac{(k+1)(k+2)}{2}$ — exactly $P(k+1)$ . ✓

Divisibility. $3 \mid (n^3 - n)$ for all $n \ge 1$ .

Base: $n=1$ , $1 - 1 = 0$ — divisible. ✓
Step: assume $3 \mid (k^3 - k)$ . Then $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3(k^2 + k)$ . Both terms divisible by 3. ✓

Why this matters in Data Science

Induction is the standard tool for proving correctness of recursive algorithms (merge sort, divide-and-conquer) and for bounding their complexity.

Mind Map

Visual structure of the concept

MATHEMATICAL INDUCTION
├── Goal: prove P(n) ∀ n ≥ n₀
├── Two-step recipe
│   ├── BASE: P(n₀) holds
│   └── STEP: P(k) ⇒ P(k+1)
├── Strong induction
│   └── Assume P(n₀)…P(k) to prove P(k+1)
└── Applications
    ├── Sum formulas
    ├── Divisibility
    ├── Inequalities (e.g. 2ⁿ > n)
    ├── Recursive definitions
    └── Algorithm correctness

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. State the principle of mathematical induction. If $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for all $k$ , then $P(n)$ is true for all $n \ge 1$ .

Q2. What is the difference between weak and strong induction? Weak induction assumes only $P(k)$ to prove $P(k+1)$ ; strong induction assumes $P(1), \dots, P(k)$ .

Q3. By induction, what is $1 + 2 + \cdots + n$ ? $\dfrac{n(n+1)}{2}$ .

Part B (20 marks)

Q. Prove by induction that $1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ for all $n \ge 1$ . Also prove $2^n > n$ for all $n \ge 1$ .

Part 1. Let $P(n): \; 1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ .

Base $n=1$ : LHS = 1, RHS = $\dfrac{1\cdot 2\cdot 3}{6} = 1$ . ✓

Step. Assume $P(k)$ holds. Then $\sum_{i=1}^{k+1} i^2 = \dfrac{k(k+1)(2k+1)}{6} + (k+1)^2.$ Factor $(k+1)$ : $= \dfrac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \dfrac{(k+1)(2k^2 + 7k + 6)}{6} = \dfrac{(k+1)(k+2)(2k+3)}{6}.$ This matches $P(k+1)$ . ∎

Part 2. Let $Q(n): \; 2^n > n$ .

Base $n=1$ : $2 > 1$ . ✓

Step. Assume $2^k > k$ . Then $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$ (since $k \ge 1$ ). So $2^{k+1} > k+1$ . ∎

Mathematical Induction