1
$\begingroup$

$a_n=5a(n/3)-6a(n/9)+2log_3n$, For $n\ge9$ and n is a power of 3. $a_3=1$, and $a_1=0$

Transforming the first two terms is straightforward, but I'm not sure what to do with the log term. Should I rewrite it somehow? The fact that it isn't attached to the function, but just to n, is also somewhat confusing.

$\endgroup$
2
$\begingroup$

Since $n\geq 9$ is a power of 3, we will write $n=3^x$ for variable $x\geq 2$. Substitute this into your recurrence, and you get $$a(3^x)=5a(3^{x-1})-6a(3^{x-2})+2x.$$ Now we define a new recurrence in terms of the variable $x$ as follows: define the function $a^*:x\mapsto a(3^x)$. Then, by the recurrence above, $a^*(x)$ satisfies the recurrence $$a^*(x)=5a^*(x-1)-6a^*(x-2)+2x.$$ Your initial conditions $a_3=1$ and $a_1=0$ become $a^*_1=1$, $a^*_0=0$. The above recurrence is linear, so can be solved using the usual methods.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Let $b_n:=a_{3^n}$. Then $b_{n}=5b_{n-1}-6b_{n-2}+2n$. Afterall, $\log_3(3^n)=n$. Can you solve it now?

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Here is a closely related recurrence that has the same complexity as the one in the OP and admits an exact solution for all $n.$ This computation resembles the following MSE link, the difference being that this one does not depend on the digits of $n.$

Suppose we start by solving the following recurrence for $n\ge 3$: $$T(n) = 5 T(\lfloor n/3 \rfloor) - 6 T(\lfloor n/9 \rfloor) + \lfloor \log_3 n \rfloor$$ where $T(0) = 0$ and $T(1) = T(2) = 1.$

We unroll the recursion to obtain an exact formula for $n\ge 3$ $$T(n) = [z^{\lfloor \log_3 n \rfloor}] \frac{1}{1- 5 z+ 6 z^2} + \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} [z^j] \frac{1}{1- 5 z+ 6 z^2} (\lfloor \log_3 n \rfloor - j).$$

where the first term represents the base cases with $n\lt 3$ and the second the contribution from the logarithmic term.

Observe that the roots of $$1- 5 z + 6 z^2 \quad\text{are}\quad\rho_0=\frac{1}{2} \quad\text{and}\quad\rho_1=\frac{1}{3}$$

and $$\frac{1}{1- 5 z+ 6 z^2} = \frac{3}{1-3z} - \frac{2}{1-2z}.$$

It follows that the coefficients of the rational term have the form $$[z^j] \frac{1}{1-5z+6z^2} = 3^{j+1} - 2^{j+1}.$$

This gives the exact formula for $T(n):$ $$T(n) = 3^{\lfloor \log_3 n \rfloor+1} - 2^{\lfloor \log_3 n \rfloor+1} + \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} (3^{j+1}-2^{j+1}) (\lfloor \log_3 n \rfloor - j) \\ = 3\times 3^{\lfloor \log_3 n \rfloor} - 2\times 2^{\lfloor \log_3 n \rfloor} \\ + \frac{9}{4} 3^{\lfloor \log_3 n \rfloor} - \frac{3}{2} \lfloor \log_3 n \rfloor - \frac{9}{4} \\ - 4 \times 2^{\lfloor \log_3 n \rfloor} + 2\times \lfloor \log_3 n \rfloor + 4$$ which simplifies to $$\frac{21}{4} 3^{\lfloor \log_3 n \rfloor} - 6 \times 2^{\lfloor \log_3 n \rfloor} + \frac{1}{2} \lfloor \log_3 n \rfloor + \frac{7}{4}.$$

It follows that $T(n)$ has the dominant asymptotic $$T(n)\in\Theta\left(3^{\lfloor \log_3 n \rfloor}\right) = \Theta\left(3^{\log_3 n}\right) = \Theta(n).$$

Observe that $5/3-6/9= 5/3-2/3=3/3=1,$ which checks.

Here is another Master Theorem computation at MSE.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ While this is certainly interesting, I have a feeling the OP wasn't looking for an answer like this, given some of the other questions they've asked. $\endgroup$ – Kevin Church Apr 30 '15 at 1:13
  • $\begingroup$ True, it's a bit beyond me and it uses generating functions when the question is framed (almost) perfectly for domain transformation. I can follow it by hand up to finding the exact solution, then I have to use a tool to simplify the expression, but maybe I'm missing an identity. $\endgroup$ – Whitesizzle Apr 30 '15 at 1:33

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.