Solving $a_n=5a(n/3)-6a(n/9)+2log_3n$ using domain transformation

Question

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

Answer 1

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.

Answer 2

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?

Answer 3

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.