# 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

`$0! = 1$`

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.

`$k! = k x (k - 1) x (k - 2) x ... x 1$`

Inductive Step: Let n = k + 1.

```
$(k + 1)! = (k + 1) x k x (k - 1) x (k - 2) x ... x 1
(k + 1)! = (k + 1) x k! From the *Induction Hypothesis*$
```

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.