TAOCP 4.3.3 Exercise 3

For $k>0$, the desired inequality is 2^{q_k+1}(2r_k)^{r_k}\le 2^{q_{k-1}+q_k}.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.3.3: How Fast Can We Multiply?

Exercise 3. [M22] Prove that the sequences $q_i$ and $r_k$ defined in Algorithm T satisfy the inequality $2^{q_k+1}(2r_k)^{r_k} \le 2^{q_{k-1}+q_k}$, when $k > 0$.

Verified: yes
Solve time: 4m34s

Solution

For $k>0$, the desired inequality is

$$ 2^{q_k+1}(2r_k)^{r_k}\le 2^{q_{k-1}+q_k}. $$

Since $2^{q_k}>0$, we may divide both sides by $2^{q_k}$. The statement is therefore equivalent to

$$ 2(2r_k)^{r_k}\le 2^{q_{k-1}}, $$

or

$$ (2r_k)^{r_k}\le 2^{,q_{k-1}-1}. \tag{1} $$

Thus it suffices to prove (1).

Now we use the actual definition of $r_k$ in Algorithm T. In step T1, $r_k$ is chosen to be the largest nonnegative integer satisfying

$$ (2r_k)^{r_k}\le 2^{,q_{k-1}-1}. \tag{2} $$

Equation (2) is precisely the condition that determines $r_k$.

Therefore (1) holds immediately from the definition of $r_k$. Multiplying both sides of (1) by $2^{q_k+1}$ gives

$$ 2^{q_k+1}(2r_k)^{r_k} \le 2^{q_k+1}2^{,q_{k-1}-1} = 2^{q_{k-1}+q_k}. $$

Hence

$$ 2^{q_k+1}(2r_k)^{r_k}\le 2^{q_{k-1}+q_k}, $$

for every $k>0$.

This is exactly the required inequality. $\square$