课程： 12.9 上岗证明 | The Way To Learn

章节大纲

选择节常规

折叠展开
常规

全部折叠展开全部
- 选择活动新闻通告
  
  新闻通告讨论区

上岗证明

Induction is one of many methods for proving mathematical statements about numbers. The basic idea is that you prove a statement is true for a small number like 1. This is called the base case. Then, you show that if the statement is true for some random number $\begin{align*}k\end{align*}$ , then it must also be true for $\begin{align*}k+1\end{align*}$ .
::上岗是证明数字数学语句的多种方法之一。基本的想法是, 您证明一个语句对像 1 这样的小数字来说是真实的。这被称为基数。然后, 您会显示, 如果语句对某些随机数k 来说是真实的, 那么它也必须是真实的叉+ 1 。

An induction proof is like dominoes set up in a line, where the base case starts the falling cascade of truth. Once you have shown that in general if the statement is true for $\begin{align*}k\end{align*}$ then it must also be true for $\begin{align*}k+1\end{align*}$ , it means that once you show the statement is true for 1, then it must also be true for 2, and then it must also be true for 3, and then it must also be true for 4 and so on.
::上岗证明就像Dominoes在一条线上设置的, 基案开始的是真理的串联。一旦您已经展示了一般情况下, 如果语句对 k 来说是真实的, 那么K+1 也必须是真实的, 这意味着一旦您展示了语句对 1 是真实的, 那么它也必须对 2 也是真实的, 然后它也必须对 3 也是真实的, 然后它也必须对 4 等来说也是真实的。

What happens when you forget the base case?
::当你忘记基本情况时会怎样?

Proof by Induction
::上岗证明

Induction is a method of proof usually used to prove statements about positive whole numbers (the natural numbers). Induction has three steps:
::上岗是一种证明方法,通常用来证明关于正整数(自然数字)的报表。

The base case is where the statement is shown to be true for a specific number. Usually this is a small number like 1. This is the first domino to fall, creating a cascade and thus proving the statement true for every number greater than the base case.
::基例是指对某个具体数字的语句显示为真实的语句。通常是像 1 这样的小数字。这是第一个跌落的多米诺语句, 创建了一个级联, 从而证明语句对每个比基例大的数字都是真实的。

The inductive hypothesis is where the statement is assumed to be true for $\begin{align*}k\end{align*}$ .
::推理假设是假定声明对k是真实的。

The inductive step/proof is where you show that then the statement must be true for $\begin{align*}k+1\end{align*}$ .
::感应步骤/ 校准是您要显示 k+1 的语句必须是真实的。

These three logical pieces will show that the statement is true for every number greater than the base case.
::这三个逻辑部分将表明,每个比基数大的数字都符合该说明。

Suppose you wanted to use induction to prove: $\begin{align*}n \ge 1,2+2^2+2^3+ \cdots + 2^n=2^{n-1}-2\end{align*}$ .
::假设你想用感应来证明: n1,2+22+232n=2n-1-2-2。

Start with the Base Case. Show that the statement works when $\begin{align*}n=1\end{align*}$ :
::以基准大小写开始。显示语句在 n= 1 时有效 :

$\begin{align*}2^1=2\end{align*}$ and $\begin{align*}2^{1+1}-2=4-2=2\end{align*}$ . Therefore, $\begin{align*}2^1=2^{1+1}-2\end{align*}$ . (Both sides are equal to 2)
::21=2和21+1-2-2=4-2=2。因此,21=21+1-2。 (两边等于2)

Next, state your Inductive Hypothesis. Assume that the statement works for some random number $\begin{align*}k\end{align*}$ :
::接下来,请说明你的感应假设。假设该语句使用随机数字 k:

$\begin{align*}2+2^2+ \cdots +2^k=2^{k+1}-2\end{align*}$ (You are assuming that this is a true statement)
::2+222k=2k+1-2(你假定这是真实的陈述)

Next, you will want to use algebra to manipulate the previous statement to prove that the statement is also true for $\begin{align*}k+1\end{align*}$ . So, you will be trying to show that $\begin{align*}2+2^2+ \cdots +2^{k+1}=2^{k+1+1}-2\end{align*}$ . Start with the inductive hypothesis and multiply both sides of the equation by 2. Then, do some algebra to get the equation looking like you want.
::接下来,您会想要使用代数来操纵先前的语句, 以证明语句对 k+1 也是真实的。因此, 您将尝试显示 2+22\\\\ 2k+1= 2k+1+1-2 。从直线假设开始, 并将方程的两边乘以 2 。然后, 做一些代数来让方程看起来像您想要的一样。

