How do you write a recursive function in a way that it will be easy to compare it to another while doing a proof by induction? How would you write the following recursive function in such a way that it will be 
easy to compare it to another while doing a proof by induction?
Base Case: $F(0) = 0; F(1) = 1$.
Recursive Step: $ F(n) = F(n - 1) + F(n - 2)$ for all $n \geq 2$
I get stuck when you have to show that $f(k+1) \leq g(k+1)$ where $g(n)$ is some arbitrary function, in this case how would I define $f(k+1)$ in order to compare it?
What if $g(x) = (\frac{1+\sqrt{5}}{2})^{n-1}$ as an example? 

Let $\varphi=\frac12\left(1+\sqrt5\right)$. Then you have $g(n)=\varphi^{n-1}$. Now note that $\varphi$ is one of the solutions of the quadratic equation $x^2-x-1=0$: just check the quadratic formula. Thus, $\varphi^2=\varphi+1$, and therefore
$$g(n)=\varphi^{n-1}=\varphi^{n-3}\varphi^2=\varphi^{n-3}(\varphi+1)=\varphi^{n-2}+\varphi^{n-3}=g(n-1)+g(n-2)$$
for $n\ge 2$. In other words, $g$ satisfies the same recurrence as the Fibonacci numbers, and a proof by induction is very straightforward: if $F_{n-1}\le g(n-1)$ and $F_{n-2}\le g(n-2)$, then automatically $$F_n=F_{n-1}+F_{n-2}\le g(n-1)+g(n-2)=g(n)\;.$$
This is the nicest possible setup for a proof by induction: the two sequences satisfy the same recurrence.
