# 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?

• is $n\in\mathbb{Z^+}$? – Artem Mar 12 '15 at 17:19
• Oh yeah $n \in \mathbb{Z}$ and is a power of 3. – dogman288 Mar 12 '15 at 18:19
• Let $b(n) = a(3^n)$, and close $b$. – DanielV Mar 13 '15 at 18:34

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

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

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.