Proving inequality.. Question:
$$
f(a,b)= \begin{cases} ja & \text{if } b \le 2 \\ jb & \text{if } a \le 2 \\ jab + f(d, \frac{b}{2}) + f(a-d, \frac{b}{2}) & \text{if } a,b >2\end{cases}
$$ where $\ j$ is a positive constant and $ \ 1 \le d<a$.
Prove using some form of induction  that $f(a,b) = \Theta(ab)$ or $ f(a,b) = \Theta(a^2b^2)$. Only one is correct.
My attempt:
I think that $ f(a,b) = \Theta(ab)$. We first have to show that $ f(a,b) = O(ab)$ and $ \ f(a,b) = \Omega(ab)$.
Prove $ \ f(a,b) = O(ab)$:
We must show there exist positive constants $c$ and $ n_0$ such that $ \ f(a,b) \le cab$ for $a,b \ge n_0$.
Base cases:
$a=1$: $f(a,b) = jb$ by definition. If we let $a=b$ then  $jb \le cb^2$.
$b=1$: $f(a,b) = ja$ by definition. If we let $a=b$ then  $ja \le ca^2$.
$a=2$: $f(a,b) = jb$ by definition. If we let $a=b$ then  $jb \le cb^2$.
$b=2$: $f(a,b) = ja$ by definition. If we let $a=b$ then  $ja \le ca^2$.
I don't understand how to do the induction step. What should I assume in my induction hypothesis and how should I complete the proof? 
 A: We assume that the domain of $f$ is a set $\Bbb R^2_+$ of pairs $(a,b)$ of non-negative real numbers and the third row of the definition means that there exists $d$ such that the claim holds. Remark that $f(a,b)=O(ab)$ fails, for instance for the sequence $a_n=\frac 1n$ and $b_n=n^2$, because then $a_nb_n=n$, whereas $f(a_n,b_n)=jn^2$. So the problem conclusion should be corrected too. 
We use induction by $n$ to show that $\left(2-\frac 3{2^{n}}\right)jab-3jb\le  f(a,b)\le \left(2-\frac 3{2^{n}}\right)jab+ja+jb$, where $n$ is the smallest positive integer such that $b\le 2^n$. For $n=1$ this follows from the definition of $f$. Assume that we have already proved the inequality for $n\ge 1$ and assume that $2^{n}<b\le 2^{n+1}$. Then $n$ is the smallest positive number such that $\frac b2\le 2^n$. If $a\le 2$ then $f(a,b)=jb$ and it is easy to check that the inequality holds. If $a>2$ then by the inductive assumption 
$$f(a,b)=jab + f\left(d, \frac{b}{2}\right) + f\left(a-d, \frac{b}{2}\right)\ge $$ $$jab + \left(2-\frac 3{2^{n}}\right)jd\frac{b}{2} + \left(2-\frac 3{2^{n}}\right)j(a-d)\frac{b}{2}-3j\frac{b}{2}-3j\frac{b}{2} =$$ $$\left(2-\frac 3{2^{n+1}}\right)jab-3jb.$$
$$f(a,b)=jab + f\left(d, \frac{b}{2}\right) + f\left(a-d, \frac{b}{2}\right)\le $$ $$jab + \left(2-\frac 3{2^{n}}\right)jd\frac{b}{2} + \left(2-\frac 3{2^{n}}\right)j(a-d)\frac{b}{2}+jd+j\frac{b}{2}+j(a-d)+j\frac{b}{2}=$$ $$\left(2-\frac 3{2^{n+1}}\right)jab+ja+jb.$$
A: https://mcs.utm.utoronto.ca/~236/ps/ps3.pdf
Would suggest others avoid answering this blatant attempt to cheat.
