Chapter 5: Induction and Recursion

Suppose that m and n are positive integers with m>n and f is a function from {1, 2,..., m} to {1, 2,...,n}. Use mathematical induction on the variable n to show that f is not one-to-one.

Describe the quick sort algorithm using pseudocode.

Prove that $\mathbf{A}\mathbf{(}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{>}\mathbf{A}\mathbf{(}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{)}$whenever m and n are nonnegative integers.

Use mathematical induction to show that n people can divide a cake (where each person gets one or more separate pieces of the cake) so that the cake is divided fairly, that is, in the sense that each person thinks he or she got at least $\left(\frac{1}{n}\right)$ th of the cake. [Hint: For the inductive step, take a fair division of the cake among the first k people, have each person divide their share into what this person thinks are k+1 equal portions, and then have the $\left(k+1\right)$st person select a portion from each of the k people. When showing this produces a fair division for k + 1 people, suppose that person k+1 thinks that person i got ${\mathit{P}}_{\mathbf{i}}$ of the cake where $\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{k}}\mathbf{ }{\mathit{p}}_{\mathbf{i}}\mathbf{=}\mathbf{1}$.]

(a) Show that if \({a_1},{a_2},\, \cdots ,\,{a_n}\) are positive integers then\(gcd\left( {{a_1},{a_2},\, \cdots ,\,{a_{n - 1}},\,{a_n}} \right) = gcd\left( {{a_1},{a_2},\, \cdots {a_{n - 2}},\,gcd\left( {{a_{n - 1}},\,{a_n}} \right)} \right)\).

(b) Use part (a), together with the Euclidean algorithm, to develop a recursive algorithm for computing the greatest common divisor of a set of \(n\) positive integers.

Prove that $\mathbf{A}\mathbf{(}\mathbf{m}\mathbf{+}\mathbf{1}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{\ge }\mathbf{A}\mathbf{(}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{)}$whenever m and n are nonnegative integers.

Describe a recursive algorithm for writing the greatest common divisor of \(n\) positive integers as a linear combination of these integers.

Prove that $\mathbf{A}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{)}\mathbf{\ge }\mathbf{j}$whenever i and j are nonnegative integers

Use mathematical induction to prove that a function F defined by specifying F (0) and a rule for obtaining F (n + 1) from F (n) is well defined.

Use strong induction to prove that a function F defined by specifying F (0) and a rule for obtaining F (n + 1) from the values F (k) for k = 0,1,2,......n is well defined.