Induction over a range of values

Question

In the induction proof below where $[a_0; a_1,\ldots, a_h]$ is a continued fraction, could someone please clarify which induction method is being used here? Is it:

1. an induction over $i$ and $h$ i.e. show for each $h\in \mathbb{N}_0$ that it the result holds for all $-1\leqslant i \leqslant h$.

2. an induction only over $i$. Where $h$ is just a given value in $\mathbb{N}_0$

I initially assumed it was the first option but I struggled a lot and wasn’t able to do the ‘straightforward’ induction. If it is the second option then why for the base step is the result proven for $i=-1$ and $i=0$ and not just for one value?

Answer 1

Option 2: It's definitely option 2.

This is induction over $i$ for a fixed $h$.

Of course $h$ could be any value as there is nothing it the proof that requires any specific qualities of $h$ (other than $h\in \mathbb N_0$).

Don't be confused in that this is a proof by induction on one variable, $i$, but a proof by generality on another, $h$. Don't forget a "proof by generality"--- to prove something is true for all values of a set $G$, which can be $\mathbb N_0$ or any other set, by arbitrarily picking a value, $w\in G$, and showing it is true for $w$, therefore it is true for all elements in $G$ because ... there was nothing special about $w$--- is still valid.

so the statement is: For any $h\in \mathbb N_0$ and for an $i: 1\le i \le h$ then .... something.

And the proof goes like:

• Fix an arbitrary $h_0 \in \mathbb N_0$ (the subscript $_0$ is my idea; the author didn't think it was necessary-- it wasn't but it illustrates my point).
• Prove via induction on $i$ that the statement is true for all $-1 \le i \le h_0$.
• Then conclude that because $h_0$ was arbitrary, it must be true for all $h \in \mathbb N_0$.

Answer 2

In order to achieve the induction step here, you need to assume the induction hypothesis is true for the previous two values of $i$, since $d_i$ depends on $d_{i-1}$ and $d_{i-2}$.

I think you could view this either as strong induction -- like your option (1), where the induction hypothesis is that the statement holds for all values from $-1$ to $i$ -- or you could view it as regular induction (like your option (2)), where the proposition $P(i)$ is that it holds for $i$ and $i-1$, and that's why you would need to prove the base step for two values.