Lesson 1.4: Induction with Sequences, Inequalities, and Matrices

Introduction

Welcome, students! In this lesson, we will delve into the concept of mathematical induction, which is a powerful tool used in proving various mathematical statements. Our focus will be on applying induction to recursively defined sequences, proving inequalities, deriving formulas for matrices, and ensuring that our inductive arguments are flawed-free! The objectives are to equip you with the methods to tackle these topics confidently.

Learning Objectives:

• Apply induction to recursively defined sequences.
• Prove inequalities using induction.
• Prove a formula for the n-th power of a 2×2 matrix.
• Identify and correct flawed "inductive" arguments.
• Establish a closed form for a recurrence relation via induction.

Understanding Mathematical Induction

Mathematical induction allows us to prove statements that can be defined for all integers greater than or equal to some base case, typically 1. The process consists of two main steps: the base case and the inductive step.

1. Base Case: Prove that the statement holds for the initial value (usually n = 1).
2. Inductive Step: Assume the statement is true for some integer k (this is called the inductive hypothesis) and then prove that it must also be true for k + 1.

For example, let’s prove that for all integers $n \geq 1$, the following formula holds:

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$

Base Case:

For $n = 1$, we have:

$$\sum_{i=1}^{1} i = 1 = \frac{1(1+1)}{2}$$

This holds true!

Inductive Step:

Assume it holds for $n = k$:

$$\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$$

Now we show it holds for $n = k + 1$:

$$\sum_{i=1}^{k+1} i = \sum_{i=1}^{k} i + (k + 1) = \frac{k(k+1)}{2} + (k + 1)$$

Factoring gives us:

$$\sum_{i=1}^{k+1} i = \frac{k(k+1) + 2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2}$$

This proves our statement is true for $n = k + 1$, completing the induction.

Induction with Recursively Defined Sequences

Recursively defined sequences are defined by previous terms in the sequence. For example:

• $a_1 = 2$
• $a_n = 3a_{n-1} + 4$ for $n > 1$

To find a closed form solution and validate it, we can use mathematical induction. First, we guess a formula. Let's say we suspect:

$$a_n = 3^n + 2$$

Base Case:

For $n = 1$, we have:

$$a_1 = 3^1 + 2 = 3 + 2 = 5$$

(but $a_1$ is actually 2 according to our definition)

So, we revise our formula as per the requirement of our sequence. After testing further, let’s say we find:

$$a_n = 3^n - 1$$

Then, we perform induction:

Inductive Step:

Assume true for $n = k$:

$$a_k = 3^k - 1$$

Then for $n = k + 1$:

$$a_{k+1} = 3a_k + 4 = 3(3^k - 1) + 4 = 3^{k+1} - 3 + 4 = 3^{k+1} - 1$$

Hence, our hypothesis is true!

Proving Inequalities by Induction

Proving inequalities often requires a similar approach. Let's prove that for every integer $n \geq 1$:

$$2^n > n \text{ for } n \geq 1$$

Base Case:

For $n = 1$:

$$2^1 = 2 > 1$$

Holds true!

Inductive Step:

Assume true for $n = k$:

$$2^k > k$$

Now, prove for $n = k + 1$:

$$2^{k + 1} = 2 \cdot 2^k > 2k.$$

\

Since $k \geq 1$, we have:

$$2k \geq k + 1 \Rightarrow 2k - k > 1,$$

leading us to correct our path following the inequality reasoning and shifting between cases. This method effectively shows $2^{k + 1} > k + 1$.

Proving Formulas for Matrix Powers

Lastly, let’s prove the formula for the n-th power of a 2×2 matrix:

$$A^n = \begin{pmatrix} a & b \\ c & d \end{pmatrix}^n$$

We start by checking for base case n = 1, where it holds trivially as:

$$A^1 = A$$

Then for the inductive step, using properties of matrices and products:

$$A^{k + 1} = A^k \cdot A$$

Assuming we have a form:

$$A^k = P \text{ for some expression in } P$$

and manipulate through rules of matrix equality and induction properties to achieve our end.

Conclusion

In this lesson, students, we've explored the essential role of mathematical induction in validating statements and building robust proofs. From sequences to inequalities, and even matrices, we have seen how induction serves as a foundational technique in mathematics. Keep practicing these methodologies to enhance your understanding and prove a broader range of mathematical claims.

Study Notes

• Mathematical induction includes base case and inductive step.
• Induction is powerful in sequences, inequalities, and matrix proofs.
• For recursive sequences, guess the formula and prove by induction!
• Inequalities can also be proven using the inductive hypothesis.
• Matrix power proofs require clever manipulation of matrix multiplication.