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.
Base Case
The base case verifies the problem or statement through a specific initial value or values. (n = 0, n = 1)
Induction Hypothesis
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.)
Inductive Step
The inductive step proves the statement holds based on the inductive hypothesis.
Example
Prove by induction that 2^n > 2n
Base case:
When n = 3 then 2^3 > 2 x 3
8 > 6 TRUE
Induction Hypothesis:
Assume the P(k) is correct for some positive integer k.
2^k > 2k.
Induction Step:
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.
Example
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)
Recursion:
Basis: If n is equal to 0, then return 1
factorial(0) = 1
Induction:
Base case: n! when n = 0
Recursion:
factorial(n) = n * (n - 1) * (n - 2) * ... * 1
Induction:
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.
All contributors
- Anonymous contributorAnonymous contributor1 total contribution
- Anonymous contributor
Looking to contribute?
- Learn more about how to get involved.
- Edit this page on GitHub to fix an error or make an improvement.
- Submit feedback to let us know how we can improve Docs.