I need a little help with expressing this recurrence relation as a closed form. I've already expanded it out to see the pattern: $$ f(n) = f\left(\frac{n}{3}\right) + f\left(\frac{2n}{3}\right) + n - 1\\ f(n) = f\left(\frac{n}{9}\right) + 2 f\left(\frac{2n}{9}\right) + f\left(\frac{4n}{9}\right) + 2n - 3\\ f(n) = f\left(\frac{n}{27}\right) + 3 f\left(\frac{2n}{27}\right) + 3 f\left(\frac{4n}{27}\right) + f\left(\frac{8n}{27}\right) + 3n - 7\\ f(n) = f\left(\frac{n}{81}\right) + 4 f\left(\frac{2n}{81}\right) + 6 f\left(\frac{4n}{81}\right) + 4 f\left(\frac{8n}{81}\right) + f\left(\frac{16n}{81}\right) + 4n - 15\\ $$
Obviously the recursive functions have binomial coefficients, the fraction numerators are the powers of 2, the denominators are $3^k$, and the trailing matter is $kn - (2^k - 1)$... but I'm not sure how I can express all that as a closed form solution, in particular the binomial coefficients.
$f(n)=f\left(\dfrac{n}{3}\right)+f\left(\dfrac{2n}{3}\right)+n-1$
$f(n)-f\left(\dfrac{n}{3}\right)-f\left(\dfrac{2n}{3}\right)=n-1$
For the particular solution part, getting the close-form solution is not a great problem.
Let $f_p(n)=An\ln n+B$ ,
Then $An\ln n+B-\left(\dfrac{An}{3}\ln\dfrac{n}{3}+B\right)-\left(\dfrac{2An}{3}\ln\dfrac{2n}{3}+B\right)\equiv n-1$
$An\ln n-\dfrac{An}{3}(\ln n-\ln3)-\dfrac{2An}{3}(\ln n+\ln2-\ln3)-B\equiv n-1$
$\dfrac{(3\ln3-2\ln2)An}{3}-B\equiv n-1$
$\therefore\begin{cases}\dfrac{(3\ln3-2\ln2)A}{3}=1\\-B=-1\end{cases}$
$\begin{cases}A=\dfrac{3}{3\ln3-2\ln2}\\B=1\end{cases}$
$\therefore f_p(n)=\dfrac{3n\ln n}{3\ln3-2\ln2}+1$
But getting the complementary solution part is not optimistic.
Since we should handle the equation $f_c(n)-f_c\left(\dfrac{n}{3}\right)-f_c\left(\dfrac{2n}{3}\right)=0$ .
$n\to3n$ :
$f_c(3n)-f_c(n)-f_c(2n)=0$
Let $\begin{cases}m=\ln n\\g_c(m)=f_c(n)\end{cases}$ ,
Then $g_c(m+\ln3)-g_c(m)-g_c(m+\ln2)=0$
Which is no hope on how to solve further.