Enter your search terms Submit search form
	Web www.lcwangpress.com

Mathematical Induction

1. In [Pet, p.58, l.11-l.-4], only after applying the whole procedure concerning the Vandermonde determinant, may we reach the desired contradiction in retrospect. By using mathematical induction [Pon, p.279, l.1-l.10], we may straighten the argument and discern the key idea between inductive steps.
   
   
2. (Inductive step)
       It is simple to define the exterior derivative of a form when the form is directly expressed in terms of basis elements [Spi, vol.1, p.286, l.5]. One may guess that the inductive step would be equally simple. However, it turns out to be quite challenging to express d in terms of [Spi, vol.1, p.289, l.-6-l.-4].
   
   
3. Evaluating a construction's effectiveness by mathematical induction (Urysohn's lemma).
   1. If we study separation axioms [Dug, chap.VII] without a geometric picture in mind, the discussion of a topological method's effectiveness could become messy. The abstract "there exist" in [Dug, p.137, Definition 1.1; p.141, Definition 2.1 & p.144, Definition 3.1] must be interpreted as "use geometric methods to find some". For Urysohn's lemma, the geometric picture in [Spi, vol.1, p.44, Lemma 2] is simple and clear. Spivak does not use mathematical induction. [War, p.11, Corollary] uses mathematical induction very awkwardly because Warner uses partitions of unity.
   2. The methods in [Dug, p.146, Theorem 4.1] and [Ru2, p.40, Lemma 2.12] are similar. Though Rudin shows the method’s flexibility, he fails to pinpoint an optimal choice. Actually, Rudin loses the control of effectiveness from the beginning. The order of r₃, r₄, r₅, ..... in [Ru2, p.40, l.-9] can be random, so we cannot predict r_i or r_j [Ru2, p.40, l.-4-l.-3] in advance. Dugundji considers a much smaller set {k/2^m}. His construction of U(k/2^m) is more definite, specific and effective. Dugundji also avoids the constant and unpredictable comparisons in [Ru2, p.40, l.-4-l.-3]. An effective construction by mathematical induction must make every step as definite as possible.
          In [Ru2, p.40, l.-9], Rudin has to complete the whole procedure of mathematical induction to define r₃, r₄, r₅, ...... Otherwise, we are not certain that the sequence {r₁, r₂, r₃, .....} includes all the rational numbers. Dugundji's method is better because he defines k/2^m and U(k/2^m) in a single inductive step. Thus to obtain U(r_n), Rudin uses math induction twice, while Dugundji only once.
          Instead of completing two mathematical inductions separately, we would like to combine separate arguments in a single inductive step. In other words, we would like to use math induction once for all.
   
   
