Chapter 4 — Principle Of Mathematical Induction

What is Mathematical Induction?
Mathematical Induction is a proof technique used to establish that a statement P(n) is true for every natural number n (or for every n ≥ a fixed integer). It is especially useful for propositions indexed by integers: formulas, inequalities, divisibility properties, recurrence relations, etc.

Motivation — the domino analogy
Imagine a row of dominoes. If the first domino falls (base case) and every time any domino falls it knocks down the next one (inductive step), then all dominoes will fall. Induction in mathematics works the same way: show the first case holds, then show that whenever the statement holds for an arbitrary k it also holds for k+1. Hence it holds for all natural numbers.

Formal two-step structure

1. Base case: Prove P(1) (or P(m) for some starting integer m).
2. Inductive step: Assume P(k) is true for some arbitrary k (this assumption is called the inductive hypothesis). Using this assumption, prove P(k+1) is true.

Why does it work?
If P(1) is true then by the inductive step P(2) is true, then P(3), and so on — forming an infinite chain. This informal idea can be formalized using the well-ordering principle of natural numbers (every non-empty set of natural numbers has a least element) or by treating the implication P(k) ⇒ P(k+1) as a mechanism that propagates truth to every successor.

Variants and cautions
There is ordinary induction (assume P(k) to prove P(k+1)) and strong induction (assume P(1), P(2), …, P(k) to prove P(k+1)). Strong induction is logically equivalent to ordinary induction but often more convenient. Common mistakes include skipping a valid base case (start might be n=0 or n=2 depending on the statement) or assuming what you need to prove inside the inductive step.

Natural numbers (denoted by N) are the counting numbers: 1, 2, 3, ... (CBSE Class 11 convention). They are the basic discrete building blocks used to count objects, index sequences, and measure steps.

Well-ordering principle (WOP): Every non-empty subset of natural numbers has a least (smallest) element. Formally, if S \u2260 \u2205 and S \subseteq N, then \u2208 m \u2208 S such that m \u2264 s for all s \u2208 S.

Why WOP matters:

• It captures the discrete, ordered nature of N: you cannot have an infinite descending chain of natural numbers.
• WOP is equivalent (logically) to the Principle of Mathematical Induction: either can be used to prove the other. Both are fundamental tools in proofs about integers.

Intuition and short proof-sketch of equivalence with induction:

• WOP => Induction: Suppose a property P(n) holds for n=1 and whenever it holds for n it holds for n+1. If some k violates P, the set S of counterexamples is a non-empty subset of N, so by WOP S has a least element r. But r cannot be 1 (since P(1) true), and if r>1 then r-1 is not in S so P(r-1) holds, so P(r) must hold by the inductive step — contradiction. Hence no counterexample exists and P(n) holds for all n.
• Induction => WOP: Suppose S is a non-empty subset of N with no least element. Define Q(n) = "no element of S is \u2264 n". Q(1) is true because 1 is not the least element of S; if Q(k) is true then Q(k+1) is also true (otherwise a counterexample \u2264 k+1 would produce a least element of S). By induction Q(n) holds for all n, contradicting S being non-empty. Thus S must have a least element.

Consequences and usages:

• Used to justify proofs by (ordinary and strong) induction.
• Used in existence proofs where you choose the smallest counterexample and derive a contradiction.

What it says

The Principle of Mathematical Induction is a method to prove that a statement P(n) is true for every integer n greater than or equal to some starting integer n0. Formally, if two conditions hold:

1. Base case: P(n0) is true.
2. Inductive step: For every integer k >= n0, if P(k) is true then P(k+1) is also true (we write: P(k) => P(k+1)).

Then P(n) is true for all integers n >= n0.

Why it works (idea of proof)

Intuitively, the base case starts the chain and the inductive step propagates truth from each integer to the next, like a row of dominoes: knock down the first domino (base) and each domino knocks down the next (inductive step), so all fall. A formal proof often uses the well-ordering principle: assume the set S of integers >= n0 for which P(n) is false is nonempty; it has a least element m. By base case m cannot be n0, so m-1 >= n0 and P(m-1) is true, and then by the inductive step P(m) must be true, contradiction. Hence S is empty and P(n) holds for all n >= n0.

Key parts to check when using induction

