Proof by Induction
Proof by Induction is a method of mathematical proof that establishes a base case to develop an induction hypothesis that can then be proven by induction.
The base case verifies the problem or statement through a specific initial value or values. (n = 0, n = 1)
The induction hypothesis assumes that the statement holds for some k, or range of values using k as a boundary.
- Weak Induction: Induction typically based on a specific assumption.(P(n) = P(k), or n = k)
- Strong Induction: Induction typically involving a range or global case of an assumption. (All integers less than or equal to k.)
The inductive step proves the statement holds based on the inductive hypothesis.
Prove by induction that 2^n > 2n
When n = 3 then 2^3 > 2 x 3 8 > 6 TRUE
Assume the P(k) is correct for some positive integer k. 2^k > 2k.
Since P(k) is true for all positive integers greater than 2, P(k+1) is true. 2^(k + 1) is the same as 2 x 2^k, which is clearly greater than 2 x 2k,which is equivalent to 2(1 + k) or due to the communitive property of multiplication is equivalent to 2(k + 1), for all k > 2. Or, 2^(k+1) = 2 x 2^k > 2 x 2k = 2(k + 1) for k>2 Hence by mathematical induction P(n) is true for all positive integers n > 2.
All mathematical proofs by induction consist of these three parts. Be sure to prove all necessary base cases, more than one is possible.
Note: Any proof by weak induction is also a proof by strong induction, the distinction between the two is determined by the need to prove a substantive range of assumptions.
Proof by Induction’s Application to Computer Science
A very strong relationship is present between recursion and mathematical induction. Recursion solves a problem by specifying a solution to one or more base cases and then demonstrating how to derive the solution to one or more base cases and then demonstrating how to derive the soltion to a problem of an arbitrary size from the solutions to smaller problems of the same type. Similarly, mathematical induction proves a property about the natural numbers by proving the property about a base case and then proving that the property must be true for an arbitrary natural number n if it is true for the natural numbers smaller than n.
Below is psuedocode of a function to compute a factorial, recursive steps will be done in parallel to show similarity:
factorial(n: integer): integer if (n == 0) return 1 else n = n * factorial(n - 1)
Basis: If n is equal to 0, then return 1
factorial(0) = 1
Base case: n! when n = 0
factorial(n) = n * (n - 1) * (n - 2) * ... * 1
Inductive Hypothesis: Assume that this property holds true for n = k. For all k > 0.
Inductive Step: Let n = k + 1.
Thus, the property is true due to the definition of factorials.
Note: Typically, the problem will be to solve an expression or inequality.
- Anonymous contributorAnonymous contributor1 total contribution
- Anonymous contributor