Mathematical Induction, Discrete Probability and Bayes' Theorem

Unit 1 groups Counting, Mathematical Induction and Discrete Probability under one head. The counting half — permutations, combinations, pigeonhole and inclusion-exclusion — has its own combinatorics chapter in this course. This chapter is the rest of that syllabus line: proof by mathematical induction, the axioms of probability, conditional probability, and Bayes' theorem, which NET asks both as a formula to apply and as a concept (the base-rate fallacy) to reason about correctly.

Mathematical Induction — the Two Steps and Where They Fail

A proof by (weak) induction that a statement P(n) holds for every n ≥ n₀ has two obligations. The base case verifies P(n₀) directly. The inductive step assumes P(k) — the induction hypothesis — for some arbitrary k ≥ n₀, and derives P(k+1) from it. Both steps are necessary and neither alone is a proof: a false base case with a perfectly correct inductive step proves nothing about any actual n, and a true base case with no valid inductive step establishes only P(n₀) itself. Strong induction assumes P(n₀), P(n₀+1), …, P(k) all hold — not just P(k) — to derive P(k+1); it is not logically stronger in what it can prove, but it is often the only form that makes the derivation possible, for example when P(k+1) genuinely depends on P(k−3) rather than P(k) alone (as in a recurrence with more than one term, or a proof that every integer greater than 1 has a prime factor).

A worked induction: 1 + 2 + ... + n = n(n+1)/2
StepWhat is shown
Base, n = 1LHS = 1, RHS = 1(2)/2 = 1. Equal.
HypothesisAssume 1 + ... + k = k(k+1)/2 for some k ≥ 1.
Step, n = k+11+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2, which is the formula at n = k+1.
⚠️ A missing base case is the classic fake induction
The joke proof that all horses are the same colour skips checking n = 1 honestly (the inductive step it offers actually needs two horses to overlap, which fails to bridge from one horse to two) — the flaw is always in one of the two obligations, never in some third hidden step. When reading a purported induction, check the base case is checked at the SMALLEST n the claim is stated for, and check the inductive step does not silently assume something true only for larger k.

The Axioms of Probability and Conditional Probability

  • Kolmogorov's axioms: for a sample space S, P(A) ≥ 0 for every event A; P(S) = 1; and for mutually exclusive A, B, P(A ∪ B) = P(A) + P(B). Everything else — P(∅) = 0, P(Aᶜ) = 1 − P(A), P(A ∪ B) = P(A) + P(B) − P(A ∩ B) for events that may overlap — follows from these three.
  • Conditional probability: P(A|B) = P(A ∩ B)/P(B), defined only when P(B) > 0 — the probability of A given that B is already known to have occurred, restricting the sample space to B.
  • Independence: A and B are independent exactly when P(A ∩ B) = P(A)·P(B), equivalently P(A|B) = P(A) — knowing B occurred changes nothing about A's likelihood. Independence must be checked, never assumed from the events sounding unrelated.
🎯 The law of total probability partitions the sample space
If B₁, …, Bₙ partition S (mutually exclusive, exhaustive, each with positive probability), then P(A) = Σᵢ P(A|Bᵢ)·P(Bᵢ). This is the identity Bayes' theorem's denominator is built from, and it is the standard tool when a direct count of P(A) is awkward but P(A) conditioned on each of a few clean cases is easy — for instance, a defective item drawn from one of three machines, each with a known defect rate and a known share of total production.

Bayes' Theorem, and the Base-Rate Fallacy It Corrects

