Induction: Prove that $(A_{1}A_{2}..A_{n-1}A_{n})^{T} = A_{n}^{T}A_{n-1}^{T}..A_{2}^{T}A_{1}^{T}$

Question

I'm currently reading book on linear algebra where author presents concept of the "mathematical induction". The author explains 3 steps of mathematical induction:

Step 1. Check the result is true for some base case such as $n = 1$

Step 2. Assume the result is true for $n = k$.

Step 3. Prove the result for $n = k + 1$ by using steps $1$ and $2$

Honestly, I'm confused about step 2. Namely, how can we assume that the result is true for some arbitrary value $k$? Isn't it what we are actually required to prove?

In an attempt to make my question clearer, I'll provide an example:

The author presents following proposition:

Proposition 1. Let $\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{n-1}\mathbf{A}_{n}$ be matrices of the approriate size so that they can be multiplied. Then we have $(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{n-1}\mathbf{A}_{n})^{T} = \mathbf{A}_{n}^{T}\mathbf{A}_{n-1}^{T}...\mathbf{A}_{2}^{T}\mathbf{A}_{1}^{T}$

His proof:

Check the result for $n = 2$: $$\tag1(\mathbf A_{1}\mathbf A_{2})^{T} = \mathbf A_{2}^{T}\mathbf A_{1}^{T}$$

Assume result is true for $n = k$:

$$\tag2(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k})^{T} = \mathbf{A}_{k}^{T}\mathbf{A}_{k-1}^{T}...\mathbf{A}_{2}^{T}\mathbf{A}_{1}^{T}$$

Required to prove the result for $n = k + 1$, that is we need to prove:

$$\tag3(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k}\mathbf{A}_{k+1})^{T} = \mathbf{A}_{k+1}^{T}\mathbf{A}_{k}^{T}\mathbf{A}_{k-1}^{T}...\mathbf{A}_{2}^{T}\mathbf{A}_{1}^{T}$$

Expanding the Left Hand Side $(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k}\mathbf{A}_{k+1})^{T}$ gives:

$$(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k}\mathbf{A}_{k+1})^{T} = ((\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k})\mathbf{A}_{k+1})^{T} = \mathbf{A}_{k+1}^{T}(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k})^{T}$$

Using the result we obtained in $(2)$: $$\mathbf{A}_{k+1}^{T}(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k})^{T} = \mathbf{A}_{k+1}^{T}\mathbf{A}_{k}^{T}\mathbf{A}_{k-1}^{T}...\mathbf{A}_{2}^{T}\mathbf{A}_{1}^{T}$$

As desired. $\Box$

OK, so now I repeat my question:

How can we assume that proposition holds true for some arbitrary value $k$, if this is what we actually are required to prove? We didn't actually obtain the result in (2), we just assumed that it is true.

I'd thought that the proof would need to look like this:

1. Check the result for $n = 2$: $$\tag1(\mathbf A_{1}\mathbf A_{2})^{T} = \mathbf A_{2}^{T}\mathbf A_{1}^{T}$$

2. Now pick some arbitrary value $n = k$. Required to prove that proposition holds for $k$, i.e:

$$\tag2(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k})^{T} = \mathbf{A}_{k}^{T}\mathbf{A}_{k-1}^{T}...\mathbf{A}_{2}^{T}\mathbf{A}_{1}^{T}$$

Using property we discovered in (1) $$\tag2(\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1}\mathbf{A}_{k})^{T} = ((\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1})\mathbf{A}_{k})^{T} = \mathbf{A}_{k}^{T} (\mathbf{A}_{1}\mathbf{A}_{2}...\mathbf{A}_{k-1})^{T}$$

Repeat the same step one more time

$$\mathbf{A}_{k}^{T} ((\mathbf{A}_{1}\mathbf{A}_{2}...)\mathbf{A}_{k-1})^{T} = \mathbf{A}_{k}^{T} \mathbf{A}_{k-1}^{T}(\mathbf{A}_{1}\mathbf{A}_{2}...)^{T}$$

Using the same process for the remaining matrices within brackets, finally we arrive at:

$$\mathbf{A}_{k}^{T}\mathbf{A}_{k-1}^{T}...\mathbf{A}_{2}^{T}\mathbf{A}_{1}^{T}$$

As desired. $\Box$

What am I missing?

Answer 1

This is the structure of all proofs by induction.

Show that the proposition is true in some base case. Assume that it is true in some general case (the inductive hypothesis). Based on the hypothesis, show that when it holds for some value of n, that it also holds for the value $n+1$

i.e. you have shown that the proposition holds when $k = 2$

And whenever it holds for some $k,$ it must also hold for $k+1.$ So, it must hold when k= 3, since it holds when $k = 2$

And it must hold when $k=4$ since it holds when $k = 3$

And following this logic along, it holds for all integers greater than or equal to 2.

https://en.wikipedia.org/wiki/Mathematical_induction

Answer 2

Principle of Mathematical Induction is just the mathematical representation for the game of Dominoes. How do you ensure that all the dominoes fall? You need two conditions:

1) The first one falls.

2) Whenever one falls, it pushes the next one.

The basis step represents the first one and the hypothesis and inductive steps together represent the second step. What does they say? They say that when the proposition is true for a natural number, it is true for the next natural number.

This ensures that the given proposition is true for all natural numbers. Otherwise, the first tile that couldn't fall was not pushed by the previous one.

Hope it helps:)