Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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


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.

share|cite|improve this answer
Thanks a lot :) – jack Mar 25 '13 at 2:23
@jack: You’re welcome. – Brian M. Scott Mar 25 '13 at 19:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.