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


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