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.

Trying to solve the following induction question, but I seem to be getting cold cause I am lost! Can someone help me, then point me in a direction I can relearn this stuff :)

Wanted to prove: $T(n) \ge 2^{n/2}$, for all $n$

f(n) =  1 if n < 2
f(n−1) + f(n−2) + 1    otherwise

This problem explores a number of ways of computing $f$, each with a different running time.

a. In the naive algorithm given below, let T(n) = Time[(calc-f-1 n)].

(define (calc-f-1 n)
  (if (< n 2)
    (+ (calc-f-1 (- n 1))
    (calc-f-1 (- n 2))

-- this is what i got thus far --

$T(n) \ge 2^{n/2}$

$T(1) = 2^{1/2} = 1$

$T(k+1) = 2^{(k+1)/2}$

$T(k+1) = 2k$

share|improve this question
What is $T(n)$? –  Daniel Montealegre Mar 19 '12 at 5:44
that's all I saw bro sorry :( –  ferron Mar 19 '12 at 5:48
You need some definition of what $T(n)$ is, otherwise you cannot solve the problem. –  Daniel Montealegre Mar 19 '12 at 5:49
This is very unclear. What does $f$ have to do with $T$? Does 2^n/2 mean $(2^n)/2$ or $2^{n/2}$? How do you manage to get both $T(k+1)=2^{(k+1)/2}$ and $T(k+1)=2k$? Think about your question a little more and edit it into something sensible, please. –  Gerry Myerson Mar 19 '12 at 5:50
added something more. hope this helps –  ferron Mar 19 '12 at 6:30

1 Answer 1

up vote 0 down vote accepted

For the first two values we have $T_0=1 \geq 2^{-1/2}$ and $T_1=1 \geq 2^{0/2}$. Then by induction

$$ T_n = T_{n-2}+T_{n-1}+1 \geq 2^{\frac{n-2}{2}}+2^{\frac{n-1}{2}}+1>2^{\frac{n}{2}}\left(2^{-1}+2^{-\frac{1}{2}}\right) > 2^{\frac{n}{2}} $$

since $\frac{1}{2}+\tfrac{\sqrt{2}}{2} > 1$.

share|improve this answer
Is it possible for u to direct me to somewhere i can learn do these wonderful stuff (humbled) –  ferron Mar 19 '12 at 8:25
Check tinyurl.com/b5j4ed and tinyurl.com/6vr6m3j and the bible tinyurl.com/8y8agqd (Introduction to Algorithms) –  Kirthi Raman Mar 20 '12 at 2:01

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.