Inductive Hypothesis (starting equation): $\begin{align*}2+2^2+ \cdots 2^k=2^{k+1}-2\end{align*}$
::诱导假设(启动方程):2+222k=2k+1-2

Multiply by 2: $\begin{align*}2(2+2^2+ \cdots +2^k)=2(2^{k+1}-2)\end{align*}$
::乘以 2 2: 2 2+22 2k) = 2 2k+1-2)

Rewrite: $\begin{align*}2^2+2^3+ \cdots + 2^{k+1}=2^{k+1+1}-4\end{align*}$
::重写: 22+232k+1=2k+1+1- 4

Add 2 to both sides: $\begin{align*}2+2^2+2^3 + \cdots + 2^{k+1}=2^{k+1+1}-4+2\end{align*}$
::双方加2:2+22+23+23+2k+1=2k+1+1+1+4+2

Simplify: $\begin{align*}2+2^2+ \cdots +2^{k+1}=2^{k+1+1}-2\end{align*}$
::简化: 2+222k+1=2k+1+1+1-2

This is exactly what you were trying to prove! So, first you showed that the statement worked for $\begin{align*}n=1\end{align*}$ . Then, you showed that the if the statement works for one number than it must work for the next number. This means, the statement must be true for all numbers greater than or equal to 1.
::这正是你试图证明的! 所以, 首先你展示了语句为 n=1 工作。然后, 你展示了如果语句为一个数字工作, 而不是下一个数字。这意味着语句必须对所有大于或等于 1 的数字都适用。这意味着, 语句必须是真实的。

The idea of induction can be hard to understand at first and it definitely takes practice. One thing that makes induction tricky is that there is not a clear procedure for the “proof” part. With practice, you will start to see some common algebra techniques for manipulating equations to prove what you are trying to prove.
::诱导的概念一开始可能很难理解,而且肯定需要实践。诱导的难度在于“防伪”部分没有明确的程序。在实践中,你将开始看到一些常见的代数技术来操纵方程式来证明你试图证明什么。

Examples
::实例

Example 1
::例1

Earlier, you were asked what happens if you forget the base case in induction. If you forget the base case in an induction proof, then you haven’t really proved anything. You can get silly results like this “proof” of the statement: “ $\begin{align*}1=3\end{align*}$ ”
::早些时候,有人问过,如果你忘记了在诱导中的基本案例。如果你忘记了在诱导证据中的基本案例,那么你并没有真正证明什么。你可以得到类似“1=3”的“证据”这样的愚蠢的结果。

Base Case: Missing
::基案:失踪

Inductive Hypothesis: $\begin{align*}k=k+1\end{align*}$ where $\begin{align*}k\end{align*}$ is a counting number.
::感想假说:k=k+1, K是数字。

Proof: Start with the assumption step and add one to both sides.
::证据:从假设步骤开始,在双方增加一个。

\begin{aligned} k & = k + 1 \\ k + 1 & = k + 2 \end{aligned}

$\begin{align*}k &=k+1 \\ k+1 &=k+2\end{align*}$
::k=k+1k+1=k+2

Thus by transitivity of equality:
::因此,通过平等的过渡性:

\begin{aligned} k & = k + 1 = k + 2 \\ k & = k + 2 \end{aligned}

$\begin{align*}k &=k+1=k+2 \\ k &=k+2\end{align*}$
::k=k+1=k+2k=k+2

Since $\begin{align*}k\end{align*}$ is a counting number, $\begin{align*}k\end{align*}$ could equal 1. Therefore:
::K是数字,K可以等于1。因此:

$\begin{align*}1=3\end{align*}$

Example 2
::例2

There is something wrong with this proof. Can you explain what the mistake is?
::这个证据有问题你能解释一下错误是什么吗?

$\begin{align*}For \ n \ge 1: 1^2+2^2+3^2+ \cdots + n^2=\frac{n(n+1)(2n+1)}{6}\end{align*}$
::n1: 12+22+32n2=n(n+1)(2n+1)6

Base Case : $\begin{align*}1=1^2=\frac{1(1+1)(2 \cdot 1+1)}{6}=\frac{1 \cdot 2 \cdot 3}{6}=\frac{6}{6}=1\end{align*}$
::基号: 1=12=1(1+1)(21+1)6=1236=66=1

Inductive Hypothesis: Assume the following statement is true:
::推论假设:假设以下说法属实:

$\begin{align*}1^2+2^2+3^2+ \cdots + k^2=\frac{k(k+1)(2k+1)}{6}\end{align*}$
::12+22+32k2=k(k+1)(2k+1)6

Proof: You want to show the statement is true for $\begin{align*}k+1\end{align*}$ .
::证据: 您想要显示 k+1 的语句是真实的。

“Since the statement is assumed true for $\begin{align*}k\end{align*}$ , which is any number, then it must be true for $\begin{align*}k+1\end{align*}$ . You can just substitute $\begin{align*}k+1 \end{align*}$ in.”
::“既然声明对k来说是真实的,而k是任意数字,那么对于k+1肯定就是真实的。您可以只用 k+1 替换 k+1 英寸。”

$\begin{align*}1^2+2^2+3^2+ \cdots +(k+1)^2=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\end{align*}$
::12+22+32(k+1)2=(k+1)((k+1)+1)(2(k+1)+1)(2(k+1)+1)6

This is the most common fallacy when doing induction proofs. The fact that the statement is assumed to be true for $\begin{align*}k\end{align*}$ does not immediately imply that it is true for $\begin{align*}k+1\end{align*}$ and you cannot just substitute in $\begin{align*}k+1\end{align*}$ to produce what you are trying to show. his is equivalent to assuming true for all numbers and then concluding true for all numbers which is circular and illogical.
::这是做上岗证明时最常见的谬误。 k 假设声明是真实的这一事实并不立即意味着 k+1 确实如此, 你不能仅仅用 k+1 来替代您想要显示的内容。他相当于假设所有数字都是真实的, 然后对所有循环和不合逻辑的数字都得出正确的结论。

Example 3
::例3

Write the base case, inductive hypothesis and what you are trying to show for the following statement. Do not actually prove it.
::写基本案例、感想假设以及您要为以下声明显示的内容。不要实际证明它。

$\begin{align*}1^3+2^3+3^3+ \cdots +n^3=\frac{n^2(n+1)^2}{4}\end{align*}$
::13+23+33n3=n2(n+1)24

Base Case: $\begin{align*}1^3=\frac{1^2(1+1)^2}{4}\end{align*}$ (Both sides are equal to 1)
::基号:13=12(1+1)24 (两边等于1)

Inductive Hypothesis: Assume the following statement is true:
::推论假设:假设以下说法属实:

$\begin{align*}1^3+2^3+3^3+ \cdots +k^3=\frac{k^2(k+1)^2}{4}\end{align*}$
::13+23+33k3=k2(k+1)24

Next, you would want to prove that the following is true:
::其次,你要证明以下事实属实:

$\begin{align*}1^3+2^3+3^3+ \cdots +k^3+(k+1)^3=\frac{(k+1)^2((k+1)+1)^2}{4}\end{align*}$
::13+23+33k3+(k+1)3=(k+1)2((k+1)+1)24

Example 4
::例4

Prove the following statement: $\begin{align*}For \ n \ge 1, 1^3+2^3+3^3+ \cdots n^3=(1+2+3+ \cdots n)^2\end{align*}$ .
::证明以下声明: n1,13+23+33n3=(1+2+3n)2。

Base Case(s): Two base cases are shown however only one is actually necessary.
::基本案件:显示两个基本案件,但实际上只需要一个。

\begin{aligned} 1^{3} & = 1^{2} \\ 1^{3} + 2^{3} & = 1 + 8 = 9 = 3^{2} = (1 + 2)^{2} \end{aligned}

$\begin{align*}1^3 &=1^2 \\ 1^3+2^3 &=1+8=9=3^2=(1+2)^2 \end{align*}$

Inductive Hypothesis: Assume the statement is true for some number $\begin{align*}k\end{align*}$ . In other words, assume the following is true:
::推论假说:假设某些数字 k 的说法是真实的。换句话说,假设以下说法是真实的:

$\begin{align*}1^3+2^3+3^3+ \cdots k^3=(1+2+3+ \cdots k)^2\end{align*}$
::13+23+33k3=(1+2+3k)2

You want to show the statement is true for $\begin{align*}k+1\end{align*}$ . It is a good idea to restate what your goal is at this point. Your goal is to show that:
::您想要显示的语句对 k+1 是真实的。这是一个好主意, 重述您目前的目标是什么。您的目标是要显示 :

$\begin{align*}1^3+2^3+3^3+ \cdots k^3+(k+1)^3=(1+2+3+ \cdots k+(k+1))^2\end{align*}$
::13+23+33k3+(k+1)3=(1+2+3}k+(k+1)2

