Valid induction?

Question

The problem was presented like this:

$A_{2n} = \begin{bmatrix} a & 0 & \cdots & 0 & b\\ 0 & a & \cdots & b & 0\\ & & \cdots & & \\ 0 & b & \cdots & a & 0\\ b & 0 & \cdots & 0 & a \end{bmatrix} n \in N, A_{0} = 1 $

Show that $detA_{2n} = (a^{2} - b^{2}) \cdot detA_{2n-2}$

I tried to use induction for this case:

Base case:

$n=1$: $detA_{2n} = \begin{vmatrix}a & b\\ b & a\end{vmatrix} = a^{2}-b^{2} = a^{2}-b^{2} \cdot detA_{2n-2} = a^{2}-b^{2} \cdot detA_{0} = a^{2}-b^{2} \cdot 1 = a^{2}-b^{2} $

Hypothesis:

$ detA_{2n} = (a^{2} - b^{2}) \cdot detA_{2n-2} \Rightarrow detA_{2(n+1)} = (a^{2} - b^{2}) \cdot detA_{2(n+1)-2} $

$detA_{2(n+1)} = (a^{2} - b^{2}) \cdot detA_{2(n+1)-2} \Leftrightarrow detA_{2n+2} = (a^{2} - b^{2}) \cdot detA_{2n+2-2} \Leftrightarrow detA_{2n+2} = (a^{2} - b^{2}) \cdot detA_{2n} \Leftrightarrow detA_{2n} = (a^{2} - b^{2}) \cdot detA_{2n-2}$

This feels circular, is this the right way to do it?

Answer 1

You are correct that the argument you gave is circular (not valid).

The issue is that you are not attending to the way the variable $n$ is quantified; in other words, which values of $n$ you are talking about and when. The deduction $\operatorname{det}A_{2n}=(a^2-b^2)\cdot \operatorname{det}A_{2n-2}\Rightarrow \operatorname{det} A_{2(n+1)} = (a^2-b^2)\cdot \operatorname{det} A_{2(n+1)-2}$ is only a valid deduction if the first formula has already been established for all $n$. Because then you can substitute any value for $n$ and the conclusion will hold (in particular, you could substitute $n+1$, as you did, and deduce the second formula). So the logic you propose is indeed circular because you are using as the induction hypothesis the statement that "$\operatorname{det}A_{2n}=(a^2-b^2)\cdot \operatorname{det}A_{2n-2}$ holds for all values of $n$," which is the desired conclusion, not something that you can validly suppose and deduce things from.

The way an induction proof works is that the induction hypothesis only supposes that the formula holds up to a certain value of $n$, and you treat higher values of $n$ as an open question. So you cannot just hop from $\operatorname{det}A_{2n}=(a^2-b^2)\cdot \operatorname{det}A_{2n-2}$ to $\operatorname{det} A_{2(n+1)} = (a^2-b^2)\cdot \operatorname{det} A_{2(n+1)-2}$. The whole work of the argument is to see if you can suppose the first formula only holds for a certain value of $n$ and validly deduce that the second formula holds for that value of $n$, or, equivalently, that the first formula also holds for the next value of $n$. This is how an induction proof does its work. You need to establish two things: (1) the proposition is true for a certain, specific ("base case") value of $n$; (2) IF the proposition is true for any particular value of $n$, then it is also true for the following value of $n$ ("the induction step"). If you establish these two things, then the fact that it is true in the base case means, because of the induction step, that it is also true in the case after the base case, and then, again because of the induction step, it is also true in the case after that, and so on.

I stress this to call your attention to the importance throughout the process of paying attention to which values of $n$ you are talking about. Your thinking will become much clearer if you avoid ever writing down a formula like $\operatorname{det} A_{2n} = (a^2-b^2)\cdot \operatorname{det} A_{2n-2}$ without specifying something about which values of $n$ you are talking about. You could write something like:

"By the induction hypothesis, we can suppose that $\operatorname{det} A_{2n} = (a^2-b^2)\cdot \operatorname{det} A_{2n-2}$ for a certain number $n$. The goal is to prove that the analogous formula holds for $n+1$."

The point is that you're only assuming the formula holds for one value of $n$, not for all, so you can't just immediately substitute $n+1$ for $n$. The following is more care than most people take, but I offer it in case it helps clarify your understanding of the induction process. You could also write,

"By the induction hypothesis, we can suppose that $\operatorname{det} A_{2n} = (a^2-b^2)\cdot \operatorname{det} A_{2n-2}$ holds when $n$ equals a specific number $N$, and our goal is to prove that it also holds when $n=N+1$."

Answer 2

$$A_{2(n+1)} = \begin{bmatrix} a & 0 & \cdots & 0 & b\\ 0 & a & \cdots & b & 0\\ & & \cdots & & \\ 0 & b & \cdots & a & 0\\ b & 0 & \cdots & 0 & a \end{bmatrix}.$$

We will proceed using the appropriate cofactor matrices. First, expand along the first row, note that we have to negate the $(1,2n+2)$-th entry b since $2n+3$ is odd:

$$\det(A_{2(n+1)})=a \det\begin{bmatrix} a & \cdots & b & 0\\ & & \cdots & & \\ b & \cdots & a & 0\\ 0 & \cdots & 0 & a \end{bmatrix}-b\det\begin{bmatrix} 0 & a & \cdots & b \\ & & \cdots & & \\ 0 & b & \cdots & a \\ b & 0 & \cdots & 0 \end{bmatrix}.$$

Here the cofactor matrices are of size (2n+1) by (2n+1). Now we expand the first resulting cofactor matrix along the last row and the second cofactor matrix along the first column. By the same logic as before, we don't have to negate anything in this case:

$$\det(A_{2(n+1)})=a^2\det(A_{2n})-b^2\det(A_{2n})=(a^2-b^2)\det(A_{2n}).$$

Hence we have finished the second part of the induction. Combine it with the base case check to complete the proof.