Let $f$ be a positive function such that $$f(n) = a f\left( \left\lfloor \frac nb\right\rfloor\right) + c$$ holds for every integer n ≥ 1, where a ≥ 1, b is an integer larger than one, and c ∈ R+ .
Prove that $f(n) = O(n^{\log_b a})$ if a > 1, and $f(n) = O(\ln n)$ if a = 1
I don't understand where to begin, I tried using the formal definition of big O notation but still couldn't progress any further
You may want to have a look at some proofs of the Master Theorem as your question seems extremely similar.