Mathematical Induction for Data Science
The Proof methodology for math equations
General Introduction
Many Mathematical statements assert that a property is true for all positive integers. Examples of such statements are that for every positive integer n: n! ≤ n^n, n³ − n is divisible by 3; a set with n elements has 2^n subsets; and the sum of the first n positive integers is n(n+1)/2. A main goal of this blog is to go thorough understanding of mathematical induction have two parts.
First, they show that the statement holds for the positive integer 1. Second, they show that if the statement holds for a positive integer then it must also hold for subsequent larger integer.
Mathematical induction is predicated on the rule of inference that tells us that if P(1) and d ∀k(P (k) → P (k + 1)) are true for the domain of positive integers, then ∀nP (n) is true.
Mathematical induction are often used to prove a fantastic kind of results. Understanding the thanks to read and construct proofs by mathematical induction could also be a key goal of learning discrete mathematics.
We can define sets and functions that is way to described sets by listing their elements or by giving some property that characterises these elements. We can give formula to values of functions.
There is alternative vital thanks to define such objects, supported mathematical induction. To define functions, some initial terms are specified, and a rule is given for locating subsequent values from values already known.
Talking about, Sets are often defined by listing a number of their elements and giving rules for constructing elements from those already known to be within the set. Such definitions, called recursive definitions, are used throughout discrete mathematics and computing . Once we’ve defined a group recursively, we will use a symbol method called structural induction to prove results about this set.
When we specified procedure for solving a drag , this procedure should solve the matter correctly. Just testing to ascertain that the right result’s obtained for a group of input values doesn’t show that the procedure always works correctly.
The correctness of a procedure are often guaranteed only by proving that it always yields the right result. subsequent few blogs will contains an introduction to the techniques of program verification. There are formal technique to verify that procedures are correct.
Example, Consider that we have an infinite ladder, and we want to know whether we can reach every step on this ladder:
- We can reach the first rung of the ladder.
- If we can reach a particular rung of the ladder, then we can reach the next rung.
Can we conclude that we will reach every rung? By [1] we all know that we will reach the primary rung of the ladder. Moreover, because we will reach the primary rung, by [2] we will also reach the second rung; it is the next rung after the primary rung.
Applying [2] again, because we will reach the second rung, we will also reach the third rung. Continuing during this way, we will show that we will reach the fourth rung, the fifth rung, and so on. as an example , after 100 users of [2] we all know that we will reach the 101st rung.
we conclude that we are ready to to succeed in every rung of this infinite ladder. Something that we will reach the nth rung of the ladder.
Mathematical induction is a particularly vital proof technique to find out , it are often wont to prove assertions of this sort . Mathematical induction are often wont to prove results about the complexity of algorithms, the correctness of certain sorts of computer programs, theorems about graphs and trees, also as a good range of identities and inequalities.
This blog will describe how mathematical induction are often used and why it’s valid proof technique. It’s extremely vital information to notice down that mathematical induction are often used only to prove results obtained in another way. it’s not a tool for locating formulae or techniques.
Mathematical Induction Steps
Mathematical Induction are often wont to prove statements that assert that P(n) is true for all positive integers n, where P(n) is propositional function.
A proof by mathematical induction has two parts,
- Basis step
- Inductive step
Basis step where we show that P(1) is true, and an inductive step, where we show that for all positive integers k, if P(k) is true, then P(k+1) is true.
BASIS STEP: We verify that P(1) is true.
INDUCTIVE STEP: We show that the conditional statement P(k) → P(k+1) is true for all positive integers k.
In order to finish the inductive step of a symbol using the principle of mathematical induction, we assume that P(k) is true for an arbitrary positive integer k and show that under this assumption. P(k+1) must even be true. the idea that P(k) is true is named the inductive hypothesis.
Once we complete both steps during a proof by mathematical induction, P(n) is true for all positive integers, that ∀nP (n) is true where the quantification is over the set of positive integers. At Inductive step, we’ve written that ∀k(P (k) → P (k + 1)) is true, where again, the domain is that the set of positive integers.
This proof can be expressed as a rule of inference,
(P (1) ∧ ∀ k (P (k) → P (k + 1))) → ∀ nP (n)
When the domain is that the set of positive integers. Because mathematical induction is such an important technique, it’s worthwhile to elucidate intimately the steps of a symbol using this system . We are only assuming that P(k) is true to start out explanation. the primary thing we do to prove that P(n) is true for all positive integers n is to point out that P(n) is true.
This amounts to showing that the actual statement obtained when n is replaced by 1 in P(n) is true. Then we must show that P (k) → P (k + 1) is true for each positive integer k.
In oder to prove that this conditional statement is true for each positive integer k, we’d like to point out that P(k+1) can’t be false when P(k) is true. this will be accomplished by assuming that P(k) is true and showing that under this hypothesis P(k+1) must even be true.
Conclusion
We use mathematical induction to prove a theorem, we first start with P(1) is true. Then we all know that P(2) is true, because P(1) implies P(2). Furthermore, we all know that P(3) is true, because P(2) implies P(3). By Continuing the lines, we visualise that P(n) is true for each positive integer n.
Content text source credit:
Discrete Mathematics and its Applications — Seventh Edition By Kenneth H. Rosen [Book]
