# Proving $T(n) \ge 2^{n/2}$, for all n, by induction

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)
1
(+ (calc-f-1 (- n 1))
(calc-f-1 (- n 2))
1)))


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

-
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

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