Bayes' theorem inverts a conditional: P(Bᵢ|A) = [P(A|Bᵢ)·P(Bᵢ)] / [Σⱼ P(A|Bⱼ)·P(Bⱼ)]. Read in words, it updates a prior belief P(Bᵢ) into a posterior P(Bᵢ|A) once evidence A is observed, weighted by how well Bᵢ predicts A (the likelihood P(A|Bᵢ)) against how well every other hypothesis predicts it. The single most commonly mis-set NET/GATE-style question is a medical test: a disease with prevalence (prior) 1%, a test with 99% sensitivity (true positive rate) and 95% specificity (true negative rate, so a 5% false positive rate). The probability that a person who tests positive actually has the disease is NOT 99% — applying Bayes with P(disease)=0.01, P(+|disease)=0.99, P(+|no disease)=0.05, P(no disease)=0.99 gives P(disease|+) = (0.99×0.01)/(0.99×0.01 + 0.05×0.99) ≈ 0.167, about 17%. The test is accurate, but the disease is rare, so false positives from the large healthy population outnumber true positives from the small sick population — this is the base-rate fallacy, and it is exactly what ignoring the prior P(Bᵢ) produces.

🧠 Build a 2x2 count table instead of the formula under pressure
Take 10,000 people. 1% have the disease: 100 sick, 9,900 healthy. Of the 100 sick, 99% test positive: 99 true positives. Of the 9,900 healthy, 5% test positive: 495 false positives. Total positives = 99 + 495 = 594, of which 99 are truly sick: 99/594 ≈ 0.167 — the same answer, reached by counting rather than by the fraction formula, and far harder to get wrong under time pressure.

Random Variables, Expectation and Common Distributions

  • Expectation E[X] = Σₓ x·P(X = x) for a discrete random variable; it is linear — E[X + Y] = E[X] + E[Y] — always, whether or not X and Y are independent, which is a fact worth applying directly rather than re-deriving.
  • Binomial B(n, p): the number of successes in n independent trials each with success probability p. Mean np, variance np(1−p). The classic GATE/NET-style setup is n coin tosses or n bits of a channel.
  • Bernoulli is the single-trial special case of Binomial with n = 1. Poisson approximates Binomial when n is large and p small with np held moderate (rare events over a fixed interval); its mean equals its variance, both λ.
  • Uniform, discrete on {1, …, n}: each outcome equally likely, mean (n+1)/2 — the standard model for an unbiased die or a random array index.

Key takeaways

  • Induction needs BOTH a correct base case and a correct inductive step; either alone proves nothing. Strong induction may assume every prior case, not just the immediately preceding one.
  • Kolmogorov's three axioms generate every other probability identity. Conditional probability P(A|B) = P(A∩B)/P(B) restricts the sample space to B.
  • Bayes' theorem inverts P(A|B) into P(B|A) weighted by the prior. Ignoring a low prior (base-rate fallacy) is the single most common Bayes error — build a 2x2 count table to avoid it.
  • Expectation is always linear, independence or not: E[X+Y] = E[X] + E[Y].
  • Binomial, Bernoulli (its n=1 case) and Poisson (its large-n, small-p, moderate-np limit) are the three discrete distributions NET tests most, each with its own mean/variance formula.

