# A calculus of the absurd

##### 22.1.7 Raising matrices to powers
Example

: The matrix $$A$$ is defined as

$$A := \begin{pmatrix} 2 & 3 \\ 0 & 2 \end {pmatrix}$$

By considering $$A$$, $$A^2$$, $$A^3$$ and $$A^4$$, make a conjecture about $$A^n$$, and then prove this conjecture by induction.

Solution

: Although it’s tempting to reach for one’s calculator to compute $$A$$, $$A^2$$, $$A^3$$ and $$A^4$$, it makes things harder.

When we multiply $$A$$ by $$A$$, we get that

$$A^2 = \begin{pmatrix} 2^2 & 2\cdot 3 + 3\cdot 2 \\ 0 & 2^2 \end {pmatrix}$$

If we then multiply this by $$A$$ again, we get that

$$A^3 = \begin{pmatrix} 2^3 & 2(2\cdot 3 + 3\cdot 2) + 3\cdot 2^2 \\ 0 & 2^3 \end {pmatrix}$$

We can multiply out the bracket and get that

\begin{align} 2(2\cdot 3 + 3\cdot 2) + 3\cdot 2^2 & = 2^2\cdot 3 + 2^2\cdot 3 + 3\cdot 2^2 \\ & = 2^2\cdot 3 + 2^2\cdot 3 + 2^2\cdot 3 \\ & = 3\cdot 2^2\cdot 3 \end{align}

Simplifying here is a bad idea, as we’re looking for patterns, and these are easier to spot when we have more information to work with (which we do when we think about the factors of our numbers.)

Multiplying to find $$A^4$$ we get that

$$A^4 = \begin{pmatrix} 2^4 & 2(3\cdot 2^2\cdot 3) + 3\cdot 2^3 \\ 0 & 2^4 \end {pmatrix}$$

We can simplify this a bit, because

\begin{align} 2(3\cdot 2^2\cdot 3) + 3\cdot 2^3 & = 3\cdot 2^3\cdot 3 + 3\cdot 2^3 & = 4\cdot 2^3\cdot 3 \end{align}

This implies that

$$A^4 = \begin{pmatrix} 2^4 & 4\cdot 2^3\cdot 3 \\ 0 & 2^4 \end {pmatrix}$$

Looking at these four matrices, the general shape is something like

$$A^n = \begin{pmatrix} 2^n & n\cdot 2^{n-1}\cdot 3 \\ 0 & 2^n \end {pmatrix}$$

There’s another way of doing this, but the maths behind it isn’t on the A Level specification. It’s the way I originally did it.

From the initial multiplication, we can see that the general shape of $$A^n$$ is

$$\begin{pmatrix} 2^n & ? \\ 0 & 2^n \end {pmatrix}$$

Here the $$?$$ denotes the confusion about what $$A_{1,2}$$ is. In terms of notation, it’s slightly more handy to call $$?$$ something more like $$f(n)$$.

We can also write the matrix $$A^n$$ as $$A A^{n-1}$$.

$$A^n = \begin{pmatrix} 2 & 3 \\ 0 & 2 \end {pmatrix} \begin{pmatrix} 2^{n-1} & f(n-1) \\ 0 & 2^{n-1} \end {pmatrix}$$

We can apply the standard rules of matrix multiplication to the above.

$$A^n = \begin{pmatrix} 2^{n} & 2f(n-1) + 3\cdot 2^{n-1} \\ 0 & 2^{n} \end {pmatrix}$$

We can compare the value of $$A^n$$ we have computed here (in terms of $$f(n-1)$$) to the one we’d like to know (that of $$f(n)$$). This gives

$$f(n) = 2f(n-1) + 3\cdot 2^{n-1}$$

We also know that $$f(1) = 3$$. To find a closed-form expression for $$f(n)$$, we can just keep substituting:

\begin{align} f(n) & = 2(2f(n-2)+3\cdot 2^{n-2}) + 3\cdot 2^{n-1} \\ & = 2^2f(n-2) + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} \\ & = 2^2(2f(n-3) + 3\cdot 2^{n-3}) + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} \\ & = 2^3f(n-3) + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} + 3\cdot 2^{n-1} \\ & = n \cdot 3 \cdot 2^{n-1} \end{align}

The last step isn’t necessarily immediately obvious (doing the expansion by hand might make it easier to understand). The other way to think about this is by using one of the helpful heuristics looked at in the heuristics section, in this case “wherever possible, draw a diagram” 127127 Unfortunately, it’s not a great diagram (but I tried)..

The sum of each node $$f(n)$$ in the tree is $$2f(n-1) + 3\cdot 2^{n-1}$$ - the $$2f(n-1)$$s are drawn as children of the parent node. We want to find the sum of all the nodes in the tree. To do this, note that we have $$n$$ levels of the tree and at each level the nodes sum to $$3\cdot 2^{n-1}$$, and thus overall we have that $$f(n)$$ is equal to the sum of all the nodes, which is equal to $$n\cdot 3\cdot 2^{n-1}$$.

It’s all downhill (in difficulty) from here!

For the proof by induction, if we set

$$P(n) = \begin{pmatrix} 2^n & n\cdot 2^{n-1}\cdot 3 \\ 0 & 2^n \end {pmatrix}$$

then we want to show that $$A^n = P(n)$$ for every natural number.

We start with the basis case: as $$A^1 = A$$, it is clear that $$A^1 = P(1)$$.

For the inductive step, we assume that $$P(k) = A^k$$, and then we consider $$P(k+1)$$, which is equal to $$A^{1}A^{k}$$. To this expression, we can now apply the inductive hypothesis (always be looking at $$P(k+1)$$ to see where $$P(k)$$ has been hidden!) and thus this expression is equal to $$A P(k)$$. We can then carry out the multiplication

$$\begin{pmatrix} 2 & 3 \\ 0 & 2 \end {pmatrix} \begin{pmatrix} 2^k & k\cdot 2^{k-1}\cdot 3 \\ 0 & 2^k \end {pmatrix} = \begin{pmatrix} 2\cdot 2^k & 2(k\cdot 2^{k-1}\cdot 3) + 3\cdot 2^{k} \\ 0 & 2\cdot 2^k \end {pmatrix}$$

This can then be rewritten as

$$\begin{pmatrix} 2^{k+1} & k\cdot 2^{k}\cdot 3 + 3\cdot 2^{k} \\ 0 & 2^{k+1} \end {pmatrix}$$

and as $$k\cdot 2^{k}\cdot 3 + 3\cdot 2^{k}$$ is equal to $$2^{k}\cdot 3\cdot (k+1)$$ we have that

$$\begin{pmatrix} 2^{k+1} & 2^{k}\cdot 3\cdot (k+1) \\ 0 & 2^{k+1} \end {pmatrix}$$

The final step is to rewrite the $$2^{k}$$ as $$2^{(k+1)-1}$$, and then we have

$$\begin{pmatrix} 2^{k+1} & (k+1) \cdot 2^{(k+1)-1}\cdot 3 \\ 0 & 2^{k+1} \end {pmatrix}$$

Thus as $$P(n)$$ is true for $$n=1$$ and $$P(n)$$ implies that $$P(n+1)$$ is true, $$P(n)$$ must hold for all $$n$$.