• Clearly state n0 (where you start).
• Prove base case P(n0) explicitly.
• Assume P(k) for arbitrary k >= n0 (this is the inductive hypothesis).
• Using the hypothesis, deduce P(k+1) with correct algebra/reasoning.
• Conclude P(n) for all n >= n0.

Variants

Strong induction (complete induction) assumes P(j) true for all j with n0 <= j <= k and uses that to prove P(k+1). It is equivalent in power to ordinary induction but sometimes easier to apply.

Mathematical induction is a method to prove that a statement P(n) holds for every integer n greater than or equal to some starting value m (usually m = 1). An inductive proof has a fixed, logical structure that mimics a chain reaction: establish the first link, then show that any link implies the next one. If both are true, every link in the (infinite) chain is true.

Standard structure (three parts)

• Base case: Verify P(m) is true for the starting value m (often m = 1). This anchors the argument.
• Inductive hypothesis: Assume P(k) is true for an arbitrary but fixed integer k ≥ m. This is a temporary assumption used only inside the next step.
• Inductive step: Using the inductive hypothesis, prove P(k+1) is true. Conclude that if P(k) holds then P(k+1) holds.

Conclusion: From the base case and the inductive step we conclude P(n) is true for all integers n ≥ m.

Notes and variants: (i) The starting index m can be any integer; adjust the base case accordingly. (ii) Strong induction assumes P(j) true for all j with m ≤ j ≤ k and uses that to prove P(k+1). It is logically equivalent but often easier for recurrence or divisibility problems. (iii) Always state clearly what the inductive assumption is and where it is used; check algebra and edge cases (e.g., when k = 0 or small n behave differently).

What is Mathematical Induction?
Mathematical induction is a proof technique used to show that a statement P(n) holds for all integers n greater than or equal to some starting integer (usually 1). The usual structure: (i) Base Case: prove P(1) (or P(start)), and (ii) Inductive Step: assume P(k) and prove P(k+1). This is often called weak or ordinary induction.

Why variations?
Some problems need stronger assumptions or more base cases. These give rise to useful variations: strong (complete) induction and k-step (multiple-base) induction. All these forms are logically equivalent to the well-ordering principle, but each is more convenient for certain proofs.

1. Ordinary (Weak) Induction
Structure: prove P(n_0) for the first n_0, then show P(k) ⇒ P(k+1) for all k ≥ n_0. Use when P(k+1) can be deduced directly from P(k).

2. Strong (Complete) Induction
Structure: prove P(n_0) (sometimes more base cases), then show: if P(n_0), P(n_0+1), …, P(k) are all true, then P(k+1) is true. In other words assume the statement holds for all smaller integers up to k to prove it for k+1. Use when P(k+1) depends on several earlier instances, not just the immediate predecessor. Classic use: existence of prime factorization.

3. k-step (r-step or multiple-base) Induction
Structure: when recurrence or statement depends on the previous r values. Provide base cases P(n_0), P(n_0+1), …, P(n_0+r-1). Then assume P(m) true for the last r indices m = k-r+1, …, k and prove P(k+1). This is natural for linear recurrences like Fibonacci where order is 2 (r=2).

4. Structural and Other Forms
Structural induction is used on recursively defined objects (trees, strings). Backward or reverse induction proves for all n ≤ N by starting at N and stepping down. These are variations adapted to the domain of the statement.

When to choose which?
- If P(k+1) uses only P(k): ordinary induction is enough.
- If P(k+1) uses several earlier values (P(k), P(k−1), ...): use k-step or strong induction.
- For recursively defined objects (e.g., expressions, trees): use structural induction.

Equivalence note
Though they look different, weak induction, strong induction and the well-ordering principle are equivalent: each can be derived from the others.

Common pitfalls
- Forgetting necessary base cases (especially for k-step induction).
- Assuming the induction hypothesis incorrectly (using it for n+1 while only established for ≤ n).
- Failing to show how the assumed cases combine to give the next case.

Short template (ordinary):
1. Base case: verify P(n_0).
2. Induction hypothesis: assume P(k) true for some k ≥ n_0.
3. Induction step: prove P(k+1) using the hypothesis.
4. Conclude: P(n) true for all n ≥ n_0.

What is a proof technique? A proof technique is a systematic method for showing that a mathematical statement is true for all values in its domain. In Class 11 (Principle of Mathematical Induction), the main technique studied is mathematical induction, but understanding when and how to use induction alongside other techniques is important.

Common proof methods

