Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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

$$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.

share|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

 
discard

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.