Recursive induction inequality

Question

Let $f:\mathbb{N}\to\mathbb{N}$ such that $f(1)=f(2)=f(3)=1$ and $f(n)\leq 5+9\cdot f(\lfloor \frac{n}{3} \rfloor)$ for $n\geq3$.

Show that $f(n)\leq 2\cdot n^2\;\forall n\in\mathbb{N}$.

---

I first tried a proof via induction but got stuck at the induction step. Using the induction hypothesis didn't seem useful so I tried to write the expression in the following way: For $n+1$ we get that $f(n)\leq 5+9\cdot(5+9\cdot(...(5+9)))$ but I don't know how to continue from there.

Thank you very much in advance.

Answer 1

Hint:

Use the stronger bound: $f(n)\le2n^2-\frac58$. Observe that $5-9\times\frac58=-\frac58$, and that this bound works for $n\le3$.

Answer 2

Since $f(1)=f(2)=1$, $f(n)\le14$ for all $n$ from $3$ to $9$ inclusive. We'll prove by induction on $k\ge1$ that any $n$ from $3^{k-1}$ to $3^k-1$ inclusive satisfies $f(n)\le 2\cdot 3^{2k-2}-1$. Certainly we've verified this for $k=1$ and $k=2$, and increasing $k$ by $1$ changes the value of $f$ to at most $18\cdot 3^{3k-2}-4=2\cdot 3^{2(k+1)-2}-4$.