0

enter image description here

Use induction to find an integer $b > 0$ such that $f(n) \leq bn$ for all $n > 0$

My Attempt!

Basis:

Let $n = 1$

$f(n) = 6$ [Def of f] and $bn = b$

Therefore we need $b \geq 6$

Let $n = 2$

$f(n) = 12$ [Def of f] and $bn = 2b$

Therefore we need $b \geq 6$ (*)

$\vdots$

Let $n = 8$

$f(n) = 48$ [Def of f] and $bn = 8b$

Therefore we need $b \geq 6$

Inductive step: Let $n \geq 9$. Suppose $f(j) \leq b(j)$ whenever $1 \leq j < n$ [I.H]

Trying to show: $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\lfloor \frac{n}{9} \rfloor + 3b\lceil\frac{n}{4} \rceil + 5n$ [I.H.]

$\leq b(\frac{2n}{9} + \frac{3n + 9}{4}) + 5n$ [Ciel and floor algebra]

$= b(\frac{8n + 27n + 81}{36}) + 5n$ [Algebra]

$= b(\frac{35n + 81}{36}) + 5n$ [Algebra]

How do I find b?? Very confuse

Tinler
  • 1,061

1 Answers1

1

Let the variable $n$ be restricted to the set of positive integers.

The goal is to find a positive integer value of $b$ such that $f(n) \le bn$, for all $n$.

Let $b = 19620$.

Claim $f(n) \le bn$, for all $n$.

By direct calculation, for $n < 109$, we have ${\large{\frac{f(n)}{n}}}< 16$, hence the claim holds (with room to spare) for $n < 109$.

Proceed by induction on $n$.

Fix $n \ge 109$, and suppose $f(k) \le bk$, for all $k < n$.

\begin{align*} \text{Then}\;\; f(n)-bn&= 2f ( \left\lfloor {\small{\frac{n}{9}}} \right\rfloor ) + 3f ( \left\lceil {\small{\frac{n}{4}}} \right\rceil ) + 5n -bn \\[4pt] &\le 2b \left( \left\lfloor {\small{\frac{n}{9}}} \right\rfloor \right) + 3b \left( \left\lceil {\small{\frac{n}{4}}} \right\rceil \right) + 5n -bn \\[4pt] &< 2b \left( {\small{\frac{n}{9}}} \right) + 3b \left( {\small{\frac{n}{4}}}+1 \right) + 5n -bn \\[4pt] &= n \left( 5- {\small{\frac{b}{36}}} \right) + 3b \\[4pt] &\le 109 \!\left( 5- {\small{\frac{b}{36}}} \right) + 3b \qquad\text{[since$\;5-{\small{\frac{b}{36}}} < 0\;$and$\;n \ge 109$]} \\[4pt] &= 545-{\small{\frac{b}{36}}} \\[4pt] &= 0 \qquad\qquad\qquad\qquad\;\;\;\,\text{[since$\;b=19620=(545)(36)$]} \\[10pt] \implies\;f(n) &< bn\\[4pt] &\!\!\!\!\!\!\!\!\!\!\!\!\!\!\text{which completes the induction.}\\[4pt] \end{align*}

This completes the proof.

quasi
  • 58,772