Chapter 5: Induction and Recursion

Let$\mathit{P}\mathbf{\left(}\mathit{n}\mathbf{\right)}$ be the statement that a postage of n cents can be formed using 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that$\mathit{P}\mathbf{\left(}\mathit{n}\mathbf{\right)}$ is true for$\mathit{n}\mathbf{\ge }\mathbf{18}$ .

(a) Show statements $\mathit{P}\mathbf{\left(}\mathbf{18}\mathbf{\right)}\mathbf{,}\mathit{P}\mathbf{\left(}\mathbf{19}\mathbf{\right)}\mathbf{,}\mathit{P}\mathbf{\left(}\mathbf{20}\mathbf{\right)}$ and$\mathit{P}\left(32\right)$ are true, completing the basis step of the proof.

(b) What is the inductive hypothesis of the proof?

(c) What do you need to prove in this inductive step?

(d) Complete the inductive step for $\mathit{k}\mathbf{\ge }\mathbf{21}$.

(e) Explain why these steps show that statement is true whenever

Let P(n)be the statement that ${\mathbf{1}}^{\mathbf{3}}\mathbf{+}{\mathbf{2}}^{\mathbf{3}}\mathbf{+}\mathbf{\dots }\mathbf{+}{\mathit{n}}^{\mathbf{3}}\mathbf{=}\mathbf{\left(}\mathit{n}\mathbf{\right(}\mathit{n}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{/}\mathbf{2}{\mathbf{)}}^{\mathbf{2}}$ for the positive integer .

a) What is the statement P(1)?

b) Show that P(1) is true, completing the basis step of

the proof.

c) What is the inductive hypothesis?

d) What do you need to prove in the inductive step?

e) Complete the inductive step, identifying where you

use the inductive hypothesis.

f) Explain why these steps show that this formula is true wheneveris a positive integer.

Trace Algorithm 3 when it finds gcd (12,17) . That is, show all the steps used by Algorithm 3 to find gcd (12,17).

Give two different examples of proofs that use strong induction.

a) We have a strong induction to show whether you can run one mile or two miles and whether you can always run two more. miles, once you've run the specified number of miles, you can run any number of miles.

b) Show that if n is an integer greater than 1, then n can be written as a product of prime numbers.

Use mathematical induction to show that

\(\frac{1}{{1 \cdot 3}} + \frac{1}{{3 \cdot 5}} + ... + \frac{1}{{\left( {2n - 1} \right) \cdot \left( {2n + 1} \right)}} = \frac{n}{{2n + 1}}\)

whenever nis a positive integer.

Show that $\mathbf{A}\mathbf{(}\mathbf{1}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{=}{\mathbf{2}}^{\mathbf{n}}\mathbf{\text{whenever}}\mathbf{n}\mathbf{\ge }\mathbf{1}$.

What is wrong with this “proof”? “Theorem” For every positive integer n, $\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathbf{ }\mathit{i}\mathbf{=}\frac{{\left(n+\frac{1}{2}\right)}^{\mathbf{2}}}{\mathbf{2}}\mathbf{.}$.

Basis Step: The formula is true for n = 1.

Inductive Step: Suppose that$\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathbf{ }\mathbf{i}\mathbf{=}\frac{{\left(n+\frac{1}{2}\right)}^{\mathbf{2}}}{\mathbf{2}}\mathbf{.}\mathbf{}\mathbf{Then}\mathbf{}\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}\mathbf{+}\mathbf{1}}\mathbf{ }\mathbf{i}\mathbf{=}\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathbf{ }\mathbf{i}\mathbf{+}\mathbf{(}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{)}$. Then. By the inductive hypothesis,

$$\begin{gathered} \mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}\mathbf{+}\mathbf{1}}\mathbf{=}\frac{{\mathbf{n}}^{\mathbf{2}}\mathbf{+}\mathbf{n}\mathbf{+}\frac{\mathbf{1}}{\mathbf{4}}}{\mathbf{2}}\mathbf{+}\mathbf{n}\mathbf{+}\mathbf{1} \\ \mathbf{=}\frac{{\mathbf{n}}^{\mathbf{2}}\mathbf{+}\mathbf{3}\mathbf{n}\mathbf{+}\frac{\mathbf{9}}{\mathbf{4}}}{\mathbf{2}} \\ \mathbf{=}\frac{{\mathbf{(}\mathbf{n}\mathbf{+}\frac{\mathbf{3}}{\mathbf{2}}\mathbf{)}}^{\mathbf{2}}}{\mathbf{2}} \\ \mathbf{=}\frac{{\mathbf{\left(}\mathbf{(}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{+}\frac{\mathbf{1}}{\mathbf{2}}\mathbf{\right)}}^{\mathbf{2}}}{\mathbf{2}} \end{gathered}$$

completing the inductive step.

Show that planes divide three-dimensional space into (n + 5n + 6)/ 6 regions if any three of these planes have exactly one point in common and no four contain a common point.

What is wrong with this “proof”? “Theorem” For every positive integer n, if x and y are positive integers with $\mathbf{max}\mathbf{}\mathbf{(}\mathit{x}\mathit{,}\mathit{y}\mathbf{)}\mathbf{=}\mathit{n}$, then$\mathit{x}\mathbf{=}\mathit{y}$

Basis Step: Suppose that $\mathit{n}\mathbf{=}\mathbf{1}$. If $\mathbf{max}\mathbf{}\mathbf{(}\mathit{x}\mathit{,}\mathit{y}\mathbf{)}\mathbf{=}\mathbf{1}\mathbf{}$and x and y are positive integers, we have $\mathit{x}\mathbf{=}\mathbf{1}$and $\mathit{y}\mathbf{=}\mathbf{1}$.

Inductive Step: Let k be a positive integer. Assume that whenever $\mathbf{max}\mathbf{}\mathbf{(}\mathit{x}\mathit{,}\mathit{y}\mathbf{)}\mathbf{=}\mathit{k}\mathbf{}$and x and y are positive integers, then x = y. Now let $\mathbf{max}\mathbf{}\mathbf{(}\mathit{x}\mathit{,}\mathit{y}\mathbf{)}\mathbf{=}\mathit{k}\mathbf{+}\mathbf{1}\mathbf{}$, where x and y are positive integers. Then , so by the inductive hypothesis, $\mathit{x}\mathbf{-}\mathbf{1}\mathbf{=}\mathit{y}\mathbf{-}\mathbf{1}$. It follows that $\mathit{x}\mathbf{=}\mathit{y}$, completing the inductive step.

Use the well-ordering property to show that \(\sqrt 2 \) is irrational. (Hint: Assume that \(\sqrt 2 \) is rational. Show that the set of positive integers of the form \(b\sqrt 2 \) has a least element \(a\).Then show that \(a\sqrt 2 - a\) is smaller positive integer of this form.)