A1 - Induction for matrix powers | AQA A-Level Further Mathematics

A few matrix products can suggest a formula, but they cannot prove it for every positive integer power. You will check a starting case, state an induction hypothesis precisely, and multiply matrices to prove the next case. You will then compare this proof with diagonalisation, including a matrix for which diagonalisation is unavailable.

Checking the first power

Can you prove that every positive integer power of $\mathbf{S}=\begin{pmatrix}1&2\\0&1\end{pmatrix}$ is $\mathbf{S}^n=\begin{pmatrix}1&2n\\0&1\end{pmatrix}$ ? Squaring gives $\begin{pmatrix}1&4\\0&1\end{pmatrix}$ , and cubing gives $\begin{pmatrix}1&6\\0&1\end{pmatrix}$ . The pattern is convincing, but a proof must reach all positive integers, including those you will never calculate individually.

From induction for sums, you know the two essential ingredients: a verified starting case and an implication that carries any valid case to the next. For matrix powers the statement $P(n)$ is a matrix equality, so every corresponding entry must agree.

Basis for a matrix-power induction

If the claim is for every integer $n\ge1$ , its basis is the case $n=1$ . Calculate the actual matrix power $\mathbf{M}^1=\mathbf{M}$ and separately substitute $n=1$ into the proposed formula. Show that they are equal.

A base case tests the complete formula, including constants and signs. It is not enough to write “true for $n=1$ ” without displaying the comparison.

Worked example 1: checking a proposed formula

Question. Verify the basis for $\mathbf{S}^n=\begin{pmatrix}1&2n\\0&1\end{pmatrix}$ , where $\mathbf{S}=\begin{pmatrix}1&2\\0&1\end{pmatrix}$ and $n\ge1$ .

Plan. Evaluate the left side from the definition of a first power, then evaluate the proposed right side at 1.

\begin{aligned} \text{Left side at }n=1:&\quad \mathbf{S}^1=\begin{pmatrix}1&2\\0&1\end{pmatrix}\\ \text{Right side at }n=1:&\quad \begin{pmatrix}1&2(1)\\0&1\end{pmatrix}=\begin{pmatrix}1&2\\0&1\end{pmatrix} \end{aligned}

Answer. The two sides agree, so $P(1)$ is true.

Check. Applying each side to a general vector $(x,y)^{\mathsf T}$ gives $(x+2y,y)^{\mathsf T}$ , so all input vectors receive the same output in this starting case.

Keep the matrix and all other entries the same, but add 1 to the proposed top-right entry. A single entry now breaks the claim immediately.

Worked example 2: a basis that fails

Question. Is $\mathbf{S}^n=\begin{pmatrix}1&2n+1\\0&1\end{pmatrix}$ true for every integer $n\ge1$ ?

Plan. Test $n=1$ before attempting an inductive step.

\mathbf{S}^1=\begin{pmatrix}1&2\\0&1\end{pmatrix},\qquad \begin{pmatrix}1&2(1)+1\\0&1\end{pmatrix}=\begin{pmatrix}1&3\\0&1\end{pmatrix}

The top-right entries are 2 and 3, so the matrices are unequal.

Answer. No. The case $n=1$ is a counterexample to the proposed claim.

Check. On $(0,1)^{\mathsf T}$ , the actual matrix gives $(2,1)^{\mathsf T}$ , while the proposed matrix gives $(3,1)^{\mathsf T}$ . They represent different transformations.

The first formula has passed only its starting check. Even checking another hundred values would still leave infinitely many cases; the inductive implication is what removes that gap. If a problem instead starts at $n=0$ , check $\mathbf{M}^0=\mathbf{I}$ , including for a singular square matrix. Use the domain stated in the question.

Watch out

“Both sides are true” is not a calculation of the basis. Display $\mathbf{M}^1$ , display the formula at $n=1$ , then say that they agree. A failed basis disproves a claim over all $n\ge1$ ; a successful basis does not finish its proof.

Check the complete starting equality for a fresh matrix.

Stating the induction hypothesis

The hypothesis is a temporary assumption about one arbitrary case. It is not a claim that you have already proved every power. Its purpose is to let you replace $\mathbf{M}^k$ while calculating the next power.

