HW5 詳解

Question 1

問題1

page 350, Section 5.1 Exercise 6

Prove that $1 ⋅ 1! + 2 ⋅ 2! + ⋯ + n ⋅ n! = (n + 1)! − 1$ whenever $n$ is a positive integer.

問題1

page 350, Section 5.1 Exercise 6

Prove that $1 ⋅ 1! + 2 ⋅ 2! + ⋯ + n ⋅ n! = (n + 1)! − 1$ whenever $n$ is a positive integer.
  1. Basis Step: Show that P(1) is true.
  2. Inductive Step: Show that P(k) → P(k + 1) is true for all positive integers k.

To complete the inductive step, assuming the inductive hypothesis that P(k) holds for an arbitrary integer k, show that must P(k + 1) be true.
  • Basis step:
    $n = 1,P(1)$ is true, since $1 · 1! = (1 + 1)! - 1 = (2)! - 1$
  • Inductive step:
    1. Inductive hypothesis, assume $P(k)$ holds for an arbitrary positive integer $k$.$1 · 1! + 2 · 2! + ... + k · k! = (k + 1)! - 1$ Add $(k + 1) · (k + 1)!$ to both sides of the equation in $P(k)$,
    2. we obtain
      $\begin{eqnarray*} 1 · 1! + ... + k · k! + (k + 1) · (k + 1)! & = & (k + 1)! - 1 + (k + 1) · (k + 1)! \\ ~ & = & (k + 1)!(1 + k + 1) - 1 \\ ~ & = & (k + 2)! - 1 \end{eqnarray*}$
    3. By mathematical induction, $P(n)$ is true for all integer $n$ with $n \geq 1$.
Question 2

問題2

page 351, chapter 5.1 Exercise 18

Let $P(n)$ be the statement that $n! < n^n$, where $n$ is an integer greater than 1.
  1. What is the statement $P(2)$?
  2. Show that $P(2)$ is true, completing the basis step of a proof by mathematical induction that $P(n)$ is true for all integers n greater than 1.
  3. What is the inductive hypothesis of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1?
  4. What do you need to prove in the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1?
  5. Complete the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1.
  6. Explain why these steps show that this inequality is true whenever $n$ is an integer greater than 1.
    7.
Let $P(n)$ be the statement that $n! < n^n$, where $n$ is an integer greater than 1.
  1. What is the statement $P(2)$?
  2. Show that $P(2)$ is true, completing the basis step of a proof by mathematical induction that $P(n)$ is true for all integers n greater than 1.
  3. What is the inductive hypothesis of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1?
  4. What do you need to prove in the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1?
  5. Complete the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1.
  6. Explain why these steps show that this inequality is true whenever $n$ is an integer greater than 1.
    7.

  1. Plugging in $n = 2$, we see that $P(2)$ is the statement $2! < 2^2$.
  2. Since $2! = 2$, this is the true statement $2 < 4$.
  3. The inductive hypothesis is the statement that $k! < k^k$.
  4. For the inductive step, we want to show for each $k ≥ 2$ that $P(k)$ implies $P(k+1)$. In other words, we want to show that assuming the inductive hypothesis (see part (c)) we can prove that $(k+1)! < (k+1)^{k+1}$.
  5. $(k+1)! = (k+1)k! < (k + 1)k^k < (k + 1)(k + 1)^k = (k + 1)^{k+1}$
  6. We have completed both the basis step and the inductive step, so by the principle of mathematical induction, the statement is true for every positive integer $n$ greater than 1.
    7.