Mathematical Induction, Direct & Indirect Proof – Key Vocabulary

Vocabulary flashcards covering definitions, theorems, and core concepts related to mathematical induction and direct/indirect proofs.

Mathematical Induction

A method of proof used to establish that a statement holds for all natural numbers by verifying a base case and an inductive step.

Principle of Mathematical Induction

States that to prove P(n) for all natural numbers n, one must show (1) Base Step: P(1) is true, and (2) Inductive Step: assuming P(k) is true implies P(k + 1) is true.

Base Step

The part of an induction proof where the statement is verified for the first natural number (usually n = 1).

Inductive Hypothesis

The assumption in an induction proof that P(k) is true for some arbitrary natural number k.

Inductive Step

The portion of an induction proof where one proves that P(k + 1) follows from the inductive hypothesis P(k).

Sum of First n Odd Integers

1 + 3 + 5 + ⋯ + (2n − 1) = n².

Gauss Formula for Natural Numbers

1 + 2 + 3 + ⋯ + n = n(n + 1)/2.

Telescoping Sum Formula

1/[1·2] + 1/[2·3] + ⋯ + 1/[n(n + 1)] = n/(n + 1).

Exponent Rule for Products

For x, y ∈ ℝ and natural n, (xy)ⁿ = xⁿyⁿ.

Parity of 3ⁿ − 1

3ⁿ − 1 is always a multiple of 2 for every natural number n.

Direct Proof

A proof technique that starts from given premises and uses logical steps to arrive directly at the desired conclusion.

Steps in a Direct Proof

(1) Assume the premises, (2) apply logical reasoning and known results, (3) derive the conclusion.

Indirect Proof

Any proof method that establishes a statement by proving an equivalent or related negation, including proofs by contrapositive or contradiction.

Proof by Contrapositive

To prove “If P then Q,” one proves the equivalent statement “If not Q then not P.”

Contrapositive (Logic)

For a conditional P → Q, the contrapositive is ¬Q → ¬P; both are logically equivalent.

Proof by Contradiction

Assumes the negation of the desired statement, derives a logical impossibility, and concludes the original statement must be true.

Reductio ad Absurdum

Latin name for proof by contradiction, meaning “reduced to an absurdity.”

Even Integer

An integer x is even if there exists k ∈ ℤ such that x = 2k.

Odd Integer

An integer x is odd if there exists k ∈ ℤ such that x = 2k + 1.

Rational Number

A real number x that can be expressed as a fraction a/b with a, b ∈ ℤ and b ≠ 0.

Irrational Number

A real number that is not rational; it cannot be written as a ratio of two integers.

Prime Number

A natural number n > 1 that has exactly two positive divisors: 1 and n.

Odd + Odd = Even

If m and n are odd integers, then m + n is an even integer.

Parity Definition

Two integers have the same parity if both are even or both are odd; otherwise, they have different parity.

Complementary Angles Fact

If angles A and B are complementary, then each measure is less than 90°.