maths.free › Discrete Math & Logic › Proof by induction

Proof by induction

Base case, inductive step, strong induction, and the well-ordering principle.

To prove P(n) for all n: prove P(1), then prove P(n) ⇒ P(n + 1). Strong induction assumes all earlier cases. Picture it: the staircase of dominoes. Think it: induction is equivalent to the well-ordering of ℕ — every non-empty set of naturals has a least element.

Ejemplo práctico: sum of k for k = 1 to n

Calculus · Series-And-Sums

Sum k for k = 1 to n

\sum_{k=1}^{n} k

Paso a paso

  1. \sum_{k=1}^{n} k

    Write the sum out.

  2. 1 + 2 + 3 + 4 + \cdots

    The first few terms.

  3. = \frac{n \left(n + 1\right)}{2}

    Closed form (a standard summation formula, provable by induction).

Revelar la respuesta
\frac{n \left(n + 1\right)}{2}

Symbols used here

\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
P(A),\ P(A \mid B)
probability, conditional probability
Chance of A; chance of A given that B happened.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

How to: Proof by induction

  1. State P(n) precisely.
  2. Base case: verify P(1) (or P(0)).
  3. Inductive step: assume P(k), derive P(k + 1), citing the assumption exactly once at least.
  4. Conclude by the principle of induction.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Prueba tu propio

Más en Discrete Math & Logic

Truth tablesSums and inductionAlgorithms and growth of functions