# Recursive induction inequality

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.

• Hint: write $n=3k+r$ for $r\in \{0,1,2\}$. Then $\lfloor \frac n3\rfloor=k$ and, inductively, we can assume that $f(k)≤2k^2$.
– lulu
Jan 25 '20 at 13:23
• @lulu Thanks but now I get that $f(k+1)\leq 5+9\cdot f(k)\leq 5+9\cdot 2k^2\geq 2(k+1)^2$ which seems strange to me. Do you if I've made a mistake?
– user731634
Jan 25 '20 at 13:43
• $k+1$ doesn't enter into it. Writing $n=3k+r$ we see that we want to show $f(3k+r)≤2(3k+r)^2$ using the assumption that $f(k)≤2k^2$.
– lulu
Jan 25 '20 at 13:46
• @lulu That bound is insufficient, as you end up with $f(3k)\le\color{red}5+2(3k)^2$. Jan 25 '20 at 13:48
• @SimplyBeautifulArt Ah, yes. You are right. We do need a stronger bound.
– lulu
Jan 25 '20 at 13:51

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$$.

• Alternately I think we can show $f(n)\le g(n)=\frac{13n^2-5}8$ where $g$ is solution of the equation with $=$ instead of $\le$, by induction given $f(i)\le g(i)$ for $i=1,2,3$. I have not worked out the details though...
– zwim
Jan 25 '20 at 13:54
• I don't think it's exactly that due to the rounding down, but you can certainly try working it out at powers of 3 and bounding it based on that. Jan 25 '20 at 13:59
• A much simpler way to improve the bound further would be to simply lower the coefficient of $n^2$ so that the inequality becomes tight at $n=1$, which gives your bound. Jan 25 '20 at 14:02
• @SimplyBeautifulArt Thanks, the $-\frac{5}{8}$ is a clever way of dealing with this. But now I have that $f(n+3)\leq 5+9 f(\frac{n+3}{3}) = 5+9f(\frac{n}{3}+1)$and if I expand this, I still don't get the desired inequality. Did I do something wrong?
– user731634
Jan 25 '20 at 15:39
• @user You should be using $f(3n)=f(3n+1)=f(3n+2)\le5+9f(n)\le\dots$, not $f(n+3)$. Jan 25 '20 at 15:54

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$$.