Is this a proof by contradiction or by induction?

Question

My course problem booklet (Mathematics BSc, 2nd year module in analysis, unpublished) has,

Let $x_1=2.5$ and $x_{n+1}=\frac{1}{5}(x_n^2+6)$ for $n>1$. Show that each $2\leq x_n\leq 3$. (Hint: Try a proof by contradiction.)

The solution booklet has,

Suppose that $x_n \geq 2$ for all $1\leq n \leq m$ but $x_{m+1}<2$. Then $$x_{m+1} = \frac{1}{5}(x_m^2+6) \geq \frac{1}{5}(4+6) = 2$$ and we have a contradiction. So $x_n \geq 2$ for all $n$.

and similarly for $x_n \leq 3$.

But why can we "Suppose that $x_n\geq2$ for all $1\leq n \leq m$", and why would we think of doing that? Shouldn't a proof by contradiction begin "Suppose there exists $N\in\mathbb{N}$ such that $x_N<2$"?

It seems to me that this is actually a proof by induction in disguise, with $x_1=2.5$ implicitly taken as the base case. Am I right?

Edit: In the statement of the problem I originally wrote $2\leq x_n\leq x_3$ instead of $2\leq x_n\leq 3$. Sorry for any confusion!

Answer 1

The proof you have written certainly uses induction ("suppose that $x_n \geq 2$ for $1 \leq n \leq m$..."). It also uses contradiction ("suppose $x_{m+1}<2$", then derive a contradiction).

However, the contradiction part isn't necessary, since $x_m \geq 2$ directly implies $x_{m+1} \geq 2$. Similarly, if $2 \leq x_m \leq 3$, then $x_{m+1} = \frac{1}{5}(x_m^2 + 6) \leq \frac{1}{5}(9 + 6) = 3$. It's generally better style to avoid a proof by contradiction where it is not necessary; in this case, the assumption that $x_{m+1} < 2$ isn't really used at all.

Answer 2

You're right, that solution is odd! They are supposed to be using strong induction and "contradiction" (actually, isn't), but it can be done with the usual induction:

Is clear that $2 \leq x_1 \leq 3$. Now let $n \geq 1$, and assume that $2 \leq x_n \leq 3$. Then $4 \leq x_n^2 \leq 9$ implies $2 = \tfrac15(4+6) \leq \tfrac15(x_n^2+6) \leq \tfrac15(9+6) = 3$, that is, $2 \leq x_{n+1} \leq 3$.

The true proof by contradiction here is as follows:

You assume that there exists $m \geq 1$ such that $2 \leq x_n \leq 3$ for all $1 \leq n \leq m$, but $x_{m+1}<2$ or $x_n > 3$ (the negation of "for every $m \geq 1$ such that $2 \leq x_n \leq 3$ for all $1 \leq n \leq m$, we then have $2 \leq x_{m+1} \leq 3$"). Then, using this (not only mentioning it), you arrive to an absurdity.