How can I solve this recurrence problem?

Question

Given a function $$ f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0 $$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.

Answer 1

The Akra-Bazzi theorem gives us a way of tackling the complexity of $T$ given a recurrence of the form $$T(n)=g(n) + \sum_{i=1}^k a_i T(b_i n + h_i(n))$$

Here, we have $f(n)=f(5n/13)+f(12n/13)+n$. So our first focus is on solving $p$ such that $a_1 b_1^p+a_2b_2^p=1$ where $a_1=a_2=1$ and $b_1=5/13,b_2=12/13$; equivalenty, we have $$5^p+12^p=13^p$$

Recall that $(5,12,13)$ is a Pythagorean triple so clearly $p=2$.The theorem then tells us $$f(n)\in\Theta\left(n^2\left(1+\int_1^n \frac1{u^2} du\right)\right)$$

Since $\int_1^n\frac1{u^2}du=1-\frac1n$ this gives us $f(n)\in\Theta(n^2)$.