Hi given this recursion tree problem-

I have a solution to this problem but I don't understand it after the k = log3n How does the k=log3n turn into 3^(K+1) - 1 / 2? Is that some sort of equation? And how does that prove Theta(N)?

Thanks!

S(n) = 3S() + b. (a) Use a recursion tree to show that S(n) = (g(n)), for some function g(n). - - - SCM) - - - - - - - b .. (ny) (M) s(my) - --.--.--.-- 3b sowa) swe) semba) .... simo)..semeg)........... 96 Sulzie) .--.3k S(M/K) It will stop, when h1 = [k= logga Total cost = b + ab + 3 b +33b+...+34b =b(1+3+3 +33 + + 3) +61.63K041-1) 3-1 aparan yo = (pasu tag -2) b - zasyonun 20, (scnse Total cost = (304)51 Hearly. Som)