Proof by Mathematical Induction

Abstract – On this paper we deal with the concept of proof by mathematical induction. Mathematical induction is one of the most powerful tools for proving statements in discrete mathematics. Notwithstanding, it is studied only by students that learn the highest level of mathematics at school, even then it is taught in the most shallow way. Like in many subjects of mathematics, the student is being taught how to use the technique to prove simple propositions of certain form, without any theoretical basis to understand the validity of it. We feel that one way to achieve a better understanding of the induction can be obtained by exposing the students to a greater variety of propositions. For that matter we end this paper with some examples of varies statements proved using mathematical induction.

Furthermore, it is rather odd that the concept of complete mathematical induction, which will be discussed further in this paper, and which is even a more powerful tool, is not taught at school at all.

Keywords – Induction, Misconceptions, Proof, Complete Induction, Paradox, Mathematical Induction.

I. INTRODUCTION

The method of proof by induction is taught in high schools only superficially, only with respect to very specific kinds of statements. The students learn how to prove certain kinds of identities and inequalities, as well as properties of division by natural numbers. No focus is placed on the correctness of the induction principle; there is no variety in the kind of statements treated; and there is no room for originality.

After extensive observations of novice math students,we can say that although most students successfully employ the method of proof by induction to prove statements of the kind they are accustomed to, they do not understand the correctness of the proof, see [1]. Most students learn how to use the method mechanically and since they lack an understanding of the correctness of the method, they fail in solving problems that are of a different style.

In general, no emphasis is placed in schools on the concept of proof. Even students who study mathematics at high level encounter the general concept of proof only when dealing with the topics of geometry (with respect to overlapping triangles), when dealing with trigonometric identities and proof by induction. In the framework of these three topics, students learn how to use proofs in a systematic manner, devoid of any originality. It is therefore not surprising that when asked, at a more advanced stage, to prove something, some students are simply clueless. It is no wonder that many engineering students, and even math students, stand gaping when the word 'Prove' appears at the beginning of a test question.

Often, when students are asked to prove that A causes B, they prove the opposite. Furthermore, they are not even aware that the important tool - indirect proof - even exists.The concept of proof in general is a very broad and interesting concept. In this paper, however, we will focus only on the concept of proof by induction.

Many articles deal with the differences between mathematics and other sciences and one of the links between them, seemingly, has to do with the method of proof by induction. Physical principles are proved by repeating experiments dealing with a specific phenomenon. From the point of view of the physical scientist, any phenomenon that can be obtained repeatedly can serve as proof of a law or rule, which can even be formulated as a mathematical equation. Such proof is called an inductive proof. Many students think that this concept is valid with respect to mathematics as well, and that it is applied in the induction principle. Shmuel Avital[2] calls this approach erroneous induction, while Adam Kenisberger [9] calls it empirical induction. Had this approach been accepted by mathematicians, then Goldbachs assumption, which claims that 'every natural,even number ngt;2,can be represented as the sum of two prime numbers', would have long ago become a theorem,since it has already been proved to be true for all nle;2∙10. Furthermore, Fermas theorem would not,most likely, require its very complex proof, which extends over some 250 pages, and which states that 'for any Natural ngt;3, no three natural numbers x, y ,z exist, such that x y=z'.

II. PROOF BY INDUCTION

The induction principle can be described by means of the following story:

It is well known in the country of Mathland that if a person takes an evening stroll one day, then this same person will take an evening stroll the next day as well.Tom lives in Mathland. Can we say, following the above,that Tom takes an evening stroll every day? The answer is,of course, no. We are missing one additional piece of information. We must know whether Tom took an evening stroll on any particular day before. If he did, then from that day on, he will indeed take a stroll every day. This is exactly the principle of induction.

When examining the extent of students understanding,who supposedly already knows how to use the principle of induction, the following problems are soon encountered:

1. First Problem: Misunderstanding of the Deductive Proof.

After proving the basis of the induction, we must then prove that the correctness of the statement for n 1 follows from its correctness for n . At this point, students sometimes ask: 'But how do we know that the statement is true for n ?' or 'But proving the statement for n is exactly the objective we aspired to achieve, isnt it?'.Many students think that at this stage they must prove the correctness of the st

剩余内容已隐藏，支付完成后下载完整资料

---

数学归纳法

