# Induction on recursive formula

I have this recursive formula

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2O\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 n⌋}\frac{1}{2^{k}}=T\left(1\right)+c_{2}(n-1)$$

I've been trying for a few hours to prove its correctness by induction, I feel like I've tried everything. The closest I got was defining $$n=2^{x}$$ and proving 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 Apr 27, 2021 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$ Apr 27, 2021 at 12:44