🧩Discrete Mathematics Unit 6 – Induction and Recursion

Key Concepts and Definitions

• Mathematical induction proves statements that depend on a natural number $n$
• Recursion defines a function or sequence in terms of itself, using previously calculated values
• Base case specifies the initial value(s) of a recursive function or sequence (e.g., $f(0) = 1$)
• Recursive case defines how to calculate the next value using previous values (e.g., $f(n) = n \cdot f(n-1)$)
• Inductive hypothesis assumes the statement holds for a specific value $k$
• Inductive step proves the statement holds for $k+1$ using the inductive hypothesis
• Strong induction assumes the statement holds for all values less than or equal to $k$
• Structural induction proves properties of recursively defined data structures (trees, lists)

Principles of Mathematical Induction

• Induction proves a statement $P(n)$ holds for all natural numbers $n \geq n_0$
• Base case: prove $P(n_0)$ is true for the smallest value $n_0$ (usually 0 or 1)
• Inductive hypothesis: assume $P(k)$ is true for some arbitrary $k \geq n_0$
• Inductive step: using the inductive hypothesis, prove $P(k+1)$ is true
  • This step often involves algebraic manipulation or logical reasoning
• If base case and inductive step are proven, $P(n)$ holds for all $n \geq n_0$ by the principle of mathematical induction
• Induction is a powerful tool for proving statements involving natural numbers
• Many mathematical theorems and properties can be proven using induction (sum of first $n$ integers, properties of Fibonacci numbers)

Types of Induction

• Weak induction (or simple induction) proves $P(k+1)$ using only the assumption that $P(k)$ is true
• Strong induction proves $P(k+1)$ using the assumption that $P(i)$ is true for all $i \leq k$
  • Useful when the problem requires using more than just the previous term
• Structural induction proves properties of recursively defined data structures
  • Base case proves the property holds for the simplest structure (empty list, leaf node)
  • Inductive step proves if the property holds for substructures, it holds for the entire structure
• Well-ordering principle states every non-empty set of natural numbers has a least element
  • Equivalent to the principle of mathematical induction
• Transfinite induction extends mathematical induction to well-ordered sets beyond the natural numbers

Recursive Definitions and Sequences

• Recursive definitions define objects or sequences in terms of themselves
• Factorial function: $n! = n \cdot (n-1)!$ for $n > 0$, with base case $0! = 1$
• Fibonacci sequence: $F_n = F_{n-1} + F_{n-2}$ for $n > 1$, with base cases $F_0 = 0$ and $F_1 = 1$
• Recursively defined sets: the set of all binary strings can be defined as the empty string and the set of all binary strings with 0 or 1 appended
• Recursive algorithms break down a problem into smaller subproblems until a base case is reached (binary search, quicksort)
• Recursive functions must have one or more base cases to avoid infinite recursion
• Recursive sequences can be analyzed using recurrence relations and generating functions

Proving Theorems with Induction

• Induction is a powerful tool for proving theorems involving natural numbers
• Steps: state the theorem as a proposition $P(n)$, prove the base case, assume the inductive hypothesis, and prove the inductive step
• Example: prove the sum of the first $n$ odd integers is $n^2$
  • $P(n)$: $1 + 3 + 5 + \cdots + (2n-1) = n^2$
  • Base case: $P(1)$ is true since $1 = 1^2$
  • Inductive hypothesis: assume $P(k)$ is true for some $k \geq 1$
  • Inductive step: prove $P(k+1)$ by adding $2(k+1)-1$ to both sides of $P(k)$
• Induction can prove divisibility properties, inequalities, and identities involving sums or products
• Inductive proofs often involve algebraic manipulation and simplification

Applications in Computer Science

• Recursive algorithms are based on the principles of recursion and induction
  • Examples: binary search, quicksort, merge sort, depth-first search, breadth-first search
• Recursive data structures are defined recursively and can be processed using recursive algorithms
  • Examples: linked lists, trees, graphs
• Induction proves the correctness and time complexity of recursive algorithms
  • Example: prove the time complexity of binary search is $O(\log n)$
• Recursive problem-solving is a fundamental paradigm in computer science
  • Divide-and-conquer algorithms break down problems into smaller subproblems (merge sort, quicksort)
  • Dynamic programming solves problems by combining solutions to overlapping subproblems (Fibonacci numbers, shortest paths)
• Functional programming languages (Haskell, Lisp) heavily rely on recursion for control flow and data processing

Common Pitfalls and Misconceptions

• Forgetting to prove the base case or proving it incorrectly
• Assuming the inductive hypothesis without explicitly stating it
• Failing to prove the inductive step completely or making unjustified assumptions
• Confusing weak induction and strong induction
  • Strong induction is needed when the problem requires multiple previous terms
• Attempting to use induction on non-integer or negative values
  • Induction only works for natural numbers (non-negative integers)
• Incorrectly defining the recursive case in a recursive definition
  • The recursive case must be well-defined and lead to the base case
• Forgetting to include a base case in a recursive definition, leading to infinite recursion
• Misunderstanding the scope and limitations of induction
  • Induction proves statements for all natural numbers but does not provide a specific value or example

Practice Problems and Examples

• Prove by induction that the sum of the first $n$ positive integers is $\frac{n(n+1)}{2}$
• Use strong induction to prove that every positive integer can be written as a sum of distinct powers of 2
• Prove by induction that for all $n \geq 1$, $\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$
• Define the Ackermann function recursively and prove that it is well-defined for all non-negative integers
• Use structural induction to prove that a binary tree with $n$ nodes has $n+1$ null pointers
• Prove by induction that the number of subsets of a set with $n$ elements is $2^n$
• Use induction to prove the binomial theorem: $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$
• Prove by induction that the Fibonacci sequence satisfies the recurrence relation $F_n = F_{n-1} + F_{n-2}$ for $n > 1$