0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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$. $\endgroup$
    – lulu
    Jan 25, 2020 at 13:23
  • $\begingroup$ @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? $\endgroup$
    – user731634
    Jan 25, 2020 at 13:43
  • $\begingroup$ $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$. $\endgroup$
    – lulu
    Jan 25, 2020 at 13:46
  • $\begingroup$ @lulu That bound is insufficient, as you end up with $f(3k)\le\color{red}5+2(3k)^2$. $\endgroup$
    – Simply Beautiful Art
    Jan 25, 2020 at 13:48
  • $\begingroup$ @SimplyBeautifulArt Ah, yes. You are right. We do need a stronger bound. $\endgroup$
    – lulu
    Jan 25, 2020 at 13:51

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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... $\endgroup$
    – zwim
    Jan 25, 2020 at 13:54
  • $\begingroup$ 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. $\endgroup$
    – Simply Beautiful Art
    Jan 25, 2020 at 13:59
  • $\begingroup$ 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. $\endgroup$
    – Simply Beautiful Art
    Jan 25, 2020 at 14:02
  • $\begingroup$ @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? $\endgroup$
    – user731634
    Jan 25, 2020 at 15:39
  • $\begingroup$ @user You should be using $f(3n)=f(3n+1)=f(3n+2)\le5+9f(n)\le\dots$, not $f(n+3)$. $\endgroup$
    – Simply Beautiful Art
    Jan 25, 2020 at 15:54
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.