First hello all, we have a lecture. It has 10 questions but I'm stuck with these two about 3 hours and I can't solve them. Any help would be appreciated.
Question 1
Given that $T(1)=1$, and $T(n)=2T(\frac{n}{2})+1$, for $n$ a power of $2$, and greater than $1$. Using mathematical induction, prove that
$T(n) = 2^k.T(\frac{n}{2^k}) + 2^k - 1$
for $k=0, 1, 2, \dots, \log_2 n$.
Question 2
Definition: $H(j) = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{j}$. Facts: $H(16) > 3.38$, $\frac{1}{3} + \frac{1}{4} = \frac{7}{12}, \frac{1}{4} + \frac{1}{5} + \frac{1}{7} = \frac{319}{420} $ a) Using induction on $n$, prove that $H(2^n) > 1 + 7n/12$, for $n\geq 4$.