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)}$
You can continue from here.