I'm trying to do a proof on fibonacci numbers by induction, and I have an answer but I'm not sure its acceptable.
I'm trying to prove $F_n < 2^n$
My base case at 1 is $F_1 = 1; 2^1 = 2$ therefore checks out
My inductive hypothesis: $F_k < 2^k; 1 \le k \le n$
And inductive step: $F_{k+1} < 2^{k+1}$
I know $F_k = F_{k-1} + F_{k-2}$, so I substitute that into my I.S.
$F_k + F_{k-1} < 2^{k+1}$
We know the L.H.S is less than or equal to $2F_k$, and $2^{k+1} = 2^k 2$
we can conclude that $F_k + F_{k-1} < 2^{k+1}$ from the above statement. This is because the above statement is true, and it is shown the L.H.S is less than that of our statement
You are right and the proof is correct. Here is how I would write this up to clean up the proof text.
We would like to prove that $$F_n < 2^n \quad \forall n \ge 1.$$ Proceed by Mathematical Induction on $n$.
For the base case, note that $$ F_1 = 1 < 2 = 2^1, $$ hence $F_1 < 2^1$ and the statement holds for $n = 1$.
For the inductive step, assume that the claim is true for all $1 \le k \le n$, and let us prove that $F_{n+1} < 2^{n+1}$.
Notice that $$ \begin{split} F_{n+1} &= F_n + F_{n-1} \quad \text{by the Fibonacci recurrence} \\ &< 2F_n \quad \text{since Fibonacci numbers are an increasing sequence} \\ &< 2 \cdot 2^n \quad \text{by the Inductive Hypothesis} \\ &= 2^{n+1}. \end{split} $$ Hence, $F_{n+1} < 2^{n+1}$ as desired.
Q.E.D.