How to do Proof by Induction with Matrices

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.

steps for doing proof by induction with matrices

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.

step1 of proof by induction with matrices

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 3 of proof by induction with matrices

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.

step 4 of proof by induction with matrices

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.

proof induction matrices to a power example

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 $the fraction with numerator open paren negative 1 close paren raised to the k plus 1 power and denominator open paren negative 1 close paren to the first power$ which is the same as .

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

harder proof by induction matrices example

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.