Solve the recurrence $a_n=3a_{n/3}+2$ given $a_0=1$ and $n$ is a power of $3$ Solve the recurrence $$a_n=3a_{n/3}+2$$ given $a_0=1$ and $n$ is a power of $3$
I am trying to study for my final using my previous quizzes, of which I got this question wrong. My instructor wants me to use the Divide and Conquer technique. I imagine I would at least start with the base cases where $n$ is a power of $3$:$$3^0\rightarrow a_0=1$$$$3^1\rightarrow a_1=3(0)+2=2$$$$3^2\rightarrow a_3=3(2)+2=8$$$$3^3\rightarrow a_9=3(8)+2=26$$The next step I have is solve for $a_n$. Stop when $\frac{n}{3^k}=1$. That implies $n=3^k$ and we substitute $k=log_3n$ times:$$a_n=3a_{n/3}+2$$$$=3(3a_{n/3^2}+2)+2=3^2a_{n/3^2}+6+2$$$$=3^2(3a_{n/3^3}+2)+6+2=3^3a_{n/3^3}+18+6+2$$$$=\cdots $$$$=3^ka_{n/3^k}+2(3^{k-1}+3^{k-2}+\cdots +3+1)$$Here is where I get lost, however. In the answer key, my instructor has this last term equating to:$$=3^ka_{n/3^k}+2\frac{3^k-1}{3-1}$$But I have NO idea how these two expressions equal each other. Can someone point this out to me? I have the steps after that complete solving the recurrence, this step just loses me, and I need to know what's going on with it for my final.

Consider:
$$\begin{aligned}
(3-1)(3^{k-1}+3^{k-2}+\cdots +3+1) & =(3^{k}+3^{k-1}+\cdots +3)-(3^{k-1}+3^{k-2}+\cdots +3+1) \\
&=3^k+(3^{k-1}-3^{k-1})+ ...+(3-3)+1\\
&=3^k-1
\end{aligned}$$
rearranging:
$$
3^{k-1}+3^{k-2}+\cdots +3+1=\frac{3^k-1}{3-1}
$$
Which is just the sum of a geometric series formula