• Direct proof: Start from known facts/definitions and use logical steps to reach the statement to be proved.
• Proof by contrapositive: To prove “If P then Q”, prove the equivalent statement “If not Q then not P”.
• Proof by contradiction: Assume the negation of the statement and derive a contradiction with known facts.
• Mathematical induction (weak/ordinary): Prove base case P(1) (or P(0)), then show P(k) ⇒ P(k+1). Concludes P(n) holds for all relevant n.
• Strong (complete) induction: Assume the statement holds for all values ≤ k and use that to prove it for k+1. Useful when k+1 depends on several earlier cases.
• Well-ordering principle: Every nonempty set of positive integers has a least element; often used equivalently to prove statements by contradiction or induction.

Structure of a standard induction proof (strategy)

1. Base case: Verify the statement for the initial integer (commonly n = 1 or n = 0).
2. Induction hypothesis: Assume the statement is true for a fixed but arbitrary n = k.
3. Induction step: Using the hypothesis, prove the statement for n = k + 1. Often requires algebraic manipulation, factorization, or adding/subtracting terms to connect P(k) to P(k+1).
4. Conclusion: By induction, the statement holds for all integers n greater than or equal to the base case.

Practical strategies when using induction

• Check the simplest cases first; sometimes the base case must start at n = 0 or a higher value (e.g., n = 2).
• If P(k) ⇒ P(k+1) looks hard, try proving a stronger statement Q(n) that makes the step easier (then Q ⇒ original statement).
• Use known identities (factorization, binomial theorem, telescoping sums) to transform P(k+1) into an expression containing P(k).
• For divisibility proofs, express the k+1 case in terms of the k case plus a factor that is divisible by the modulus.
• For inequalities, careful bounding and monotonicity arguments often help when moving from k to k+1.
• If the k+1 depends on multiple previous values, consider strong induction.

Common pitfalls

• Forgetting to verify the base case or verifying the wrong base case.
• Assuming what you need to prove inside the induction step (circular reasoning).
• Applying induction to statements that are not naturally indexed by integers.

How induction connects to real life (intuition)

• Domino effect: proving the first domino falls (base case) and that any fallen domino knocks the next one down (induction step) ensures all dominos fall.
• Climbing a ladder: show you can step on the first rung and that if you can reach rung k you can reach k+1; thus you can reach any rung.

Overview. In the chapter on the Principle of Mathematical Induction (PMI), a central application is proving formulas for finite sums and series: closed forms for 1 + 2 + ... + n, sums of powers, arithmetic series, geometric series, etc. PMI gives a systematic method to show a proposed formula works for every positive integer n.

Induction template (how to apply PMI to sums).

1. Base case: Verify the formula for n = 1 (or the smallest relevant n).
2. Induction hypothesis: Assume the formula holds for n = k (i.e. assume the closed form equals the sum up to k).
3. Induction step: Use the hypothesis to show the formula holds for n = k + 1 by adding the (k+1)-th term and simplifying to get the proposed expression for k+1.

Why it works for sums. Sums usually have a simple recurrence: S_{n+1} = S_n + (n+1)-th term. This recurrence fits exactly with the induction step: assume S_n has the closed form, then add the next term and simplify to reach the closed form for S_{n+1}.

Typical examples proved by induction. sum of first n natural numbers, sum of first n odd numbers, sum of first n even numbers, sum of squares and cubes, finite geometric series, and sum formula for an arithmetic progression. Proofs are short because the next partial sum is previous sum plus one extra term.

Notes on sigma notation. A sum is often written as Σ_{r=1}^n a_r. To prove a closed form for Σ_{r=1}^n a_r, show it holds for n=1 and that adding a_{k+1} to the k-case yields the (k+1)-case.

Overview. In the Principle of Mathematical Induction (PMI) we often use induction to prove statements about divisibility for all natural numbers n. Many useful results can be proved in a uniform way by combining simple modular arithmetic facts, factorisations and induction.

Basic idea and a key lemma (useful for many problems). If m | (a − b) (i.e. a ≡ b (mod m)), then for every natural number n we have m | (a^n − b^n). This can be proved either by factorisation a^n − b^n = (a − b)(a^{n-1} + a^{n-2}b + ··· + b^{n-1}) or by induction:

