2
$\begingroup$

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?

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.