1
$\begingroup$

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:

  1. 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.
$\endgroup$
  • $\begingroup$ We’re assuming it’s true for $n-1$ and showing it’s true for $n$; by the way, I think you meant $n$ not $i$ in the subscripts in the second determinant $\endgroup$ – J. W. Tanner Apr 22 at 15:31
  • $\begingroup$ Changes the subscripts in the second det, thank you. I just don't understand why we multiply the last part by $-1$ and how the part inside the brackets $= -(-1)^{n-2}$ $\endgroup$ – Mathstatsstudent Apr 22 at 15:33
  • $\begingroup$ $h_{n-1}k_{n-2}-k_{n-1}h_{n-2}= (-1)^{n-2}$ is basically the statement (assumed true) for $n-1$ $\endgroup$ – J. W. Tanner Apr 22 at 15:46
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.