1. Base n = 1: a^1 − b^1 = a − b is divisible by m by hypothesis.
2. Inductive step: assume m | (a^k − b^k). Then a^{k+1} − b^{k+1} = a(a^k − b^k) + b^k(a − b). Both terms are divisible by m, so m | (a^{k+1} − b^{k+1}).

Immediate corollaries often used:

• If a ≡ 1 (mod m) then m | (a^n − 1) for every n ≥ 1.
• If a ≡ r (mod m) then a^n ≡ r^n (mod m) for every n ≥ 1 (proved by induction on n).
• Special case: 10 ≡ 1 (mod 9) so 9 | (10^n − 1); hence a string of n nines is divisible by 9. Also 10 ≡ −1 (mod 11) so 10^n ≡ (−1)^n (mod 11): this gives divisibility rules involving 11.

Typical proofs by induction used in exercises. Many CBSE problems ask to prove statements such as “for all n ∈ N, m divides some expression in n”. The standard pattern:

1. Check the base case (usually n = 1 or small n).
2. Assume the statement holds for n = k.
3. Use algebra, factorisation, modular congruence or multiplication by a to obtain the statement for n = k + 1.

Why these results matter (applications / motivation).

• Understanding residues (remainders) of powers helps in computing last digits, checksums and cyclic patterns (e.g. last digit of 2^n repeats every 4).
• Divisibility results are used in checksum schemes (ISBN-10 uses mod 11), hashing, some simple cryptographic observations and in problem solving (contest mathematics).
• They give fast tests for divisibility of large numbers (using congruences rather than full division).

Connections with other algebraic facts. Factorisation identities commonly used together with induction:

• a^n − b^n = (a − b)(a^{n-1} + a^{n-2}b + ··· + b^{n-1}).
• a^n + b^n is divisible by a + b when n is odd (because a^n + b^n = (a + b)(...).)

Short remark on alternate (non-inductive) methods. Some divisibility statements follow immediately from congruence reasoning or binomial theorem (for example, for any n, (n+1)^n − 1 is divisible by n because binomial expansion gives (n+1)^n = 1 + n·(integer)). Still, induction gives a systematic way to prove families of such results.

Principle of Mathematical Induction (PMI) is often used to prove inequalities that are stated for every natural number n (or for n ≥ n0). The general method is:

1. Base case: Verify the inequality for the smallest n (usually n = 1 or n = n0).
2. Inductive hypothesis: Assume the inequality holds for some k ≥ n0.
3. Inductive step: Using the hypothesis, manipulate algebraically to deduce the inequality for k+1. Typical tactics: multiply both sides by positive quantities, add/subtract convenient terms, factor, use monotonicity, or apply known inequalities (Bernoulli, AM–GM, binomial expansion).

Key remarks when using induction for inequalities:

• Sometimes the statement must be strengthened (prove a stronger inequality) so the inductive step becomes easier.
• Careful handling of signs: ensure any multiplier used is positive so the direction of inequality is preserved.
• For inequalities involving functions of n that grow rapidly (e.g., exponentials), it is common to verify a few base cases (e.g., n = 1,2,3,4) before a general inductive step becomes valid.

Common inequality results proved by induction include Bernoulli's inequality, bounds comparing polynomial and exponential growth, factorial vs exponential lower bounds, and AM–GM in certain forms.

Overview: A sequence is an ordered list of numbers a1, a2, a3, ... A recurrence relation (or recurrence) expresses each term of a sequence in terms of previous terms. Applications in Class 11 use the Principle of Mathematical Induction to (a) prove closed-form formulas for sequences defined by a pattern or recurrence, and (b) justify formulas for sums and nth terms.

Key ideas:

• Recurrence relation: an equation like a_{n+1} = f(a_n, a_{n-1}, ..., n) together with initial condition(s) determines a sequence.
• Closed form: an explicit formula a_n in terms of n (no earlier terms). Many recurrences have simple closed forms (AP, GP, first-order linear recurrences).
• Using induction: To prove a proposed closed form, use mathematical induction: verify base case(s); assume true for n = k; prove for n = k+1 using the recurrence.

Common types:

• Arithmetic progression (AP): difference between successive terms constant.
• Geometric progression (GP): ratio between successive terms constant.
• First-order linear recurrence: a_{n+1} = p a_n + q (special cases include AP and GP).
• Fibonacci-type recurrences: a_{n+2} = a_{n+1} + a_n (needs two initial values).

Strategy for solving simple recurrences (class 11 level):

