Question

Show that if${\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathbf{a}}_{\mathbf{n}}$ are distinct real numbers, exactlyn -1 multiplications are used to compute the product of thesen numbers no matter how parentheses are inserted into their product. [Hint: Use strong induction and consider the last multiplication.]

Short answer

$a_1,a_2,...,a_n$aren distinct real numbers.

Step-by-step solution

Significance of the induction

The induction is described as a technique that is used to prove a theorem or statement. The induction comprises of two types such as simple and strong induction.

Determination of the proof of the statement

Let$P\left(n\right)$ is described as the statement “exactly$n-1$ multiplications are used to compute the product of then numbers $a_1,a_2,...,a_n$”.

In the basis step, let $n=1$, when there are one number that is $a_1$, then 0 multiplications are needed for computing the product of$a_1$ the number 1 . Hence $P\left(1\right)$, holds true.

In the inductive step, let$P\left(1\right),P\left(2\right),...,P\left(k\right)$ holds true. Exactly$n-1$ multiplications are used to compute the product of the n numbers$a_1,a_2,...,a_n$ for the numbers$i=1,2,...,k$. It is needed to be proved that$P(k+1)$ holds true.

The product ofrole="math" localid="1668580066096" $a_1,a_2,...,a_k,a_{k+1}$ is to be determined. It has been assumed that the last multiplication lies between the last$k+1-i$ terms product and terms product as $i\ge 1$.

The equation of the product is expressed as:

$(a_1,a_2,...,a_i)(a_{i+1},a_{i+2},...,a_k,a_{k+1})$

As$P\left(i\right)$ holds true, then$i-1$ multiplications are required for computing $a_1,a_2,...,a_i$. Moreover, as$P(k+1-i)$ holds true, then$k+1-i-1=k-i$ multiplications are required for computing .

One additional level of multiplication is required for determining the product of the numbers role="math" localid="1668580192352" $a_{i+1},a_{i+2},...,a_k,a_{k+1}$and $a_1,a_2,...,a_i$. Hence, totally$i-1+k-i+1=k+1-1$ multiplications are required for computing $a_1,a_2,...,a_k,a_{k+1}$. Hence, holds true.

Thus,$a_1,a_2,...,a_n$ aren distinct real numbers.