# Induction on recursive formula

Okay so I have this recursive formula

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$$

$$T\left(n\right) =T\left(1\right)\ +\ c_{2}*n\cdot\sum_{k=1}^{⌊\log\left(n\right)⌋}\frac{1}{2^{k}}=T\left(1\right)+c_{2}*(n-1)$$

I've been trying for a few hours to prove the correctness of it by induction, I feel like I've tried everything. The closest I got was defining $$n=2^{x}$$ and prove the correctness for every $$x$$ but I can't seem to get the right answer.. How do you prove something like that?

The main question is how do I prove $$T(n) = T(n/2) + c_{2}n = T(1) + c_{2}*(n-1)$$

The series $$\frac{1}{2^k}$$ is a geometric progression. Hence, $$\sum_{k=0}^m \frac{1}{2^k} = \frac{1-\left(\frac{1}{2}\right)^m}{1-\left(\frac{1}{2}\right)}$$
• If you managed to show that $T(n)=T(1)+c\cdot n\cdot \sum_{k=1}^{\lfloor \log(n) \rfloor} \frac{1}{2^k}$, then substitute the formula in this answer. If you didn't manage to prove this, then try to prove it using induction. Do not skip over the step of showing $T$ as a summation! it will only make it harder for you to prove it by induction – nir shahar Apr 27 at 12:43
• If you would rather not go through this step (of showing that $T$ can be expressed as a summation), you can find some constant $c>0$ that suits you, and prove by induction that $T(n) \le T(1) + c\cdot n$ – nir shahar Apr 27 at 12:44