1. Identify recurrence and initial condition(s).
2. Try iteration: write first few terms to guess a pattern (unroll the recurrence).
3. Conjecture a closed form.
4. Prove the conjecture by induction (base case(s) and inductive step using recurrence).

Why induction helps: Many recurrences define a sequence step-by-step. Once you propose a closed form from pattern/iteration, induction is the rigorous tool that shows the closed form holds for all n by using the recurrence itself in the inductive step.

Overview. The Principle of Mathematical Induction is a fundamental proof technique used to establish combinatorial and algebraic identities that hold for every positive integer n. The standard induction template is:

1. Base case: Verify the identity for the initial value (usually n = 1 or n = 0).
2. Inductive hypothesis: Assume the identity holds for n = k.
3. Inductive step: Using the hypothesis, prove the identity for n = k + 1.

Induction often pairs with combinatorial reasoning: an identity can be proved algebraically by induction or justified combinatorially by counting the same set in two ways.

Common types of identities proved by induction

• Arithmetic and power sums: formulas for 1 + 2 + ... + n, 1^2 + 2^2 + ... + n^2, 1^3 + ... + n^3, etc.
• Geometric sums: partial sums of a geometric progression.
• Binomial and combinatorial identities: e.g. sum of binomial coefficients, relations among combinations.

Typical inductive proofs (sketches)

1) Sum of first n natural numbers:

Claim: 1 + 2 + ... + n = n(n+1)/2.
Base: n=1 gives 1 = 1(2)/2. Assume true for n=k. For n=k+1 add (k+1) to both sides and simplify to get (k+1)(k+2)/2. Thus holds for k+1.

2) Sum of squares:

Claim: 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6.
Proceed by base case and add (k+1)^2 to the k-case expression and simplify.

3) Geometric sum:

Claim: 1 + r + r^2 + ... + r^n = (r^{n+1}-1)/(r-1) for r != 1.
Prove by induction or multiply both sides by (r-1) and telescope; induction verifies step from k to k+1.

4) Binomial sum:

Claim: sum_{i=0}^n C(n,i) = 2^n.
A combinatorial argument: each subset of an n-element set is counted; algebraically prove by induction using Pascal's identity C(n+1,i)=C(n,i)+C(n,i-1) and summing.

5) Weighted binomial sum:

Claim: sum_{i=0}^n i C(n,i) = n 2^{n-1}.
Prove by noting i C(n,i) = n C(n-1,i-1) and summing, or use induction.

Why these are useful.

Such identities reduce repeated computation, evaluate combinatorial counts, simplify algebraic expressions, and appear in probability, algebra, number theory and real-world computations (finance, network counts, resource allocation).

Principle of Mathematical Induction (PMI) — quick reminder: To prove a statement P(n) for all integers n ≥ n0, use two steps: (1) Base case: show P(n0) is true. (2) Induction step: assume P(k) true for some k ≥ n0 (induction hypothesis) and prove P(k+1). When both hold, P(n) is true for all n ≥ n0.

Structure / checklist for every induction proof: (i) State domain and base n0. (ii) Verify base case. (iii) State induction hypothesis P(k). (iv) Starting from P(k), algebraically reach P(k+1). (v) Conclude by PMI. If the direct step is hard, consider strong induction: assume P(1),...,P(k) to prove P(k+1).

Canonical problem types and why they matter:

• Sum formulas (arithmetic, geometric, powers): common in algebra and sequence problems; induction provides a straightforward verification.
• Sum of odd/even sequences and visual proofs: induction often pairs with geometric/diagrammatic arguments (e.g., building squares).
• Divisibility problems: show expressions are divisible by a fixed integer for all n (use modular arithmetic inside induction).
• Inequalities for integers or growth comparisons (e.g., powers vs polynomials): induction often proves lower/upper bounds.
• Recurrence relations and algorithm correctness: induction (or strong induction) proves formulas or correctness for all steps.

Worked example 1 — Sum of first n natural numbers (standard model): Prove S(n)=1+2+...+n = n(n+1)/2 for n ≥ 1.

Base n=1: S(1)=1 and formula gives 1(2)/2=1. Assume true for k: 1+...+k = k(k+1)/2. Then 1+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 +1) = (k+1)(k+2)/2 = (k+1)(k+2)/2, which is formula with n=k+1. Thus true for all n≥1.

