I am trying to solve this recurrence by back substitution and then proving it by using strong induction but induction doesn't seem to go well, maybe my error lies in my back substitution. Can someone help check my work, I might have missed something. Assume: $n=2^{k}$
Given:
$$ T(n) = 1\ if \ n = 1$$ $$ 2T(\frac{n}{2}) + 6n -1 \ if \ n \ge 2$$ Then: $$ T(\frac{n}{2}) = 2T(\frac{\frac{n}{2}}{2}) + 6(\frac{n}{2}) - 1$$ $$=2 T(\frac{n}{4}) + 6(\frac{n}{2}) - 1 $$ $$= 2 (2 T(\frac{n}{4}) + 6(\frac{n}{2}) - 1) + 6n - 1$$ $$ = 2^{2} T (\frac{n}{4}) + 6n -2 + 6n - 1$$ $$T(\frac{n}{4}) = 2T(\frac{\frac{n}{4}}{2}) + 6(\frac{n}{4}) - 1$$ $$ =2 T(\frac{n}{8}) + 6(\frac{n}{4}) - 1 $$ $$ = 2^{2} (2 T(\frac{n}{8}) + 6(\frac{n}{4}) - 1) + 6n - 2 + 6n - 1$$ $$ = 2^{3} T(\frac{n}{8}) + 6n - 4 + 6n - 2 + 6n - 1$$ $$ T(\frac{n}{8}) = 2T(\frac{n}{16})+6(\frac{n}{8})-1$$ $$ 2^{3} (2T{(\frac{n}{16})+6(\frac{n}{8})-1})+6n-4+6n-2+6n-1$$ $$ 2^{4} T(\frac{n}{16}) +6n -8 +6n -4 +6n -2 +6n - 1 $$ $$ 2^{4} T (\frac{n}{16}) + 24n - 15 $$ $$ 2^{k} T (\frac{n}{2^{k}}) + 2^{k}n - (2^{k}-1) $$ I get an answer that doesn't pass the base case, now question here is that am I allowed to add the same terms and simplify them to 24n - 15? Or am I not allowed and should do the summation instead, because honestly don't want to deal with summation that much haha. Cause I can do the proof by induction if my reccurence was correct, but the answer i get above don't seem to pass the base case. Which means my back substitution was inncorect.
The last expression should have been $2^kT(\frac{n}{2^k})+6nk-(2^k-1)$ and when $n=1$ we should have $k=0$. So this evaluates to $2^0T(\frac{1}{2^0})+6.1.0-(2^0-1)=T(1)$ which is the defined base case when $n=1$.