Practice questions (9)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. A proof by mathematical induction on P(n) for n ≥ 1 is INCOMPLETE if it:

    1. Verifies P(1) but never proves P(k) → P(k+1) for arbitrary k
    2. Uses strong induction instead of weak induction
    3. Proves the inductive step before stating the base case
    4. States the hypothesis for a specific k rather than a general one
    Show answer

    Answer: A — Verifies P(1) but never proves P(k) → P(k+1) for arbitrary k

    A proof needs both the base case AND a generally-quantified inductive step; verifying only the base case, or only a specific instance rather than an arbitrary k, leaves the chain of implications unestablished.

  2. Strong induction differs from weak (ordinary) induction in that:

    1. It assumes P holds for all values from the base case up to k, not just at k, to derive P(k+1)
    2. It requires no base case
    3. It can prove statements that are actually false
    4. It only works for statements about integers less than 10
    Show answer

    Answer: A — It assumes P holds for all values from the base case up to k, not just at k, to derive P(k+1)

    Strong induction's hypothesis is P(n₀) ∧ P(n₀+1) ∧ ... ∧ P(k), which is needed whenever the step to k+1 genuinely depends on some earlier case besides k itself.

  3. Events A and B are independent if and only if:

    1. P(A ∩ B) = P(A)·P(B)
    2. A and B are mutually exclusive
    3. P(A ∪ B) = P(A) + P(B)
    4. P(A) = P(B)
    Show answer

    Answer: A — P(A ∩ B) = P(A)·P(B)

    Independence is P(A∩B) = P(A)P(B). Mutual exclusivity is a different (and, for events of positive probability, opposite) condition — two mutually exclusive events with positive probability are never independent, since one occurring makes the other's probability zero.

  4. A disease has 1% prevalence. A test is 99% sensitive and 95% specific. A random person tests positive. The probability they actually have the disease is closest to:

    1. 17%
    2. 99%
    3. 95%
    4. 50%
    Show answer

    Answer: A — 17%

    Per 10,000 people: 100 sick (99 true positives), 9,900 healthy (495 false positives at a 5% false-positive rate). Of 594 total positives, 99 are truly sick: 99/594 ≈ 17%. The 99% figure is the test's sensitivity, P(+|disease) — not the quantity asked, P(disease|+); confusing the two is exactly the base-rate fallacy.

  5. The law of total probability requires the conditioning events B₁, ..., Bₙ to be:

    1. Mutually exclusive and exhaustive (a partition of the sample space)
    2. Independent of each other
    3. Equally likely
    4. Each with probability greater than 0.5
    Show answer

    Answer: A — Mutually exclusive and exhaustive (a partition of the sample space)

    P(A) = Σ P(A|Bᵢ)P(Bᵢ) is valid precisely because the Bᵢ partition S — every outcome falls in exactly one Bᵢ, so summing over them double-counts nothing and misses nothing.

  6. For any two random variables X and Y (not necessarily independent), E[X + Y] equals:

    1. E[X] + E[Y], always
    2. E[X] + E[Y], only if X and Y are independent
    3. E[X]·E[Y]
    4. It cannot be determined without knowing the joint distribution
    Show answer

    Answer: A — E[X] + E[Y], always

    Linearity of expectation holds unconditionally — no independence assumption is needed, unlike the product rule for variance or for E[XY], which do require it.

  7. The Poisson distribution is typically used as an approximation to the Binomial distribution when:

    1. n is large, p is small, and np stays moderate
    2. n is small and p is close to 0.5
    3. The trials are dependent on each other
    4. Variance exceeds the mean by a large margin
    Show answer

    Answer: A — n is large, p is small, and np stays moderate

    The Poisson limit applies to rare events over many trials — large n, small p, with λ = np held fixed and moderate. In this limit both the mean and the variance of the Binomial converge to λ, matching the Poisson's own property that mean equals variance.

  8. Which of the following follow directly from Kolmogorov's three axioms? (More than one option may be correct.)

    1. P(∅) = 0
    2. P(Aᶜ) = 1 − P(A)
    3. P(A) is always exactly 0.5 for any event A
    4. P(A ∪ B) = P(A) + P(B) − P(A ∩ B) for any A, B
    Show answer

    Answer: A — P(∅) = 0; B — P(Aᶜ) = 1 − P(A); D — P(A ∪ B) = P(A) + P(B) − P(A ∩ B) for any A, B

    P(∅)=0 and P(Aᶜ)=1−P(A) follow from additivity applied to A and Aᶜ (which partition S), and the general union formula corrects the double count in A∩B when A and B overlap. There is no axiom fixing every event's probability at 0.5.

  9. A fair coin is tossed 4 times. Using the Binomial distribution, the expected number of heads is _____.

    Numerical answer — type the value.

    Show answer

    Answer: 2

    For Binomial(n, p), mean = np. Here n = 4, p = 0.5, so mean = 4 × 0.5 = 2.