摘要——在这篇文章中，我们主要涉及的是数学归纳法的概念。在离散数学的命题证明中，数学归纳法是最有力的证明工具之一。尽管，它只是通过研究在学校教了最浅显的学习数学水平最高的学生。像许多数学科目一样，学生被教导如何使用这一技术来证明某些形式的简单的命题，但没有任何理论基础来解释它的有效性。我们认为获得对归纳法的一个更好的理解方式是通过让学生练习更多种类的命题。对于这个问题，我们在本文的最后将用数学归纳法对一些不同的命题例子进行证明。

此外，本文将进一步讨论完整的数学归纳法的概念，甚至是一个更强大的证明工具，但是在学校却不教授，这是非常奇怪的。

关键词——归纳法，误解，证明，完整的归纳法，悖论，数学归纳法

1.介绍

在高中只是浅薄地教数学归纳法这种方法，只有涉及一些特殊类型的命题。学生们学习如何证明一致性和不等式，以及自然数的性质。但没有把焦点放在归纳法原理的正确性上，没有去解决各种类型的命题，也没有任何创意的空间。

经过广泛地观察数学初学者，我们可以说，虽然大多数学生成功的采用归纳法（他们已经习惯了的语句的证明方法）去证明，但是他们对证明的正确性不理解。大多数学生机械地学习如何使用方法去证明，缺乏对归纳法正确性的理解，如果换一种类型就不能解决了。

一般来说，学校没有把重点放在证明的概念上，甚至数学成绩很好的学生。只有当处理几何专题(对重叠的三角形),处理三角恒等式和归纳法证明时才会遇到证明的概念。在这3个专题的框架中，学生学习如何使用系统的方法去证明，但没有任何的创意。因此毫不奇怪,当被问及在更高级的阶段去证明一些东西时，一些学生表示无能为力。难怪许多工科学生，甚至是学数学的学生，当出现试着证明一个问题时，就只能傻掉了。

通常情况下，当学生们被要求证明导致时，他们一般都用反向证明。此外，他们甚至没有意识到重要的工具——间接证明，即使它是存在的。一般来说，证明的概念是一个非常广泛而有趣的概念。然而，在本文，我们将只关注归纳证明的概念。

很多文章处理数学和其他学科之间的差异和联系时,似乎与归纳证明相关。在物理学，涉及一个特定的现象时我们用重复实验来证明。从物理科学家的观点来看，任何可以获得多次的现象都可以作为定律或准则的依据，甚至可以制定成为一个数学方程。这样的证明被称为归纳证明。很多学生认为这种观念对数学也是有用的，并把它运用于归纳原则。叫这种方法是错误的归纳法，而 称之为经验归纳法。而这种方法被数学家们所接受，就如哥德巴赫的假设，他声称“每一个自然数，甚至任何大于2的数，都可以表示为两个素数的和”，在很早以前，自从它被证明是正确的，这就已经成了一个定理。此外，费马定理最可能不需要非常复杂的证明（延伸约250页）为了证明“对于任何大于3的数，不存在这样的三个自然数使得成立”。

2.归纳法证明

归纳法原理可以通过下面故事的方式来描述：

众所周知，居住在的一个人某一天在傍晚散步，然后这个人第二天又将在傍晚散步。根据以上信息，我们能不能说每天在傍晚散步？答案是当然不能。我们缺少一个额外的信息。我们必须知道从前是否在任意的每一天都在傍晚散步。如果他是这样的，那么从那天起，他确实会每天傍晚散步。这正是归纳法原理。

当检查学生对此的理解程度时，他们认为自己已经知道如何使用归纳法原理了,但很快会遇到以下问题:

A.第一个问题：对演绎证明的误解。

在证明了归纳法的第一步后，我们必须按照时的成立来证明在下命题的成立。在这一点上，有时同学会问：“但是我们怎么知道时命题是成立的呢？”或者“但是证明时，命题的成立正是我们渴望获得的，不是吗？”许多学生知道在这个阶段他们必须证明在时，命题也成立，但是不知道事实并非如此。这意味着大多数学生不知道在这个阶段证明的关键是什么。

B.第二个问题：对归纳法第一步的意义的理解不充分。

这种误解的症状有:

• 在一些不需要的情况下验证命题的成立。学生有时会验证当和当时，命题成立，但它只需要验证当时就足够了。学生这么做有许多可能的原因。学生的高中老师有可能就这么做，或者学生可能认为老师这么做。事实上，在某些情况下的确需要证明当和时，命题成立（由于增量的大小，或者是问题1的条件限制）。在任何情况下,某些学生在没有必要这样做的情况下验证两个语句的正确性,可能是缺乏对归纳法概念的理解。
• 不知道如何选择归纳法的第一步。学生们习惯于证明对于任意自然数成立的命题。当他们被要求证明一个大于等于3（或者是任意自然数）的语句时，他们在选择归纳法的第一步时就有困难了。老师告诉学生在这个特殊的例子中归纳法的第一步是什么后，学生将“输入”这样一种心理关联：每一个像这样的例子归纳法的第一步都是一致的。

