# Proving a recurrence relation by induction

Hi I have the following recurrence relation:

$$T(n) = \begin{cases} 1, & \text{if n=2} \\ 2T\left({n \over 2}\right) + 4, & \text{if n > 2} \\ \end{cases}$$

Where $n$ can be assumed to be, $n = 2^c$ for some $c \ge 1$.

Which I solved using back substitution to find that: $$\sum_{i=2}^n{2^i} = {n\over 2} + 2(n-2)$$

I am now tasked with proving by induction. I solve the base case fine, and get my Induction hypothesis to state that for some $k$, $$T(k) = {k \over 2} + 2(k-2)$$

Now I get I have to show that for the Induction Step, $$T(k+1) = {k+1 \over 2} + 2(k-1)$$

This is where I get lost. I use the recurrence relation to show: $$T(k+1) = 2T\left({k+1 \over 2}\right) + 4$$ and I get stuck from there, any hints would be appreciated.

-
There is something screwy about your recurrence, which defines $T(n)$ in terms of $T(n)$. –  Gerry Myerson Oct 23 '12 at 5:03
I didn't understand the statements that $n=2^c$ for some $c>1$ and the sum $\sum_{i=2}^{k} ..$. –  Ganesh Oct 23 '12 at 5:04
$$\sum_{i=2}^k{2^i} = {n\over 2} + 2(n-2)$$ The sum of an exponential is linear? Something is fishy here. Is $k$ the index, or just some number? (you never defined it) –  Navin Oct 23 '12 at 5:34
It should be $T(n) = 2T(n/2) + 4$, right? :-). And k must be $log(n)$, right. I did some such problems before, so, could guess it. Please mention everything needed for people to attempt to answer it in future. Why induction, recurrence relation does not talk about odd n, so how can you ever prove for odd numbers using just the input? If you have a definition of $T$ for odd n, you can consider it. –  Salahuddin Oct 23 '12 at 7:44