4. To find a natural unit of argument (Urysohn's Lemma).
       The argument in [Dug, p.147, l.10-l.26] uses induction twice (First on m [ À₀-induction], then on k [finite induction]) to find a natural unit of the argument. [Po3, p.67, l.24-p.68, l.21] is quite redundant simply because Pontryagin uses induction only once.
   
   
5. Many people believe that the method of infinite descent is only good for reduction to absurdity. However, a downward induction can be completely constructive (see [Karl, 21, Theorem 12], [Baz, p.58, Theorem 2.6.5] and [Wan3, p.133, II, (1), (2)].
   
   
6. Initiating device.
       The induction on a finite ordered structure [Po3, p.473, l.-9] uses primitive elements as the initiating device.
   
   
7. Finite induction provides a pace indicator which measures the progress toward a goal. Suppose a loop from beginning to end requires five iterations. After each iteration, we know one fifth of our job has been done [Karl, p.111, l.8-l.13].
   
   
8. Suppose that a theorem can be proved by two methods: one that uses mathematical induction and one that does not. After comparing these two methods, we find that the method of mathematical induction automatically organizes the structure of the argument, and that the key idea of the proof is further simplified and more precisely located by the induction process itself.
   Example 1. In [Jack, p.98, l.-5], Jackson offers two options to calculate the integral given in [Jack, p.98, l.-6]. The brute force method can be found in [Guo, p.221, l.7-l.10]. It involves a very complicated function, the Gamma function. In contrast, the induction method gives a simpler and more structured relation [Jack, p.99, (3.20)].
   Example 2. The proof given in [Guo, p.236, l.-9-p.237, l.8] does not use mathematical induction. Therefore, if there is a mistake in the proof, it is necessary to conduct an exhausted search to find it. Since each step shares about the same weight, it is difficult to judge where the emphasis should be placed. In contrast, the proof given in [Chou, p.604, l.8-p.605, l.-3] is more organized simply because it uses mathematical induction. If we make an incorrect calculation somewhere in the proof, the first place we want to check is the induction step (e.g., justifying the details of [Chou, p.605, l.8-l.9]) because the rest of the proof [Chou, p.605, l.-7-l.-2] is routine.
   
   
9. The proof of [Mun00, p.434, Theorem 71.1] uses mathematical induction. The proof of the induction step [(n-1)®n] is similar to the proof of the step [1®2] [Mun00, p.434, l.16]. The proof of [Ru1, p.34, Theorem 2.40] does not use mathematical induction, so the argument involves n copies of I (see [Ru1, p.34, Theorem 2.39]). In contrast, the proof of [Mun00, Theorem 26.7] uses mathematical induction. All we need do is prove that the product of two compact spaces is compact. Thus, mathematical induction enables us to advance our argument more easily because two factors is less burdensome than n factors.
   
   

10. How we apply the axiom of mathematical induction to a proof
        The axiom of mathematical induction contains two parts: (1). Starting from number one, we can construct a chain of successors; (2). The collection of constructed successors contain all the natural numbers except for 1. The second statement is warranted by the conclusion of the axiom of mathematical induction [Lan8, p.2, l.-1]. [Lan8, p.3, Theorem 3] only asks us to prove (2). We need not consider (1), the construction part. However, in [Lan8, p.3 l.-6-p.4, l.9] Landau creates a virtual chain using the fact that AÞB is equivalent to [(not A) or B]. This approach allows him to apply the entire package of the mechanism to the proof. When someone asks what your name is, it is unnecessary to say who your great grandfather is.¬

11. We should use the axiom of mathematical induction as infrequently as possible.
        The proof of [Lan8, p.67, Theorem 162] uses the well-ordering principle [Lan8, p.67, l.19], an equivalent to the axiom of mathematical induction. In contrast, the proof given in [Ru1, p.2, l.7-l.19] does not use the axiom of mathematical induction. In addition, [Lan8, p.67, Theorem 162] is essentially a problem concerning unique factorization. If we directly use the unique factorization theorem as the target for contradiction, we will reach the contradiction quickly [Ru1, p.2, l.7-l.19]. If we use the well-ordering principle, a concept more distantly related to our theorem, as our target for contradiction, the argument will become unnecessarily long [Lan8, p.67, l.14-p.68, l.11].
    
    
12. Wise application of mathematical induction may help us avoid complications, make proofs more constructive, effective, and meaningful. Only simple tasks and a minimum amount of work should be performed within an inductive step. The rule of thumb is that in a proof we should take everything out of an inductive step if possible. Thus, mathematical induction should be applied to only the inevitable part of a proof.
        In computer programs mathematical induction involves recursion. In order to save the cost of memory and operations, we should perform only simple tasks and a minimum amount of work within an inductive step. Let us compare the proof of [Cod, p.6, Theorem 1.2] with that of [Har, p.10, Theorem 2.1]. First, the former provides an error estimate [Cod, p.3, theorem 1.1], while the latter fails to do. Second, [Cod, p.4, Fig. 1] uses finite induction to construct j, while [Har, p.10, (2.10] uses finite induction on n to expand the domain [t₀, t₀+ne] of y_e. The inductive step in the former construction involves drawing a line and finding the intersection with a vertical line. They are simple tasks and can be done in a finite steps. In contrast, the inductive step in the latter construction involves integration which is an infinite process. Third, if we recall the definition of limit, we will find that we must use induction on n when we take lim _n®¥ y_n. All the natural numbers n except a finite number of them have to be taken into account. Let us consider the inductive steps involved in the above two proofs. In order to derive [Cod, p.7, (1.7)] from [Cod, p.6, (1.6)], we only need to note that |D_n(t)| £ e_n. In contrast, deriving [Har, p.9, (1.5)] from [Har, p.10, (2.1)] requires more operations:
    | f (t,y_e(n)(t-e(n))) - f (t,y(t))|
    £ K |y_e(n)(t-e(n)) - y(t)|
    £ K [|y_e(n)(t-e(n)) - y_e(n)(t)| + |y_e(n)(t) - y(t)|]
    £ K [Me(n) + |y_e(n)(t) - y(t)|].
    In view of the above considerations, Levinson's proof avoids complications and focuses on the essence of the theorem.
    Remark.

    Train	Mathematical induction
    To save cost, let a train run once instead of twice. Increase carloads.	To avoid unnecessary abuse, we should not use mathematical induction twice if the proof can be done by using it once. Let each inductive step do more work.
    In order to make the train run fast, load a minimum amount of cargo on each car.	To save the cost of memory and operations, we should perform a minimum amount of work within an inductive step.




13. Counting embedded levels of mathematical induction
    If there is no other induction embedded in the inductive step of a mathematical induction, then the step is called a 1-level inductive step and the mathematical induction is called a 1-level induction. Assume that an (n-1)-level inductive step and an (n-1)-level induction are defined. If the main inductive step of a mathematical induction is embedded with an (n-1)-level induction, then the main step is called an n-level inductive step and the original induction is called an n-level induction.
    Example 1. (The worst case for non-uniqueness)
        [Har, pp.18-23, §5] constructs an example using 4-level induction.
    First level: infinite induction on n [Har, p.18, l.17]
    Second level: infinite induction on k [Har, p.18, l.16]
    Third level: infinite induction on i [Har, p.18, (5.2)] for Case n = 0; infinite induction on j [Har, p.20, l.11] for Case n+1, where n³0
    Forth level: finite (m) induction on i [Har, p.20, (5.15)] for Case n+1, where n³0
    Remark. The two exponents n+1 given in [Har, p.21, (5.21)] should be replaced with n.
    Example 2. (Lattices)
        One may define an n-dimensional lattice using an n-level induction and define an À₀-demensional lattice using an À₀-level induction.
    Remark. The use of À₀-level induction is the most sophisticated and cumbersome application of mathematical induction.



14. Links {1, 2, 3, 4}.