I copied a proof from lecture and don't understand the end of it. It is intro number theory on continued fractions. Hopefully someone can explain it to me
Background: The sequences {$h_n$} and {$k_n$} are defined recursively as such.
$h_{-2} = 0 \quad h_{-1} = 1 \quad h_i = a_ih_{-1} + h_{-2}$
$k_{-2} = 1 \quad k_{-1} = 0 \quad k_i = a_ik_{-1} + k_{-2}$
Prop:
$$ det\begin{vmatrix} h_i & h_{i-1} \\ k_i & k_{i-1} \\ \end{vmatrix} = (-1)^{i-1} $$
Proof:
Works for $i=0$ (I'm omitting this part, I understand we need the base case).
(Then the next part is where I get confused)
Suppose true for $i < n$
Then
$$ det\begin{vmatrix} h_n & h_{n-1} \\ k_n & k_{n-1} \\ \end{vmatrix} = h_nk_{n-1}-k_nh_{n-1} = (a_nh_{n-1}+h_{n-2})k_{n-1} - (a_nk_{n-1}+k_{n-2})h_{n-1} = h_{n-2}k_{n-1}- k_{n-2}h_{n-1} $$
(Following all the algebra and substitution up to this point.)
Then:
$$ = -(h_{n-1}k_{n-2}-k_{n-1}h_{n-2}) = -(-1)^{n-2} = (-1)^{n-1}$$ By induction hypothesis we are done.
Some questions:
- How are we done? I don't understand, don't we need to do an $n+1$ case? If someone could also shed light on induction proofs where the induction hypothesis is of the type $i<n$ that'd really help me out. Maybe I'm just missing something or confusing myself.
To prove something by induction, we have to prove it for the base case, say $i=0,$
and then prove that, if it holds for any $m ≥ 0$, it holds for $m+1.$
Equivalently (replacing $m+1$ with $n$), if it holds for any $n-1\ge0$, it holds for $n$.
So we assume the statement is true for any $n-1$, i.e., $h_{n-1}k_{n-2}-k_{n-1}h_{n-2}= (-1)^{n-2}$
and then show that the statement holds for $n$, i.e., $h_nk_{n-1}-k_nh_{n-1}=(-1)^{n-1}$.
I hope this clarifies things for you.