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:

  1. Substitute n=1 into both sides of the equation to show that the base case is true.
  2. Substitute n = k into both sides of the equation and assume it is true to obtain Mk.
  3. Prove it is true for n=k+1 by writing Mk+1 as MMk and substituting the Mk from step 2.
  4. Conclude the proof by induction.
steps for doing proof by induction with matrices

For example prove that the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of n equals the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of n Row 2: Column 1, 0 Column 2, 2 to the power of n 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 the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of nbecomes the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the first power which is just the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2.

When n=1, the right hand side of the equation the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of n Row 2: Column 1, 0 Column 2, 2 to the power of n becomes the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the first power Row 2: Column 1, 0 Column 2, 2 to the first power which is just the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2.

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 Mk

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

n=k is substituted into the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of n equals the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of n Row 2: Column 1, 0 Column 2, 2 to the power of n to produce the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of k equals the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of k Row 2: Column 1, 0 Column 2, 2 to the power of k.

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 Mk+1 as MMk and substituting the Mk 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 Mk+1 as MMk
  • Substitute Mk 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.

the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of n equals the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of n Row 2: Column 1, 0 Column 2, 2 to the power of n becomes the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 raised to the k plus 1 power equals the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 raised to the k plus 1 power Row 2: Column 1, 0 Column 2, 2 raised to the k plus 1 power.

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

  • Write Mk+1 as MMk

The first step is to split Mk+1 into MMk.

That is, we write the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 raised to the k plus 1 poweras the product of the two matrices the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the first power the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of k.

  • Substitute Mk 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 thatthe 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of k equals the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of k Row 2: Column 1, 0 Column 2, 2 to the power of k.

Therefore the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the first power the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 to the power of k can be written as the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 times the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of k Row 2: Column 1, 0 Column 2, 2 to the power of k.

  • Multiply the resulting matrices

Multiplying the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 times the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 to the power of k Row 2: Column 1, 0 Column 2, 2 to the power of k using the usual matrix multiplication procedure, we obtain:

the 2 by 2 matrix Row 1: Column 1, open paren 1 times 1 close paren plus open paren negative 1 times 0 close paren Column 2, open paren 1 times open paren 1 minus 2 to the power of k close paren close paren plus open paren negative 1 times 2 to the power of k close paren Row 2: Column 1, open paren 0 times 1 close paren plus open paren 2 times 0 close paren Column 2, open paren 0 times open paren 1 minus 2 to the power of k close paren close paren plus open paren 2 times 2 to the power of k close paren

  • Simplify to obtain the desired result

We wish to show that this above matrix multiplication result leads us to our desired result of the 2 by 2 matrix Row 1: 1 negative 1 Row 2: 0 2 raised to the k plus 1 power equals the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 raised to the k plus 1 power Row 2: Column 1, 0 Column 2, 2 raised to the k plus 1 power.

Evaluating the calculations inside the matrix multiplication, we obtain:

the 2 by 2 matrix Row 1: Column 1, 1 Column 2, open paren 1 minus 2 to the power of k close paren minus 2 to the power of k Row 2: Column 1, 0 Column 2, 2 times 2 to the power of k

This can then simplify as:

the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 times 2 to the power of k Row 2: Column 1, 0 Column 2, 2 times 2 to the power of k

We can write 2 times 2 to the power of k as 2 raised to the k plus 1 power

the 2 by 2 matrix Row 1: Column 1, 1 Column 2, 1 minus 2 raised to the k plus 1 power Row 2: Column 1, 0 Column 2, 2 raised to the k plus 1 power 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 the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the power of n equals the 2 by 2 matrix Row 1: Column 1, n plus 1 Column 2, n Row 2: Column 1, negative n Column 2, 1 minus n

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

the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the first power equals the 2 by 2 matrix Row 1: Column 1, 1 plus 1 Column 2, 1 Row 2: Column 1, negative 1 Column 2, 1 minus 1

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

the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the power of k equals the 2 by 2 matrix Row 1: Column 1, k plus 1 Column 2, k Row 2: Column 1, negative k Column 2, 1 minus k

matrix proof by induction step 1

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 the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 raised to the k plus 1 power equals the 2 by 2 matrix Row 1: Column 1, k plus 1 plus 1 Column 2, k plus 1 Row 2: Column 1, negative open paren k plus 1 close paren Column 2, 1 minus open paren k plus 1 close paren.

This can be simplified as the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 raised to the k plus 1 power equals the 2 by 2 matrix Row 1: Column 1, k plus 2 Column 2, k plus 1 Row 2: Column 1, negative k minus 1 Column 2, negative k. This is the result we are aiming to prove.

We start by writing the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 raised to the k plus 1 power as the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the first power the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the power of k.

We then substitute our assumption from step 2, replacing the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the power of k with the 2 by 2 matrix Row 1: Column 1, k plus 1 Column 2, k Row 2: Column 1, negative k Column 2, 1 minus k so that:

the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the first power the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the power of k becomes the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 to the first power times the 2 by 2 matrix Row 1: Column 1, k plus 1 Column 2, k Row 2: Column 1, negative k Column 2, 1 minus k.

We then multiply these two matrices out so that

the 2 by 2 matrix Row 1: 2 1 Row 2: negative 1 0 times the 2 by 2 matrix Row 1: Column 1, k plus 1 Column 2, k Row 2: Column 1, negative k Column 2, 1 minus k equals the 2 by 2 matrix Row 1: Column 1, open paren 2 times open paren k plus 1 close paren close paren plus open paren 1 times negative k close paren Column 2, open paren 2 times k close paren plus open paren 1 times open paren 1 minus k close paren close paren Row 2: Column 1, open paren negative 1 times open paren k plus 1 close paren close paren plus open paren 0 times negative k close paren Column 2, open paren negative 1 times k close paren plus open paren 0 times open paren 1 minus k close paren close paren

Simplifying these calculations, we obtain:

the 2 by 2 matrix Row 1: Column 1, 2 k plus 2 negative k Column 2, 2 k plus 1 minus k Row 2: Column 1, negative k minus 1 Column 2, negative k which then becomes the 2 by 2 matrix Row 1: Column 1, k plus 2 Column 2, k plus 1 Row 2: Column 1, negative k minus 1 Column 2, negative k which is the result we were trying to prove.

matrix proof by induction step 3

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.

step 4 of proof by induction with matrices

Example 2. Prove that the 2 by 2 matrix Row 1: negative 1 0 Row 2: 2 0 to the power of n equals the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren to the power of n Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren to the power of n Column 2, 1

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

We substitute n=1 on the left hand side of the equation to obtainthe 2 by 2 matrix Row 1: negative 1 0 Row 2: 2 0 to the first power which is the same as the 2 by 2 matrix Row 1: negative 1 0 Row 2: 2 0 raised to the power.

Substituting n=1 on the right hand side, we obtain the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren to the first power Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren to the first power Column 2, 1. Evaluating this, we have the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1.

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 the 2 by 2 matrix Row 1: negative 1 0 Row 2: 2 0 to the power of n equals the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren to the power of n Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren to the power of n Column 2, 1 becomes the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 to the power of k equals the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren to the power of k Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren to the power of k Column 2, 1.

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: the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 raised to the k plus 1 power equals the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren raised to the k plus 1 power Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren raised to the k plus 1 power Column 2, 1.

We then start with the left hand side of the equation and write the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 raised to the k plus 1 power as the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 to the first power the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 to the power of k.

We then use our assumption from step 2 that the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 to the power of k equals the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren to the power of k Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren to the power of k Column 2, 1 to write the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 to the first power the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 to the power of k as the 2 by 2 matrix Row 1: Column 1, negative 1 Column 2, 0 Row 2: Column 1, 2 Column 2, 1 times the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren to the power of k Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren to the power of k Column 2, 1.

We then multiply out these two matrices to obtain the 2 by 2 matrix Row 1: Column 1, open paren negative 1 times open paren negative 1 close paren to the power of k close paren plus open paren 0 times open paren 1 minus open paren negative 1 close paren to the power of k close paren close paren Column 2, open paren negative 1 times 0 close paren plus open paren 0 times 1 close paren Row 2: Column 1, open paren 2 times open paren negative 1 close paren to the power of k close paren plus open paren 1 times open paren 1 minus open paren negative 1 close paren to the power of k close paren close paren Column 2, open paren 2 times 0 close paren plus open paren 1 times 1 close paren

Simplifying the calculations, we obtain the 2 by 2 matrix Row 1: Column 1, open paren negative 1 times open paren negative 1 close paren to the power of k close paren Column 2, 0 Row 2: Column 1, open paren 2 times open paren negative 1 close paren to the power of k close paren plus open paren 1 minus open paren negative 1 close paren to the power of k close paren Column 2, 1.

Since negative 1 times open paren negative 1 close paren to the power of k equals open paren negative 1 close paren raised to the k plus 1 power and 2 times open paren negative 1 close paren to the power of k plus 1 minus open paren negative 1 close paren to the power of k equals 1 plus open paren negative 1 close paren to the power of k, this simplifies further to:

the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren raised to the k plus 1 power Column 2, 0 Row 2: Column 1, 1 plus open paren negative 1 close paren to the power of k Column 2, 1.

Now open paren negative 1 close paren to the power of k 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 negative open paren negative 1 close paren raised to the k plus 1 power.

Therefore we can finish the proof by writing the matrix as the 2 by 2 matrix Row 1: Column 1, open paren negative 1 close paren raised to the k plus 1 power Column 2, 0 Row 2: Column 1, 1 minus open paren negative 1 close paren raised to the k plus 1 power Column 2, 1.

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.

step 4 of proof by induction with matrices