Worked example 2 — Simple divisibility: Prove 7^n − 1 is divisible by 6 for all n ≥ 1.

Base n=1: 7−1=6 divisible by 6. Assume 7^k − 1 = 6m for some integer m. Then 7^{k+1} − 1 = 7·7^k − 1 = 7(7^k −1) + 6 = 7·(6m) + 6 = 6(7m+1), divisible by 6. So holds for all n by induction.

Common pitfalls: forgetting to state the base case, using an incorrect or insufficient induction hypothesis, or mixing up direct and strong induction. Also check domain: often n starts from 0 or 1—be explicit.

When to use strong induction: use when proving P(k+1) needs not only P(k) but several earlier cases (for example, statements about factorizations, representations, or recurrence with order >1). The proof pattern is the same but the hypothesis assumes P(n0),P(n0+1),...,P(k).

Principle of Mathematical Induction (PMI) is a method to prove that a statement P(n) holds for all integers n >= n0. The standard structure is: (i) prove the base case P(n0), (ii) assume P(k) holds for an arbitrary k >= n0 (inductive hypothesis), and (iii) using that assumption prove P(k+1) (inductive step). If both steps are valid, P(n) holds for every n >= n0.

Common pitfalls arise not from the method itself but from mistakes in applying it. The main types of errors are:

• Missing or insufficient base case: Failing to check the correct starting value n0 or checking only P(n0) when the inductive step needs more initial cases (e.g., proving P(k+1) uses P(k−1)). If the base case is false or inadequate, the whole proof collapses.
• Wrong domain or start point: Not specifying or using the correct domain (natural numbers, integers ≥ 2, etc.). Induction only proves for n ≥ the base value—don’t implicitly assume n starts at 1 if it should start at 0 or 2.
• Circular reasoning: Using what you want to prove inside the proof of P(k+1) in a way that presumes the result for k+1 (explicitly or implicitly).
• Illegal algebraic steps: Dividing by an expression that might be zero, cancelling terms that may vanish, or making assumptions about invertibility without verifying them for the k under consideration.
• Confusing implication with equivalence: Showing P(k) implies P(k+1) is fine, but sometimes writers quietly use equivalences that require extra justification. Make sure each algebraic manipulation preserves logical truth in the given direction.
• Improper use of strong induction: Strong (complete) induction assumes P(j) for all j ≤ k and proves P(k+1). Misapplying strong induction by assuming only some of the required earlier cases or failing to check enough base cases is a common error.
• Overlooking special small cases: The inductive step may work for k ≥ some m, not from n0, so you must verify all n in [n0, m] separately.
• Assuming uniqueness or existence without proof: Using existence of a particular object for k or k+1 without justifying it (e.g., dividing by a quantity that could be zero) leads to false conclusions.

Error analysis strategies:

• Always check the base case(s) explicitly—sometimes multiple base cases are needed.
• Test small values of n (n0, n0+1, n0+2…) to find counterexamples quickly.
• Examine algebraic manipulations for steps that require nonzero denominators or other side conditions; state these conditions where needed.
• If you suspect an error, search for the smallest counterexample and use the well-ordering principle: if a false statement has counterexamples, there is a least one—inspect how the induction breaks at that least counterexample.
• When using strong induction, list explicitly which previous cases are assumed and why they imply the next case.
• Write logical implications clearly: state assumptions and derived conclusions at every step to avoid hidden circularity.

Following these checks and being precise about domain, base cases and algebraic conditions will greatly reduce mistakes in induction proofs.

Overview. The Principle of Mathematical Induction (PMI) is a logical tool to prove statements P(n) for all integers n starting from some n0. The section "Connections and Further Remarks" places PMI in a wider mathematical context, shows variants, common uses and pitfalls, and links it to related principles such as strong induction and the well-ordering principle.

Key ideas and variants.

• Standard induction: verify the base case P(n0); assume P(k) true (induction hypothesis); prove P(k+1). This gives P(n) for all n ≥ n0.
• Strong (complete) induction: to prove P(n) for n ≥ n0, assume P(n0), P(n0+1), …, P(k) and prove P(k+1). Useful when P(k+1) depends on several previous values (e.g., recurrence relations, factorization).
• Multiple or shifted base cases: sometimes you must check more than one base case (e.g., P(n0), P(n0+1), …, P(n0+r)) when the induction step needs earlier ones or when recurrence steps by >1.
• Induction starting at other integers: PMI works for any starting integer n0 (not only 1). Always state the starting point.