You need to start with the assumed case and do algebraic manipulations until you have created what you are trying to show (the equation above):
::您需要从假设的大小写开始, 并进行代数操纵, 直到您创建了您想要显示的东西( 以上方程式) :

$\begin{align*}1^3+2^3+3^3+ \cdots k^3=(1+2+3+ \cdots k)^2\end{align*}$
::13+23+33k3=(1+2+3k)2

From the work you have done with arithmetic series you should notice:
::你用算术序列做的工作你该注意到:

$\begin{align*}1+2+3+4+ \cdots +k=\frac{k}{2}(2+(k-1))=\frac{k(k+1)}{2}\end{align*}$
::1+2+3+3+4k=k2( 2+(k-1)=k(k+1)2

Substitute into the right side of the equation and add $\begin{align*}(k+1)^3\end{align*}$ to both sides:
::取代方程式的右侧, 并在两侧添加( k+1) 3:

$\begin{align*}1^3+2^3+3^3+ \cdots k^3+(k+1)^3=\left(\frac{k(k+1)}{2} \right)^2+(k+1)^3\end{align*}$
::13+23+33k3+(k+1)3=(k(k+1)2+(k+1)3+(k+1)3

When you combine the right hand side algebraically you get the result of another arithmetic series.
::当您将右手侧的代数组合在一起时, 你会得到另一个算术序列的结果。

$\begin{align*}1^3+2^3+3^3+ \cdots k^3+(k+1)^3=\left(\frac{(k+1)(k+2)}{2} \right)^2=(1+2+3+ \cdots k+(k+1))^2\end{align*}$
::13+23+33k3+(k+1)3=((k+1)(k+2)(k+2)2)2=(1+2+2+3}k+(k+1)2)2

$\begin{align*}\therefore\end{align*}$

The symbol $\begin{align*}\therefore\end{align*}$ is one of many indicators like QED that follow a proof to tell the reader that the proof is complete.
::符号 QED是许多指标之一, 例如QED,

Example 5
::例5

Prove the following statement using induction:
::使用上岗培训证明以下陈述:

For $\begin{align*}n \ge 1, \ 1+2+3+4+ \cdots + n=\frac{n(n+1)}{2}\end{align*}$
::Forn1, 1+2+3+4n=n( n+1) 2

Base Case: $\begin{align*}1=\frac{1(1+1)}{2}=1 \cdot \frac{2}{2}=1\end{align*}$
::基号:1=1(1+1)2=122=1

Inductive Hypothesis: $\begin{align*}1+2+3+4+ \cdots +k=\frac{k(k+1)}{2}\end{align*}$
::感应假设:1+2+3+4k=k(k+1)2

Proof: Start with what you know and work to showing it true for $\begin{align*}k+1\end{align*}$ .
::证据: 以您所知道的开始, 并努力为 k+1 显示真实性。

Inductive Hypothesis: $\begin{align*}1+2+3+4+ \cdots +k=\frac{k(k+1)}{2}\end{align*}$
::感应假设:1+2+3+4k=k(k+1)2

Add $\begin{align*}k+1\end{align*}$ to both sides: $\begin{align*}1+2+3+4+ \cdots + k+(k+1)=\frac{k(k+1)}{2}+(k+1)\end{align*}$
::向两边添加 k+1 : 1+2+3+3+4@k+( k+1)=k( k+1)2+( k+1)

Find a common denominator for the right side: $\begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{k^2+k}{2}+\frac{2k+2}{2}\end{align*}$
::为右侧寻找一个共同的分母:1+2+3+3+4k+( k+1)=k2+k2+2+2k+22

Simplify the right side: $\begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{k^2+3k+2}{2}\end{align*}$
::简化右侧: 1+2+3+3+4 @k+( k+1)=k2+3k+22

Factor the numerator of the right side: $\begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{(k+1)(k+2)}{2}\end{align*}$
::乘以右侧的分子数:1+2+3+3+4k+(k+1)=(k+1)(k+2)2

Rewrite the right side: $\begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{(k+1)((k+1)+1)}{2}\end{align*}$
::重写右侧: 1+2+3+3+4}k+( k+1) = (k+1) (k+1) ((k+1)+1) 2

$\begin{align*}\therefore\end{align*}$

Summary

Induction is a method for proving mathematical statements about numbers. There are three steps:
::上岗是证明数字数学语句的一种方法。有三个步骤:

The base case shows the statement is true for a specific number, usually a small number like 1.
::基例显示对特定数字的语句是真实的,通常数字小于1。

