TAOCP 1.2.3 Exercise 24

Let P(R)=\prod_{R(j)} a_j, \qquad S(R)=\sum_{R(j)} (\log_b a_j),

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.3: Sums and Products

Exercise 24. [20] Suppose that $R(j)$ is true for only finitely many $j$. By induction on the number of integers satisfying $R(j)$, prove that $\log_b \prod_{R(j)} a_j = \sum_{R(j)} (\log_b a_j)$, assuming that all $a_j > 0$.

Verified: yes
Solve time: 33s

Solution

Let

$$ P(R)=\prod_{R(j)} a_j, \qquad S(R)=\sum_{R(j)} (\log_b a_j), $$

where all $a_j>0$. We shall prove that

$$ \log_b P(R)=S(R) $$

whenever $R(j)$ is true for only finitely many integers $j$.

The proof is by induction on the number of integers satisfying $R(j)$.

For the basis step, suppose that no integer satisfies $R(j)$. By the definition of product notation in Eq. (20),

$$ \prod_{R(j)} a_j = 1. $$

Also, by the definition of summation over an empty domain,

$$ \sum_{R(j)} (\log_b a_j)=0. $$

Hence

$$ \log_b \prod_{R(j)} a_j = \log_b 1 = 0 = \sum_{R(j)} (\log_b a_j). $$

Therefore the theorem holds when the number of integers satisfying $R(j)$ is $0$.

Assume now that the theorem holds whenever exactly $n$ integers satisfy the relation, and consider a relation $R(j)$ that is true for exactly $n+1$ integers.

Choose one integer $k$ such that $R(k)$ is true. Define a new relation

$$ R'(j) = R(j)\text{ and }j\ne k. $$

Then $R'(j)$ is true for exactly $n$ integers. By the induction hypothesis,

$$ \log_b \prod_{R'(j)} a_j = \sum_{R'(j)} (\log_b a_j). $$

By the analog of rule (d) for products,

$$ \prod_{R(j)} a_j = a_k \prod_{R'(j)} a_j, $$

since the domains overlap in no values of $j$.

Taking logarithms,

$$ \log_b \prod_{R(j)} a_j = \log_b \left(a_k \prod_{R'(j)} a_j\right). $$

Using the elementary property of logarithms,

$$ \log_b(xy)=\log_b x+\log_b y, $$

valid for positive $x$ and $y$, we obtain

$$ \log_b \prod_{R(j)} a_j = \log_b a_k + \log_b \prod_{R'(j)} a_j. $$

Applying the induction hypothesis gives

$$ \log_b \prod_{R(j)} a_j = \log_b a_k + \sum_{R'(j)} (\log_b a_j). $$

Since $R(j)$ consists of the disjoint union of the single value $j=k$ and the values satisfying $R'(j)$, the analog of Eq. (11) for sums yields

$$ \log_b a_k + \sum_{R'(j)} (\log_b a_j) = \sum_{R(j)} (\log_b a_j). $$

Therefore

$$ \log_b \prod_{R(j)} a_j = \sum_{R(j)} (\log_b a_j). $$

Thus the theorem holds whenever $R(j)$ is true for exactly $n+1$ integers. By induction, it holds for all finite domains.

This completes the proof.

∎