# 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?

-
It really depends very much on the functions involved. The Fibonacci numbers have a well-known closed form, which may be useful in such arguments, but if $g$ itself is defined recursively, the recursive definition of the Fibonacci numbers may be handier. – Brian M. Scott Mar 25 '13 at 0:26
@BrianM.Scott What if $g(x) = (\frac{1+\sqrt{5}}{2})^{n-1}$ as an example? – jack Mar 25 '13 at 0:29
It was a bit long for a comment, so I’ve written up an answer for that specific $g$. – Brian M. Scott Mar 25 '13 at 0:47

## 1 Answer

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.

-
Thanks a lot :) – jack Mar 25 '13 at 2:23
@jack: You’re welcome. – Brian M. Scott Mar 25 '13 at 19:05