Induction hypothesis and target

Assume the proposed matrix equality holds for $n=k$ , where $k\ge1$ is an arbitrary integer. This is the induction hypothesis. The target is the formula with every $n$ replaced by $k+1$ . You must deduce the target from the hypothesis, rather than assuming it too.

Write the target separately to see which expressions must be formed. For example, $2n$ becomes $2(k+1)$ , while $2^n-1$ becomes $2^{k+1}-1$ . Replacing only some occurrences of $n$ changes the intended statement.

Worked example 3: setting up the upper-triangular claim

Question. State the induction hypothesis and next-case target for $\mathbf{S}^n=\begin{pmatrix}1&2n\\0&1\end{pmatrix}$ , where $\mathbf{S}=\begin{pmatrix}1&2\\0&1\end{pmatrix}$ and $n\ge1$ .

Plan. Substitute $k$ into the claimed formula, then separately substitute $k+1$ .

\begin{aligned} \text{Assume:}&\quad \mathbf{S}^k=\begin{pmatrix}1&2k\\0&1\end{pmatrix}\quad\text{for an arbitrary integer }k\ge1\\ \text{To prove:}&\quad \mathbf{S}^{k+1}=\begin{pmatrix}1&2(k+1)\\0&1\end{pmatrix} \end{aligned}

Answer. The first equality is available for substitution; the second is the target that must be established.

Check. At $k=1$ , the target becomes $\mathbf{S}^2=\begin{pmatrix}1&4\\0&1\end{pmatrix}$ , agreeing with a direct square. This checks the indexing, not the full implication.

Transpose the matrix, moving the changing entry below the diagonal. The logic stays the same, but the changing entry of the hypothesis and target must move too.

Worked example 4: the same logic for a lower-triangular claim

Question. State the induction hypothesis and target for $\mathbf{L}^n=\begin{pmatrix}1&0\\2n&1\end{pmatrix}$ , where $\mathbf{L}=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ and $n\ge1$ .

Plan. Keep the matrix-entry positions fixed and replace the index throughout.

\begin{aligned} \text{Assume:}&\quad \mathbf{L}^k=\begin{pmatrix}1&0\\2k&1\end{pmatrix}\quad\text{for an arbitrary integer }k\ge1\\ \text{To prove:}&\quad \mathbf{L}^{k+1}=\begin{pmatrix}1&0\\2(k+1)&1\end{pmatrix} \end{aligned}

Answer. Only the first statement is assumed. The next power must be calculated from it.

Check. Direct multiplication gives $\mathbf{L}^2=\begin{pmatrix}1&0\\4&1\end{pmatrix}$ , matching the target when $k=1$ .

There is no circular argument in temporarily assuming $P(k)$ to prove the conditional statement “if $P(k)$ , then $P(k+1)$ ”. Once that implication is proved for arbitrary $k$ , the verified basis starts the chain. Assuming both cases would remove the very step that needs proof.

Watch out

Wrong: “Assume true for $n=k$ and $n=k+1$ .” Correct: assume the formula for $n=k$ , then prove it for $n=k+1$ . The word if matters in the final implication.

Choose the statement that sets up a valid proof.

Proving the next matrix power

Start with a genuine identity for powers, such as $\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}$ . Substitute the assumed matrix for $\mathbf{M}^k$ , carry out row-by-column multiplication, then simplify until the target appears.

The matrix-power step

For a square matrix $\mathbf{M}$ and a positive integer $k$ ,

\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}=\mathbf{M}\mathbf{M}^k

Either side gives a valid route because both products consist of $k+1$ copies of the same matrix. Use your chosen route consistently. This does not say that two unrelated matrices commute.

Not in the formula booklet: learn it.

The conclusion must connect the pieces: the basis is true, and truth at any $k\ge1$ implies truth at $k+1$ ; therefore the statement holds for all integers $n\ge1$ .

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics

Statistics

Discrete Mathematics

A1 - Induction for matrix powers

Checking the first power

Stating the induction hypothesis

Proving the next matrix power

Continue this lesson.

Learn faster with Nova