So I have a question (it's from William j.LeVeque's Elementary Theory of Numbers and you are supposed to use either induction or/and well-ordering principle to solve it):
"Re-examine the proof $u_n=\alpha^n$ for all n, to find the smalles $\beta$ such that you could prove that $u_n < \beta^n$ for all $n$, and carry out this proof. Can you prove an inequality in the opposite direction, of the form $u_n > c\beta^n$, for some positive constant $c$?"
Here is the proof mentioned for $u_n=\alpha^n$:
So, $u_n$ is the $n^{th}$ element in the fibonacci sequence and you need to prove that for every positive integer n, $u_n < (\frac{7}{4})^n$. Let P(n) be $u_n < (\frac{7}{4})^n$.
First we see that $u_1 < \alpha$ and $u_2 < \alpha^2$. Then, we assume that P(1), ..., P(m) are true, then we have for $m \ge 2$, $$u_{m+1} = u_m + u_{m-1} < \alpha^m + \alpha^{m-1} = \alpha^{m-1}(1+\alpha) < \alpha^{m-1}*\alpha^2 = \alpha^{m+1}, since $$ $$ 1 + \alpha = \frac{11}{4} < 3 < \frac{49}{16} = \alpha.$$
(This was given in the book.)
So, I solved the first part of the question:
Let P(n) be $u_n < \beta^n$. Now, I assumed P(1) and P(2) true. Then assumed true for all integer from 1 to m and tried to deduce $u_{m+1}$: $$u_{m+1} = u_m + u_{m-1} < \beta^m + \beta^{m-1} = \beta^{m-1}(\beta+1).$$ From here, we can see that to prove P(m+1) true, we need to find a $\beta$ such that $\beta + 1 \le \beta^2$ and $\beta > 1$ (from P(1) < $\beta$ ). In such conditions $u_{m+1} < \beta^{m+1}$ ( by replacing $(\beta+1)$ with $\beta^2).$ Solving the inequality we can conclude that $$\beta = \frac{1+\sqrt(5)}{2}.$$ (if we take the smallest $\beta$)
Now, how do I solve the second part? (or tell me if there is something wrong about the solution that I gave to the first part of the question.)
P.S. I am kinda new to the site. You can say if you have any sugestions to formulating or formatting the queston.