# Using mathematical induction to prove a statement

The problem is:

Define a sequence by $$a_{1} = 1, a_{2} = 1, a_{n+2} = \sqrt{a_{n+1} + a_{n}}, \forall n \geq 1.$$

(a) Prove that $$a_{n} < 2$$, for all positive integer $$n$$.

(b) Prove that for all positive integer $$n$$ such that $$n \geq 2$$, we have $$a_{n+1} > a_{n}$$.

I have trouble with part (b). What I did is as follows:

For $$n = 2$$, $$$$a_{n+1} = a_{3} = \sqrt{a_{2} + a_{1}} = \sqrt{1+1} = \sqrt{2} > a_{2} = 1; \tag{1}$$$$ For $$n = k$$, assume $$a_{k+1} > a_{k}$$;

For $$n = k+1$$, $$$$a_{n+1} = a_{k+2} = \sqrt{a_{k+1} + a_{k}} > \sqrt{a_{k} + a_{k}} = \sqrt{2a_{k}} . \tag{2}$$$$

I need to prove $$a_{k+2} > a_{k+1}$$, but (2) does not lead to it. How should I solve this problem?

The inductive hypothesis says $$\;a_{k+1}\ge a_k\ge a_{k-1}\;$$ , so
$$a_{k+2}:=\sqrt{a_{k+1}+a_{k}}\ge\sqrt{a_k+a_{k-1}}=:a_{k+1}\implies Q.E.D.$$
Note that\begin{align}a_{n+2}>a_{n+1}&\iff\sqrt{a_{n+1}+a_n}+\sqrt{a_n+a_{n-1}}\\&\iff a_{n+1}+a_n>a_n+a_{n-1}\\&\iff a_{n+1}>a_{n-1},\end{align}which is true, since $$a_{n+1}>a_n>a_{n-1}$$.