0

enter image description here

Base Case:

Let n = 0

$f(n) = 4$ [def of f] and $cn^2 = 25c$

Therefore we need $4 \leq 25c$ or $c \geq \frac{4}{25}$ (*)

IND STEP: Let $n > 0$. Suppose $f(n) \leq cn^2$ [IH]

Trying to show $f(n+1) \leq c(n+1)^2$

$f(n+1) = 7f\left(\lfloor \frac{n+1}{3} \rfloor \right) + 5(n+1)^2$ [def of f; $n > 0$]

$\leq 7c\left(\lfloor \frac{n+1}{3} \rfloor \right)^2 + 5(n+1)^2$ [IH]

$\leq 7c\left(\frac{n+1}{3} \right)^2 + 5(n+1)^2$ [$\lfloor \frac{n+1}{3} \rfloor \leq \frac{n+1}{3}$]

$= 7c \frac{(n+1)^2}{9} + 5(n+1)^2$ [Algebra]

$= (n+1)^2 (\frac{7}{9} c + 5)$ [Algebra]

How do I find c?

Tinler
  • 1,061

1 Answers1

0

Hint: If $f(n)\leq c_nn^2$, then by your findings $$f(n+1)\leq c_{n+1}(n+1)^2$$ where $c_{n+1} = \frac{7}{9}c_{n} + 5$. Do you know an upper bound for the sequence $c_0,c_1,\ldots$?

Yannik
  • 628
  • I know that $c \geq \frac{4}{25}$ by (*). But I don't know what to make up this since im kind of lost in definitions. Upper bound meaning highest value c could take? $c = \frac{7}{9}c + 5$, $\frac{2}{9}c = 5$, $c = \frac{45}{2}$ , iunno – Tinler Oct 19 '17 at 07:50
  • An upper bound is just a number $b$ such that $c_n\leq b$ for all $n$. Also, note that you can write $c_n = \left(\tfrac{7}{9}\right)^n c_0 + 5\sum_{i=0}^{n-1}\left(\tfrac{7}{9}\right)^i$ with $c_0 = \frac{4}{25}$. The first term is decreasing and less or equal to $c_0$ and the second term is a geometric serie, which is increasing and can be bounded by it's limit. – Yannik Oct 19 '17 at 07:56