# Two questions with mathematical induction

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

-
For some basic information about writing math at this site see e.g. here, here, here and here. – Julian Kuelshammer Dec 1 '12 at 12:27

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