1
$\begingroup$

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$.

  • 0
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2012-12-01

1 Answers 1

2

1) Prove by induction on $k$:

If $0\le k\le m$, then $T(2^m)=2^kT(2^{m-k})+2^k-1$.

The case $k=0$ is trivial. If we already know that $T(2^m)=2^{k-1}T(2^{m-(k-1)})+2^{k-1}-1$ for all $m\ge k-1$, then for $m\ge 2^k$ we have $\begin{align}T(2^m)&=2^{k-1}T(2^{m-(k-1)})+2^{k-1}-1\\ &=2^{k-1}\left(2\cdot T\left(\tfrac{2^{m-(k-1)}}2\right)+1\right)+2^{k-1}-1\\ &=2^k T(2^{m-k})+2^k-1\end{align}$

2) Note that $H(2(m+1))-H(2m)=\frac 1{2m+1}+\frac1{2(m+2)}>\frac2{2m+2}=H(m+1)-H(m)$ and therefore (by induction on $d$) for $d>0$ $H(2(m+d))-H(2m)>H(m+d)-H(m)$ hence with $m=d=2^{n-1}$ $H(2^{n+1})-H(2^n)>H(2^n)-H(2^{n-1})$ thus by induction on $n$ $H(2^n)-H(2^{n-1})>H(4)-H(2)=\frac7{12}\text{ if }n\ge2$ and finally by induction on $n$ $H(2^n)>H(16)+\frac7{12}(n-4)\text{ for }n\ge 4.$