Section 2-4

Principle of Mathematical Induction (PMI)

A method to prove statements about natural numbers by establishing a base case and an inductive step, which includes the basis step showing the initial case and the inductive step demonstrating that if the statement holds for n, it also holds for n+1.

Inductive Definition

A way of defining objects for each natural number n using a base case and a rule for deriving the nth object from the (n-1)th object.

Factorial

The product of all positive integers up to a certain number n, denoted as n!.

Sigma Notation

A concise way to represent the sum of a sequence of terms.

Proof by Induction

A mathematical proof technique that establishes the validity of an infinite sequence of statements, including examples like the sum of the first n odd numbers equals n squared, and divisibility by specific integers for natural numbers.

Divisible

A number a is said to be divisible by another number b if there exists an integer k such that a = b*k.

Inequality

A mathematical expression that shows the relationship between two values where one value is less than or greater than the other.

Generalized Mathematical Induction

A method of induction that can be used under broader circumstances than standard mathematical induction.

Examples in Induction

Specific statements showcasing induction application include: (2i-1)=1+3+5+...+(2n-1)=n², n³ + 5n + 6 divisible by 3, 2ⁿ > n² for n > 4, n³ - n divisible by 6, Σ (2i-1)(2i+1) = 2n+1, 4ⁿ - 1 divisible by 3, and (n³ - n)(n + 2) divisible by 12.

What does PMI stand for?

PMI stands for Principle of Mathematical Induction.

What is the base case in induction?

The base case is the initial step in mathematical induction, where the statement is shown to hold for the first natural number.

How do you prove a statement using induction?

To prove a statement using induction, establish a base case and then show that if the statement is true for n, it is also true for n+1.

What does n! represent?

n! represents the factorial of n, which is the product of all positive integers up to n.

What is Sigma notation used for?

Sigma notation is used to concisely express the sum of a sequence of terms.

Can induction be used for finite sums?

Yes, induction can be used to prove formulas for finite sums.

What is an example of proof by induction?

An example of proof by induction is showing that the sum of the first n odd numbers equals n².

What is a divisible number?

A number is divisible by another number if there exists an integer k such that a = b*k.

What is a generalized induction?

Generalized induction is a form of induction used under broader circumstances than standard mathematical induction.

Name a specific example of induction.

One example is proving that 4ⁿ - 1 is divisible by 3 for all natural numbers n.