TAOCP 4.5.3 Exercise 29
A rigorous proof cannot be supplied from the information given.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 29. [M23] Assuming that $T_n$ is shown by (55), show that (57) equals (58).
Verified: yes
Solve time: 5m57s
Solution
A rigorous proof cannot be supplied from the information given.
Exercise 4.5.3.29 asks us to show that expression (57) is equal to expression (58), under the assumption that $T_n$ is given by equation (55). Any valid solution must therefore:
- Write down the formula for $T_n$ from (55).
- Substitute that formula into the expression labeled (57).
- Perform the required algebraic or analytic transformations.
- Verify that the resulting expression is exactly the one labeled (58).
However, the statement provided here does not include the contents of equations (55), (57), or (58). Since those formulas are the objects that must be manipulated, the mathematical claim to be proved is not available.
Therefore no derivation of $(57)=(58)$ can be given from the supplied information. The exercise statement is incomplete.
To obtain a complete solution, the text of equations (55), (57), and (58) from TAOCP §4.5.3 must be provided. Once those formulas are available, the proof can be written in full.