The inductive hypothesis assumes the statement is true for some random number $\begin{align*}k.\end{align*}$
::推理假设假设,对于某些随机数字k来说,声明是真实的。

The inductive step/proof shows that if the statement is true for $\begin{align*}k,\end{align*}$ it must also be true for $\begin{align*}k+1,\end{align*}$ proving the statement for all numbers greater than or equal to the base case.
::感应步骤/证据表明,如果 k 的语句是真实的,K+1 也必须是真实的,证明所有数字的语句大于或等于基数。

Review
::回顾

For each of the following statements: a) show the base case is true; b) state the inductive hypothesis; c) state what you are trying to prove in the inductive step/proof. Do not prove yet.
::对于下列每一陈述a) 显示基本案例是真实的;(b) 说明感应假设;(c) 说明你试图在感应阶梯/抗体中证明什么。请不要证明。

1. For $\begin{align*}n \ge 5, \ 4n < 2^n\end{align*}$ .
::1. n5, 4n < 2n.

2. For $\begin{align*}n \ge 1, \ 8^n-3^n\end{align*}$ is divisible by 5.
::2. n1, 8n-3n 可除以 5 。

3. For $\begin{align*}n \ge 1, \ 7^n-1\end{align*}$ is divisible by 6.
::3. n1, 7n-1可除以6。

4. For $\begin{align*}n \ge 2, \ n^2 \ge 2n\end{align*}$ .
::4. 注2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2

5. For $\begin{align*}n \ge 1, \ 4^n+5\end{align*}$ is divisible by 3.
::5. n1, 4n+5可除以3。

6. For $\begin{align*}n \ge 1, \ 0^2+1^2+ \cdots + n^2=\frac{n(n+1)(2n+1)}{6}\end{align*}$
::6. n1,02+12n2=n(n+1)(2n+1)6

Now, prove each of the following statements. Use your answers to problems 1-6 to help you get started.
::现在, 请证明以下的每个语句。使用您对问题 1 - 6 的回答来帮助您启动。

7. For $\begin{align*}n \ge 5, \ 4n <2^n\end{align*}$ .
::7. n5, 4n < 2n.

8. For $\begin{align*}n \ge 1, \ 8^n-3^n\end{align*}$ is divisible by 5.
::8. n1、8n-3n可除以5。

9. For $\begin{align*}n \ge 1, \ 7^n-1\end{align*}$ is divisible by 6.
::9. n1, 7n-1可除以6。

10. For $\begin{align*}n \ge 2, \ n^2 \ge 2n\end{align*}$ .
::10. n% 2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2,n2

11. For $\begin{align*}n \ge 1, \ 4^n+5\end{align*}$ is divisible by 3.
::11. n1, 4n+5可除以3。

12. For $\begin{align*}n \ge 1, \ 0^2+1^2+ \cdots +n^2=\frac{n(n+1)(2n+1)}{6}\end{align*}$
::12. n1,02+12n2=n(n+1)(2n+1)6

13. You should believe that the following statement is clearly false. What happens when you try to prove it true by induction?
::13. 您应该相信以下声明显然是虚假的:如果您试图通过上岗培训来证明其属实,会发生什么情况?

For $\begin{align*}n \ge 2, \ n^2 < n\end{align*}$
::n2, n2 <n

14. Explain why the base case is necessary for proving by induction.
::14. 解释为什么通过上岗培训证明基本情况是必要的。

15. The principles of inductive proof can be used for other proofs besides proofs about numbers. Can you prove the following statement from geometry using induction?
::15. 除了关于数字的证明之外,还可用于其他证据,可以使用感应证据的原则,你能证明以下几何学使用感应的描述吗?

The sum of the interior angles of any $\begin{align*}n-gon\end{align*}$ is $\begin{align*}180(n-2)\end{align*}$ for $\begin{align*}n \ge 3\end{align*}$ .
::任何 n-gon 的内角总和为 n- 3 的180(n-2) 。

Review (Answers)
::回顾(答复)

Click to see the answer key or go to the Table of Contents and click on the Answer Key under the 'Other Versions' option.
::单击可查看答题键, 或转到目录中, 单击“ 其他版本” 选项下的答题键。

章节大纲

常规

上岗证明

Proof by Induction ::上岗证明

Examples ::实例

Example 1 ::例1

Example 2 ::例2

Example 3 ::例3

Example 4 ::例4

Example 5 ::例5

Review ::回顾

Review (Answers) ::回顾(答复)