how to prove recursive function f(x) is in O(n)?

Question

Let f(n) be defined recursively as follows: $$\begin{align}f(0) &= 0 \\ f(n) &= f\left(\left \lfloor \frac{n}{3} \right \rfloor\right) + 3f\left(\left \lfloor \frac{n}{5} \right \rfloor\right) +n,\quad\forall n \ge 1 \end{align}$$ Show that $f(n)\in\mathcal O(n)$.

I find some similar question that $f(n) = 2f\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + 1$, but I don't know how to deal with the $\left \lfloor \frac{n}{3} \right \rfloor$ and $n$. can anyone give me some hint?

Answer 1

Let us prove that $f(n)\le 30n$. It is true for $n=0$. Suppose it is true for every $m< n$. Then $f(n)=f(\lfloor\frac{n}{3}\rfloor) + 3f(\lfloor\frac{n}{5}\rfloor ) )+n\le 30\lfloor\frac{n}{3}\rfloor+90\lfloor\frac{n}{5}\rfloor+n\le 10n+18n+n<30n$. Q.E.D.

Answer 2

Since $n$ is positive and the initial condition is non-negative, it is easy to show that $f$ is non-decreasing. So,

$$ f(\lceil n/3\rceil) \leq f(n) $$