Mathematical Induction

PROBLEMS
1 Use mathematical induction to show that the product of any n consecutive positive integers is divisible by n!
Hint: Use the identity: m(m + 1)…(m + n - 1)/n! = (m - 1)m(m + 1)… (m + n - 2)/n! + m(m + 1) …(m + n - 2)/(n — 1)!
SOLUTION
Theorem: Product of any n consecutive positive integers is divisible by n!
Proof:
* Base case: For (n = 1), the product of 1 consecutive positive integer (m) is m. Since (1! = 1), m is divisible by 1!. (the base case holds).
* Inductive hypothesis: For some positive integer k, the product of k consecutive positive integers is divisible by k!.
* Induction requirement: If the inductive hypothesis holds for k, then it also holds for k + 1.
* Let the product of (k + 1) consecutive positive integers be:
P(k + 1) = (m)(m + 1)(m + 2)...(m + k)………………(i)
* Using the question hint, let’s express P(k + 1) in equation (i) above as:
P(k + 1) = (m - 1)m(m + 1)...(m + k - 1) / k! + m(m + 1)...(m + k - 1) / (k - 1)!........(ii)
* Combining (i) and (ii) the product in (i) becomes
(m)(m + 1)(m + 2)...(m + k) = (m - 1)m(m + 1)...(m + k - 1) / k! + m(m + 1)...(m + k - 1) / (k - 1)!
* Following the inductive hypothesis:
(m - 1)m(m + 1)...(m + k - 1) is divisible by (k - 1)!.
* The first term on the right-hand side in equation (ii) is
{(m - 1)m(m + 1)...(m + k - 1) / k!}.....................................(term 1)
* And since: (m - 1)m(m + 1)...(m + k - 1) is divisible by (k - 1)!, the first term is divisible by k!.
* The second term in the right-hand side of equation (ii) is:
{m(m + 1)...(m + k - 1) / (k - 1)!}.........................................(term 2)
* Term 2 can be rewritten as;
(k + 1)m(m + 1)...(m + k - 1) / [(k + 1)(k - 1)!]……………..……..(iii)
* Simplifying equation (iii), we get:
(k + 1)m(m + 1)...(m + k - 1) / k!.....................................................(iv)
Conclusion: Since (k + 1) is a factor of k!, this term is also divisible by k!.
The product of (k + 1) consecutive positive integers is divisible by k!.
Thus by the principle of mathematical induction, the product of any n consecutive positive integers is divisible by n!.
2 Design a Turing Machine that, given two 16-bit binary numbers written on the tape, delimited by A, computes the sum of...