Applications of Mathematical Induction

We can apply the process of mathematical induction to formally prove general results from other mathematical topics such as calculus and probability.

For example, we can:

• Prove differential and integral calculus results
• Prove combinatoric and probability theorems
• Prove geometric results

In these proofs, we will see that proof by inductiion provides the framework for our proof, but there is often considerable work to be done to prove the foundational results. The power of the inductive proof is the ability to generalise the results to a wider scope of situations than the foundational results can handle.

Applying mathetical induction to prove differential calculus results

We can use mathmatical induction to generalise certain results in calculus. For example, we have been using the result

$\frac{d}{dx}\left(x^n\right) = nx^{n-1}, \quad n \in \N$

but we have not formally proven that this result holds. However, we can use mathematical induction to achieve this and applying the first principles for differential calculus. The first definition we will use is that of a derivative, which is

$\frac{d}{dx}\left(f(x)\right) = \lim_{h\rightarrow0}\frac{f(x+h) - f(x)}h$

We will also use the result of the product rule, which is that

$$\begin{aligned} \frac{d}{dx}\left(f(x)g(x)\right) &= \lim_{h\rightarrow0}\frac{f(x+h)g(x+h) - f(x)g(x)}h \\ \frac{d}{dx}\left(f(x)g(x)\right) &= \lim_{h\rightarrow0}\frac{f(x+h)g(x+h) - f(x+h)g(x) + f(x+h)g(x) - f(x)g(x)}h \\ \frac{d}{dx}\left(f(x)g(x)\right) &= \lim_{h\rightarrow0}\left(\frac{f(x+h)g(x+h) - f(x+h)g(x)}h + \frac{f(x+h)g(x) - f(x)g(x)}h\right) \\ \frac{d}{dx}\left(f(x)g(x)\right) &= \lim_{h\rightarrow0}\left(f(x+h)\frac{g(x+h) - g(x)}h + g(x)\frac{f(x+h) - f(x)}h\right) \\ \frac{d}{dx}\left(f(x)g(x)\right) &= \lim_{h\rightarrow0}\left(f(x+h)\frac{g(x+h) - g(x)}h\right) + \lim_{h\rightarrow0}\left(g(x)\frac{f(x+h) - f(x)}h\right) \\ \frac{d}{dx}\left(f(x)g(x)\right) &= \lim_{h\rightarrow0}\left(f(x+h)\right)\lim_{h\rightarrow0}\left(\frac{g(x+h) - g(x)}h\right) + g(x)\lim_{h\rightarrow0}\left(\frac{f(x+h) - f(x)}h\right) \\ \frac{d}{dx}\left(f(x)g(x)\right) &= f(x)\lim_{h\rightarrow0}\left(\frac{g(x+h) - g(x)}h\right) + g(x)\lim_{h\rightarrow0}\left(\frac{f(x+h) - f(x)}h\right) \\ \frac{d}{dx}\left(f(x)g(x)\right) &= f(x)\frac{d}{dx}\left(g(x)\right) + g(x)\frac{d}{dx}\left(f(x)\right) \\ \end{aligned}$$

The base case, $n = 1$

Consider the case when $n = 1$, in this case we have $f(x) = x$, and we can then see that

$$\begin{aligned} \frac{d}{dx}\left(f(x)\right) &= \lim_{h\rightarrow0}\frac{f(x+h) - f(x)}h \\ \frac{d}{dx}\left(x^1\right) &= \lim_{h\rightarrow0}\frac{x+h - x}h \\ \frac{d}{dx}\left(x^1\right) &= \lim_{h\rightarrow0}\frac{h}h \\ \frac{d}{dx}\left(x^1\right) &= \lim_{h\rightarrow0}1 \\ \frac{d}{dx}\left(x^1\right) &= 1 \\ \end{aligned}$$

So we see that for $n = 1$, the base case is satisfied.

The inductive step

To prove the inductive step, we establish our inductive hypothesis for $n = k$, which is that

$\frac{d}{dx}\left(x^k\right) = kx^{k-1}$

We now want to show that

$\frac{d}{dx}\left(x^{k+1}\right) = (k+1)x^k$

To do this, we calculate the derivative of $x^{k+1}$ and apply the product rule

$$\begin{aligned} \frac{d}{dx}\left(x^{k+1}\right) &= \frac{d}{dx}\left(x^k \cdot x^1\right) \\ \frac{d}{dx}\left(x^{k+1}\right) &= x^1\cdot\frac{d}{dx}\left(x^k\right) + x^k\cdot\frac{d}{dx}\left(x^1\right) \\ \frac{d}{dx}\left(x^{k+1}\right) &= x^1\cdot\frac{d}{dx}\left(x^k\right) + x^k\cdot1 \\ \end{aligned}$$

We can then apply our inductive hypothesis to get

$$\begin{aligned} \frac{d}{dx}\left(x^{k+1}\right) &= x^1\cdot\frac{d}{dx}\left(x^k\right) + x^k\cdot1 \\ \frac{d}{dx}\left(x^{k+1}\right) &= x^1\cdot kx^{k-1} + x^k\cdot1 \\ \frac{d}{dx}\left(x^{k+1}\right) &= kx^k + x^k \\ \frac{d}{dx}\left(x^{k+1}\right) &= (k + 1)x^k \\ \end{aligned}$$

This is the result we were trying to prove, and so we can then apply inductive reasoning that the relationship

$\frac{d}{dx}\left(x^n\right) = nx^{n-1}$

does indeed apply for all $n \in \N$.

...

Log in or sign up to see more