Solve $T(n)=T(\frac{n}{a})+T(\frac{n}{b})+n^{k}$

Question

is there known way to solve iterative equasion to direct one:

$T(n)=T(\frac{n}{a})+T(\frac{n}{b})+n^{k}$

if the starting condition like $T(n)=c$ is known

or maybe you can invent one? thanks for answers

Answer 1

I suppose initial condition is $T(n_1)=c$. $$T(n)=T_0(n)+T_1(n)$$ $$T_0(n)=T_0\left(\frac{n}{a}\right)+T_0\left(\frac{n}{b}\right)+n^k, T_1(n)=T_1\left(\frac{n}{a}\right)+T_1\left(\frac{n}{b}\right)$$ $$T_0(n)=An^k \Rightarrow A=\frac{A}{a^k}+\frac{A}{b^k}+1\Rightarrow A=\frac{a^kb^k}{a^kb^k-a^k-b^k}\Rightarrow T_0(n)=\frac{a^kb^kn^k}{a^kb^k-a^k-b^k}$$ $$T(n_1)=c\Rightarrow T_1(n_1)=c-T_0(n_1)=c-\frac{a^kb^kn_!^k}{a^kb^k-a^k-b^k}=c_1$$ I believe solution for $T_1(n)$ may be not unique. Lets try solution in form $$T_1(n)=Bn^m \Rightarrow 1=\frac1{a^m}+\frac1{b^m}\Rightarrow m=m_1(a,b)$$ Here $m_1(a,b)$ is special function giving solution of $1=\frac1{a^m}+\frac1{b^m}$. $$T_1(n_1)=Bn_1^{m_1(a,b)}=c_1\Rightarrow B=\frac{c_1}{n_1^{m_1(a,b)}}$$ $$T=\frac{a^kb^k}{a^kb^k-a^k-b^k}\left(n^k-n_1^k\left(\frac{n}{n_1}\right)^{m_1(a,b)}\right)+c\left(\frac{n}{n_1}\right)^{m_1(a,b)}$$