Fibonacci numbers for $3 \leq n$ , proof by induction Let $P_{1}, P_{2}, P_{3}$ represent the _Fibonacci_ numbers. Show by induction that claim ($n$): $P_{n} \geq (\sqrt{2})^{n-1}$ for $n \geq 3$ Step $1$) is comprehensible. I cant get past: $P_{n+1} ≥ (\sqrt{2})^{n-1+1}$ $P_{n} + P_{n -1} ≥ (\sqrt{2})^n$ Where do I go from here?

**HINT**

As you suggested, you have $$ P_{n+1} = P_n + P_{n-1} \ge \left(\sqrt{2}\right)^{n-1} + \left(\sqrt{2}\right)^{n-2} \ge 2 \cdot \left(\sqrt{2}\right)^{n-2} $$

Can you finish this?

**UPDATE**

Note that this relies on Strong Induction (which is equivalent to regular induction but easier to prove sometimes, like here). Namely, the inductive step is that if $P_1, P_2, \ldots, P_n$ all hold, then $P_{n+1}$ holds as well...

**UPDATE 2**

Note that $2 = \left(\sqrt{2}\right)^2$, so what is $2 \cdot \left(\sqrt{2}\right)^{n-2}$?