C.第三个问题：增加量的误解

证明的命题是对于任意自然数时，增加量为1。然而，在其他情况下，其他增加量也是适当的。例如，如果我们希望用归纳法证明的命题是对于任何偶数或者是奇数时，此时的增加量就为2。例如，一段时间后，学生们知道用数学归纳法证明的命题对于任意偶数时，增加量必须为2。然而，碰到借以以上问题证明命题对于任意奇数时，学生仍会使用增加量为1。当面对证明的命题是对于所有能除以3的数时，学生们往往放弃。

理解归纳法原理的根本逻辑的学生可以自由地运用这一原理。例如：

• 在某些情况下，运用增加量的大小为比使用增加量为1更好。在这种情况下，命题的成立必须验证当时。
• 归纳法可用于任何集合（相似于自然数集合）。例如，负整数的集合。在这种情况下，归纳法的步骤是当时命题成立，假设时命题也成立，并由此证明时命题也成立。
• 归纳法原理也可以用于两个变量。假设我们想证明在任何自然数和下，命题是成立的。在这种情况下，我们首先要证明其中一个变量作为归纳法的第一步。这样过后，就变成证明对于任意自然数，命题成立。如果可能的话，这可以看成是关于的归纳法。最后，它必须证明对于任何自然数和，当时命题成立并且时命题也成立。
• 归纳法的例子还能用于问题中隐藏的一个变量。通常，学生习惯于把归纳法原理运用于问题中出现的变量，但是有时我们需要更大程度的创新。偶尔，必须定义一个新的变量并且归纳法原理应用于它。这种创意有点类似于一个人在几何证明学习初期被要求必须会使用辅助线。

3.归纳法中的悖论

更好的检测学生对于归纳法原理理解的差距在哪里的一种方法是呈现有错误语句的归纳证明并让学生识别证明中的错误。我们不建议这个练习被用于刚刚开始学习这个专题的学生；这可能会使学生对归纳法原理失去信心，因为信心本来就摇摇欲坠了。

我们将呈现两个著名的“悖论”,每一个都有不同的问题点。

A.悖论1

命题：对于任何给定的一群人,所有的这群人中的高度是统一的。

证明：通过对归纳证明，其中是指这群人的人数。

当时，语句显然是成立的，因为在任何群体只包含一个人时，人的高度是统一的（等于这个人的高度）。

我们假设对于任何自然数命题成立并证明时命题也成立。

把个人组成的群体叫作，我们要证明中的人的身高是统一的。让我们从中移掉一个人。结果，我们剩下一个包含个人的群体，由表示。根据归纳的假设，中的人的高度是统一的。让我们假定这个高度等于厘米。现在，让我们回到并从中移走另一个人。这个群现在剩下的人表示为。中包含个人，这个群体中的人的高度也是统一的。让我们假定这个高度为厘米。因为中的人的高度包括和，既是厘米又是厘米，由此可见。此外，这也是和的高度，因为他们要么属于要么属于。换句话说，中的人的高度是统一的。

这种证明的问题在于演绎证明。证明时命题成立的过程借以时命题的成立，但是对于任意自然数中不是有效的。在这种情况下，若,则我们从只包含两个人的群体中移走两个不同的人和，那么剩下的群体将没有人了。然而，和y的高度的统一性是基于两个群体的一部分，和是和的一部分。

学生遇到这种错误的证明通常不能识别证明中的错误并且他们试图解释错误的来源听起来都是非常有趣的。相当一部分的学生声称问题在于归纳假设并且通常听起来是这样的:“问题是假设一组人,高度统一。我们知道这是不正确的。”

B.悖论2

命题：如果和是自然数，那么。

证明：我们将证明对于任意自然数，这个命题成立.

如果，那么，命题成立。

我们假设对于任意自然数命题成立，并证明时也成立。

使和是两个自然数，。现在我们要证明。

因为，它遵循于归纳假设；因此。

事实上，这种证明的问题在于，和是自然数不会导致和也是自然数这样的结论。

因此，不能用于归纳假设。

4.完全归纳法

