Tell me more ×
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.
up vote 0 down vote favorite

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.

share|improve this question
1  
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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.