## Video Lesson: Proof by Induction with Matrices

## How to do Proof by Induction with Matrices

**To do proof of induction with matrices:**

- Substitute n=1 into both sides of the equation to show that the base case is true.
- Substitute n = k into both sides of the equation and assume it is true to obtain M
^{k}. - Prove it is true for n=k+1 by writing M
^{k+1}as MM^{k}and substituting the M^{k}from step 2. - Conclude the proof by induction.

For example prove that using induction.

**Step 1. Substitute n=1 into both sides of the equation to show that the base case is true**

The goal of this first step is to show that both sides of the equation are equivalent for a given value. We choose a simple value such as n=1 and this is known as our base case.

When n=1, the left hand side of the equation becomes which is just .

When n=1, the right hand side of the equation becomes which is just .

We can see that substituting n=1 into both sides of the equals sign produces the same result.

**Step 2. Substitute n = k into both sides of the equation and assume it is true to obtain M ^{k}**

In this step, it is assumed the result is true for when n=k.

n=k is substituted into to produce .

No proof is required at this stage because it is *assumed* that this result is true. Therefore the left hand side of the equation is set equal to the right hand side.

**Step 3. Prove it is true for n=k+1 by writing M ^{k+1} as MM^{k} and substituting the M^{k} from step 2**

Step 3 is the inductive step in which the algebraic proof is required to prove the n=k+1 case.

For proof by induction involving matrices, this requires the following steps:

- Write M
^{k+1}as MM^{k} - Substitute M
^{k}for the assumption made in the n=k case - Multiply the resulting matrices
- Simplify to obtain the desired result

It is first helpful to decide what outcome we wish to prove. That is, we substitute n=k+1 into both sides of the equals sign.

becomes .

To prove this result, we use the steps listed in the list above.

- Write M
^{k+1}as MM^{k}

The first step is to split M^{k+1} into MM^{k}.

That is, we write as the product of the two matrices .

- Substitute M
^{k}for the assumption made in the n=k case

From step 2, we assumed the result was true when n=k. That was, we assumed that.

Therefore can be written as .

- Multiply the resulting matrices

Multiplying using the usual matrix multiplication procedure, we obtain:

- Simplify to obtain the desired result

We wish to show that this above matrix multiplication result leads us to our desired result of .

Evaluating the calculations inside the matrix multiplication, we obtain:

This can then simplify as:

We can write as

which is the desired result.

**Step 4. Conclude the proof by induction**

The result was proven true for the case where n=k+1 using the assumption that n=k is true.

This means that for every true result (n=k), the following result (n=k+1) must be true as well.

Since we showed that the first base case (n=1) was true, then the result is true for all positive integer values of n.

## Proof by Induction Matrices Questions

Here are some examples of using proof by induction to prove results of matrices raised to powers.

**Example 1.** Prove that

Step 1 is to verify the n=1 case by substituting n=1 into both sides of the equation to obtain:

We can see that this result is true.

Step 2 is to assume that the result is true for n=k.

That is, we substitute n=k into both sides of the equation to obtain

Step 3 is to show the result is true for n=k+1.

We wish to prove that the result obtained when n=k+1 is substituted in is true. That is .

This can be simplified as . This is the result we are aiming to prove.

We start by writing as .

We then substitute our assumption from step 2, replacing with so that:

becomes .

We then multiply these two matrices out so that

Simplifying these calculations, we obtain:

which then becomes which is the result we were trying to prove.

Step 4 requires us to conclude the proof by stating that since the statement is true for n=k+1 when true for n=k and true for n=1, the statement is true for all positive integers.

**Example 2. **Prove that

Step 1 is to verify the result for n=1.

We substitute n=1 on the left hand side of the equation to obtain which is the same as .

Substituting n=1 on the right hand side, we obtain . Evaluating this, we have .

Step 2 is to assume the result is true for n=k.

We substitute n=k into both sides of the equals sign so that becomes .

We assume this result is true.

Step 3 is to prove the result is true for n=k+1.

We substitute n=k+1 into both sides to see what we are hoping to prove. That is: .

We then start with the left hand side of the equation and write as .

We then use our assumption from step 2 that to write as .

We then multiply out these two matrices to obtain

Simplifying the calculations, we obtain .

Since and , this simplifies further to:

.

Now is the same as which is the same as .

Therefore we can finish the proof by writing the matrix as .

Step 4 is our conclusion of the proof, stating that since the statement is true for n=k+1 when true for n=k and the base case of n=1 is true, then the statement is true for all positive integer values of n.