Solve the recurrence $a_n=3a_{n/3}+2$ given $a_0=1$ and $n$ is a power of $3$

Question

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.

Answer 1

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

Answer 2

You probably meant $a_1=1$ instead.

Define a sequence $b_n=a_{3^n}$.

We have $b_0=1$ and $b_{n+1}=3b_n+2$.