﻿ Induction method for square matrices. Exercises resolved.

# Induction method for square matrices. Exercises resolved.

Next I am going to explain to you what the induction method consists of for square matrices, with exercises solved step by step.

The successive powers of a square matrix A follow a certain pattern, which allows us to establish a hypothetical formula that is supposed to be fulfilled for A elevated to n, which will then have to be demonstrated by induction.

## What is the induction method?

The induction method is used to demonstrate that a hypothesis referring to natural numbers n is true for any natural number n. The procedure for demonstrating by induction is as follows:

1. Demonstrate that the base step is met. The base step is when n=1. Therefore, it is necessary to demonstrate that the hypothesis is true for n=1
2. Demonstrate that the induction step is met: We assume that the hypothesis is true for n and calculate that it is met for n+1

If the base step and the induction step are fulfilled, the hypothesis will be demonstrated for any natural number n.

This demonstration process is best understood if you compare it with demonstrating that if in a row of dominoes standing up and if you throw the first one, they will all fall down.

If you had to demonstrate this with the induction method, complying with the base step, you demonstrate that the first tile falls and complying with the induction step, you demonstrate that if the next tile has fallen (n+1) it is because the previous one (n) has fallen previously.

## Example of induction method for square matrices

Let’s see an example of the induction method for square matrices of order 2, when we have a matrix elevated to n:

Demonstrate by induction the following formula is true: First we demonstrate the base step: let’s calculate if the formula is fulfilled for n=1. Replace n with 1 and calculate: The formula is fulfilled for the base step, that is, when n=1.

We continue with the induction step: we assume that the formula is true for n and from there we will demonstrate that it is true for n+1.

To do this we are going to calculate the matrix elevated to n+1: This matrix will be equal to the matrix elevated to n plus the matrix elevated to 1: We apply the induction hypothesis, i.e., we assume that the formula is true for n: And we replace the matrix elevated to n with its result: We multiply matrices and we are left: So, the formula is true for n+1.

Therefore, the two steps are fulfilled, so the formula is true for all natural numbers.

## Resolved exercise of induction method for square matrices

Let’s solve now by the induction method a more complicated exercise:

Given the matrix: Calculate the matrices: And to obtain by the induction method the matrix: We squared A, which will be the multiplication of matrices A by A:   We calculate A to the cube, which will be the multiplication of A by A squared:  And we calculate A elevated to 4, which will be the multiplication of A by A to the cube:  We put the 4 matrices together: And we see that the elements of the matrices can be written as powers of 2: Therefore, we can assume that A elevated to n can have the following expression: But we have to demonstrate by the induction method that this formula is true.

We are going to demonstrate the base step, that in this case, as we are asked to demonstrate for n greater than 4, the base step will be when n=5.

We calculate A raised to 5, which will be the multiplication of A by A raised to 4:  On the other hand, we calculated A elevated to 5 with the formula:  And we see that they coincide, so the formula is fulfilled for the base case, when n=5.

We continue with the induction step: we suppose that the formula is true for n and from there we are going to demonstrate that it is true for n+1.

We calculate A elevated to n+1, which will be the multiplication of A elevated to n by A. A elevated to n we substitute it according to the formula and it remains: Now we multiply matrices. We see that adding the same element is equal to multiplying it by 2: And now in each element, we maintain the base and add the exponents: The formula is fulfilled for n+1.

Therefore, both the base step and the induction step are met, so it is proven that the formula is true for all natural numbers.