Recurrence relations with factors in recurrence

Question

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?

Answer 1

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}$$

Answer 2

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 $$

Answer 3

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.