Connections with other principles.

• Well-ordering principle (WOP): Every nonempty subset of the natural numbers has a least element. WOP, PMI and strong induction are logically equivalent: a proof using one can be converted to a proof using another.
• Proof by contradiction: WOP often converts an induction proof to a contradiction: if some n is the smallest counterexample, you derive a contradiction using smaller cases.
• Recurrence relations and construction: Induction is the natural way to prove formulas for sequences defined recursively (e.g., closed form for linear recurrences) and to justify algorithms built stepwise.

Common applications and typical patterns.

• Proving algebraic identities (sum of first n integers, sum of geometric series, binomial identities).
• Divisibility statements (e.g., 7 | (8^n ? 1) type statements).
• Combinatorial counts and tiling problems (e.g., tiling a 2 × n board uses recursion and induction).
• Number theory results that require strong induction (e.g., every integer >1 factors into primes).

Pitfalls and how to avoid them.

• Failing to check the correct base case(s). If the induction step uses values earlier than k (or leaps by more than 1), you must verify enough initial cases.
• Using a weak induction hypothesis when a strong one is needed. If P(k+1) depends on multiple earlier cases, use strong induction.
• Assuming the statement for all k less than n without justification. Always make the hypothesis explicit.

Why PMI is convincing (intuition). Think of a row of dominoes labelled n0, n0+1, n0+2, ... . The base case knocks down the first domino; the induction step ensures that whenever domino k falls it knocks down domino k+1. Therefore every domino falls. This physical picture explains the chain nature of the logical argument.

Summary. PMI is a foundational proof technique equivalent to other basic principles (WOP, strong induction). Understanding variants, choosing the right form (standard vs strong), and checking appropriate base cases are essential to correct application. The method ties closely to recursion, sequences and constructive procedures in mathematics.

Principle of Mathematical Induction (PMI) — brief: PMI is a method to prove that a statement P(n) holds for all integers n greater than or equal to some initial integer (usually 1 or 0). The standard two-step structure is:

1. Base case: Verify P(n0) is true for the starting n0.
2. Inductive step: Assume P(k) true for some arbitrary k ≥ n0 (the induction hypothesis) and prove P(k+1) follows.

Exercise types:

• Algebraic identities and sums: Prove formulas for finite sums (Σ n, Σ n^2, Σ n^3, geometric sums) or combinatorial identities using induction.
• Divisibility problems: Show an expression is divisible by a fixed integer for all n (use modular arithmetic within the inductive step).
• Inequalities: Prove statements like a_n ≥ b_n or monotonicity (often need a strengthened hypothesis or comparison). Typical forms: 2^n > n^2 for large n, or n! ≥ 2^{n-1}.
• Recurrence and sequence properties: Prove explicit formulas for recurrences or show properties of sequence terms (e.g., parity, bounds).
• Combinatorial/tiling problems: Use induction to prove counts of tilings, colorings, or graph properties; sometimes use strong induction.
• Strong induction / complete induction: When P(k+1) depends on several earlier cases (k, k−1,...), assume P(j) for all j ≤ k to prove P(k+1).

Typical proof pattern / tips:

• Always state the base case clearly (sometimes more than one base case is required, e.g., for recurrence of order >1).
• Write the induction hypothesis explicitly: assume P(k) (or P(1),...,P(k) in strong induction).
• Algebraically transform P(k) into P(k+1) — isolate terms, add/subtract the (k+1)-term, or multiply by a factor.
• For divisibility, reduce modulo m and use that if a ≡ 0 (mod m) then expressions built from a preserve divisibility; often factor expressions to show a multiple of m.
• For inequalities, consider strengthening the hypothesis (prove a stronger but true inequality) so the inductive step becomes easier.
• When induction seems hard, try proving an equivalent statement (e.g., use S(n) = S(n−1)+f(n) for sums, or transform inequality to a product form).
• Check small values explicitly to avoid counterexamples — sometimes the property starts from n = 2, 3 or higher.
• For combinatorial proofs, give a constructive argument that relates the (k+1)-case to earlier cases (often by partitioning configurations by a distinguished element).

Common pitfalls: forgetting to prove (or using) base case(s); assuming what you need to prove inside the inductive step; using an induction hypothesis stronger than what you actually assumed; ignoring domain restrictions (e.g., n ∈ N).