Recurrence relations with factors in recurrence How would I go about approaching solving a recurrence relation such as:
$$a_{n}=2a_{\frac{n}{3}}+1$$
I'm just not sure how to get a general form for a non-recursive solution, can someone walk through the first couple steps?
 A: Method 1: Exploit the relationship between recurrences and summations
$$ a(3^0)=\phi $$
$$ a(3^k)=2a\left(3^{k-1}\right)+1 $$
$$\mbox{for}\ k\geq 1 $$
Let's multiply both sides by the summation factor of $\frac{1}{2^k}$
$$ \frac{a(3^0)}{2^0}=\frac{\phi}{2^0}=\phi $$
$$ \frac{a(3^k)}{2^k}=\frac{2a\left(3^{k-1}\right)}{2^k}+\frac{1}{2^k} = \frac{a\left(3^{k-1}\right)}{2^{k-1}}+\frac{1}{2^k} $$
Let $s(k)=\frac{a(3^k)}{2^k}$, then
$$ s(0) = \phi $$
$$ s(k) = s(k-1) + \frac{1}{2^k} $$
Therefore
$$ s(k)= \phi+\sum_{j=1}^{k}\frac{1}{2^j} = \phi + 1 - \frac{1}{2^k}$$
And
$$ a(3^k) = 2^ks(k)=2^k\left(\phi + 1 - \frac{1}{2^k}\right) = 2^k\left(\phi+1\right)-1$$
Method 2: Generalize the recurrence and use the repertoire method
$$ a(3^0)=\phi $$
$$ a(3^k)=2a\left(3^{k-1}\right)+1 $$
$$\mbox{for}\ k\geq 1 $$
This is just a special case of the generalized recurrence 
$$ a(1)=a(3^0)=\phi $$
$$ a(n)=a(3^k)=2a\left(3^{k-1}\right)+\beta$$ $$\mbox{for}\ k\geq 1 $$
Also note that we can redefine $a(n)$ as a linear combination of unknown functions and their corresponding coefficients
$$ a(n)=A(n)\phi+B(n)\beta $$
Let's begin by studying the output of $a(n)$
$$ a(3^0)=\phi $$
$$ a(3^1)=2\phi+\beta $$
$$ a(3^2)=4\phi+3\beta $$
$$ a(3^3)=8\phi+7\beta $$
$$ a(3^4)=16\phi +15\beta$$
$$ a(3^5)=32\phi+31\beta $$
The obvious guess for $A(n)$ is $2^k$. So now let's find $A(n)$ via the repertoire method
$$\mbox{Let}\ a(n)=a(3^k)=2^k, \mbox{then} $$
$$ a(1)=a(3^0)=2^0=1=\phi  $$
$$ a(n)=a(3^k)= 2a\left(3^{k-1}\right) +\beta$$
$$2^k=2\cdot 2^{k-1}+\beta$$
$$2^k=2^k+\beta$$
Which implies that
$$\phi=1, \beta=0$$
Now let's apply these facts to the general equation
$$ a(n)=A(n)\phi+B(n)\beta $$
$$ 2^k=A(n)\cdot 1+B(n)\cdot 0 $$
$$ 2^k=A(n)+0 $$
$$A(n)=2^k$$
Now let's find $B(n)$ also via the repertoire method
$$\mbox{Let}\ a(n)=a(3^k)=2^k-1, \mbox{then} $$
$$ a(1)=a(3^0)=2^0-1=0=\phi  $$
$$ a(n)=a(3^k)= 2a\left(3^{k-1}\right) +\beta$$
$$2^k-1=2\left(2^{k-1}-1\right)+\beta$$
$$2^k-1=2^k-2+\beta$$
$$2-1=\beta$$
Which implies that
$$\phi=0, \beta=1$$
Now let's apply these facts to the general equation
$$ a(n)=A(n)\phi+B(n)\beta $$
$$ 2^k-1=A(n)\cdot 0+B(n)\cdot 1 $$
$$ 2^k-1=0+B(n) $$
$$B(n)=2^k-1$$
So now we have
$$ a(n)=A(n)\phi+B(n)\beta $$
$$ a(n)=2^k\phi+\left(2^k-1\right)\beta $$
$$ a(n)=2^k\phi+2^k\beta-\beta $$
Therefore, the closed form solution to the general recurrence is
$$ a(n)=a(3^k)=2^k\left(\phi+\beta\right)-\beta $$
Note that for your specific recurrence, $\beta=1$. So the closed form solution to your specific recurrence is
$$ a(n)=a(3^k)=2^k\left(\phi+1\right)-1 $$
A: If I've understood this correctly, $n=3^k,k\in\mathbb{Z^+}$. A good method that I found in Concrete Mathematics - A Foundation for Computer Science is called the repertoire method (please correct me, but this is the way I understood it.) So, the idea is simply to try to break the recurrence into smaller ones, and hopefully, the smaller ones will have a recognizable pattern.
In your case, let's assume that $a_1=\alpha$. So, the idea is simply to evaluate this several times, as shown below:
$$\begin{array}{l}
{a_1} = \alpha \\
{a_3} = 2{a_1} + 1 = 2\alpha  + 1\\
{a_9} = 2(2\alpha  + 1) + 1 = 4\alpha  + 3\\
{a_{27}} = 2(4\alpha  + 3) + 1 = 8\alpha  + 7\\
{a_{81}} = 2(8\alpha  + 7) + 1 = 16\alpha  + 15
\end{array}$$
As you can see, there is a pattern. The initial parameter $\alpha$ has the coefficient that is equal to the power of $3$ squared, i.e. for $a_{81}$, it's $81=3^4$, so $4^2=16$. The constant term is simply one less than the coefficient.
Edit
Here's how it would be expressed:
$$\begin{array}{l}
{a_1} = \alpha \\
{a_{{3^k}}} = {k^2}\alpha  + ({k^2} - 1)
\end{array}$$
A: Just use the change of variables $n = 3^k$ and $b_k = a_{3^k}$ to get:
$$
b_k = 2 b_{k - 1} + 1
$$
Solve this one, and express in terms of the original variables.