值得注意的是，在学校教授归纳原理，但作为一个更强大的证明命题的工具——完全归纳原理在学校却不教。许多命题可以用完全归纳法证明但不能用常规归纳法。

完全归纳原理相似于最小值原理，即在每一个非空的自然数集中都存在一个最小的数。下面的这个命题，有点幽默，但却真实，也可以用这一原则来证明。

命题：所有的自然数都是特殊的。

证明：让所有非特殊的自然数的集合叫作。我们将证明是一个空集。假设不是空集，那么根据最小值原理，中存在最小的一个数。换句话说，是最小的非特殊的数字，这是一个非常特殊的属性的矛盾。

完全归纳原理证明了如果对于任意的自然数某一命题成立遵循于对于任意小于自然数的自然数命题成立，那么对于所有自然数命题都成立。我们将通过这样一个例子来展示该原理：

命题：对于任意大于等于2的自然数，存在一个素数，是的因子。

证明：假设当时，对于任意自然数命题成立。我们将证明当时命题也成立。如果是基本的，那么我们的工作就完成了。否则，存在。根据归纳的假设，存在一个素数，是的因子。因此，也是的因子。

4.选择问题用归纳法证明

这部分提供了用归纳法证明的各种各样的例子。在.的书中可以找到一个用完整的方法解决的典型例子。

1. 问题1

给矩阵 ，证明对于任意自然数成立。

证明：当时，命题成立，因为,。

我们将假设对于任意大于等于2的自然数命题成立，并将证明n 1时命题也成立。

。故当时命题也成立。

因此，对于任意的自然数，命题成立

注解：在之前问题上归纳法的第一步要求我们也验证时的情况，因为它是为了被用于证明假设。

B.问题2

基于三角形的3个内角的角度之和为180度，证明当时，任意多边形的内部角度之和是。

证明：通过对归纳证明。

当时，这个多边形是三角形，命题成立。

我们将假设对于任意大于等于3的自然数命题都成立，并证明当时命题也成立。

在一个具有个顶点的多边形中，画对角线连接不相邻的两个顶点，只相距一个顶点。这个对角线把多边形分成两个多边形:一个是三角形,另一个是个顶点的多边形。

个顶点的多边形的内部角度之和等于两个多边形的内部角度的总和。这个总和等于这个三角形的180度加上这个个顶点的多边形的（根据归纳的假设）。换句话说，根据要求总共是。

注释：（1）完全归纳法证明了以上问题能依赖任何对角线，在任意个顶点的凸多边形中，将多边形分成两个多边形，一个多边形，一个多边形，并且。根据和的归纳假设，按照需要，我们发现一个个顶点的多边形的内部角度之和是。

（2）上述证明也适用于非凸多边形，但证明稍微有点复杂。在继续下一个问题之前，我们给出3个集合的理论符号。

符号：对于一个有限集，让表示集合里元素的数量。

符号：对于任意一个集合，让表示集合的所有子集。

符号：让Oslash;表示空集。

C.问题3

证明一个有个元素的集合的子集的个数是。

证明：当时命题成立，因为一个含有0个元素的集合必然是空集，并且空集只有一个子集，这个子集就是它自己。换句话说，根据需要|p(Oslash;)|=1=2。

我们假设对于任意大于等于0的整数命题都成立，我们将证明时命题也成立。让表示 1个元素的集合。

因为集合中的元素的个数至少为1，我们能从集合中拿走任意一元素。让表示包含的的所有子集，表示不包含的的所有子集。是显而易见的。

值得注意的是通常是集合，包含的子集和包含个元素的集合的子集相等。因此，根据归纳假设，。

此外，如果我们将元素添加到的每个集合中，这样就是集合。换句话说，。

因此，

注释：在前面的练习中我们证明了所有非负整数的命题，归纳的第一步是.

斐波那契数列是一个自然数序列,在数学中有着特殊的意义。这个序列被定义为递归的，如下： a=1

a=1

a=a a nge;3

换句话说，第一个和第二个的元素都等于1并且所有其他元素等于前面两个元素的和。因此，序列的排列是1，1，2，3，5，8，13，21.。。。。。

D.问题4

{a}是斐波那契数列。然后，对于任何自然数，证明。

证明：当和时命题成立，因为和。

假设时，和时命题成立，证明时命题也成立。

注释：在前面的问题中归纳的第一步中包含之前的两个必要的数据。

E.问题5

让我们用奇数以

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[498717]，资料为PDF文档或Word文档，PDF文档可免费转换为Word