1

enter image description here

Pretend induction is just a weird way our teacher uses induction when it comes to finding constant. Same as induction

Base Case:

let $n = 1$

$f(n) = 6(1) = 6$ and $bn = b$. Therefore we need $b \geq 6$ (*)

let $n = 2$

$f(n) = 6(2) = 6$ and $bn = 2b$. Therefore we need $b \geq 6$ (*)

$\vdots$

as wanted

IND STEP: Let $n \geq 9$. Suppose $f(j) \leq bj $ whenever $0 \leq j < n$. [IH]

WTP: $f(n) \leq bn$

$f(n) = 2f(\lfloor \frac{n}{9} \rfloor) + 3f(\lceil \frac{n}{4} \rceil) + 5n$ [def of f; $n \geq 9$]

$\leq 2b(\frac{n}{9}) + 3b \frac{n+3}{4} + 5n$ [IH, and $\frac{n}{9} \geq \lfloor \frac{n}{9} \rfloor$ and $\frac{n+3}{4} \geq \lceil \frac{n}{4} \rceil $]

$\leq 2b(\frac{n}{9}) + 3b \frac{2n}{4} + 5n$ [$\frac{2n}{4} \geq \frac{n+3}{4}$ for $n \geq 9$]

$= n \left(b \frac{2}{9} + b \frac{6}{4} + 5\right)$ [n common factor]

$= n \left( \frac{31}{18}b + 5\right)$ [Basic Arithmetic]

Thus we need $= n \left( \frac{31}{18}b + 5\right) \leq bn$

$5 \leq b \frac{-13}{18}$

$-\frac{90}{13} \leq b$

I'm lost. I don't know where I went wrong.

Especially Lime
  • 40,828
Tinler
  • 1,061

1 Answers1

0

I think the problem is that you are using $\frac{n+3}{4}\leq\frac{2n}4$ which isn't strong enough (if the problem had $\lfloor 2n/4\rfloor$ instead of $\lceil n/4\rceil$ no such $b$ would exist).

Instead, keep $\frac{n+3}{4}$. That means that $$f(n)\leq\bigg(\frac{35}{36}b+5+\frac{3b}{2n}\bigg)n.$$

We $n$ to be quite large to have a hope here: since this bound needs to be at most $bn$ we must have $\frac{35}{36}+\frac{3}{2n}<1$. This is true only for $n>216$.

I think what you need to do here is bound $f(n)$ up to some suitable $n_0>216$. You can do this in stages; for $n\leq 32$, $\lceil n/4\rceil<9$ which gives you some bound like $13n$ in that region. Then you get a worse bound in the region $32<n\leq 128$, and so on.

This means you will get one bound $b_1$ for $n\leq 256$ and another value $b_2$ such that for all $b\geq b_2$ the inductive step works for all $n>256$. Then that means you can prove $\max(b_1,b_2)$ will work by induction, with the "base case" being all $n\leq 256$.

Especially Lime
  • 40,828