10. Induction and binomial tools for calculus

Let $P(n)$ be a statement about integers $n\ge n_0$, where $n_0$ is fixed. The principle of mathematical induction says:

1. Prove the base case $P(n_0)$.
2. For an arbitrary integer $k\ge n_0$, assume $P(k)$ and prove $P(k+1)$.
3. Conclude that $P(n)$ holds for every integer $n\ge n_0$.

The assumption in step 2 is the induction hypothesis. It is conditional, not an assumption that the final theorem is already true. The base starts the chain, and the implication extends any valid link to the next.

Here is a justification using the least-element property of the nonnegative integers. If a counterexample existed, there would be a least counterexample $m\ge n_0$. It could not be $n_0$ because of the base case. Then $m-1\ge n_0$ would not be a counterexample, and the induction step would force $P(m)$, a contradiction.

For an arbitrary integer starting index $n_0$, applying the least-element property to the shifted indices $m-n_0\ge0$ justifies the preceding least-counterexample step.

Conversely, ordinary induction on the positive integers implies the least-element property. Suppose a nonempty set $S\subseteq\{1,2,3,\ldots\}$ has no least element. Let $P(n)$ assert that none of $1,\ldots,n$ belongs to $S$. If $1\in S$ it is the least element, so $P(1)$ holds. If $P(k)$ holds but $k+1\in S$, then $k+1$ is the least element of $S$, a contradiction. Thus $P(k)\Rightarrow P(k+1)$. Induction gives $P(n)$ for every positive integer $n$, so $S$ is empty, contradicting its assumed nonemptiness. Hence every nonempty set of positive integers has a least element. Translating indices by $n\mapsto n-n_0+1$ gives the corresponding induction version for any integer starting index $n_0$.

Learning goals and role in calculus

Prove finite formulas by induction, compute binomial coefficients, and distinguish a finite identity from an infinite expansion.

Binomial coefficients and the finite theorem

For integers $n\ge0$ and $0\le k\le n$, define

$$\binom nk=\frac{n!}{k!(n-k)!},\qquad 0!=1.$$

It counts $k$-element selections from $n$ distinct objects: there are $n(n-1)\cdots(n-k+1)$ ordered selections, and each unordered selection occurs in $k!$ orders. In particular $\binom n0=\binom nn=1$ and $\binom nk=\binom n{n-k}$.

Pascal's identity, for $1\le k\le n$, is

$$\binom n{k-1}+\binom nk=\binom{n+1}k.$$

To see it without factorial manipulation, distinguish one object among $n+1$. A $k$-element selection either contains it, in which case the other $k-1$ come from $n$, or does not, in which case all $k$ come from $n$. The two alternatives are disjoint and exhaustive. Equivalently, put the two factorial fractions over the common denominator $k!(n+1-k)!$; the numerator factors sum to $k+(n+1-k)=n+1$.

For a nonnegative integer $n$ and real $a,b$,

$$(a+b)^n=\sum_{k=0}^{n}\binom nk a^{n-k}b^k.$$

Here powers of exponent zero in this polynomial identity represent the constant factor $1$, including at $a=0$ or $b=0$. This is a convention for evaluation of a polynomial, not a claim that every limiting expression $0^0$ has a prescribed value.

Induction proof. At $n=0$ both sides are $1$. Assume the formula for $n$. Multiply it by $a+b$. One part contributes $\binom nk a^{n+1-k}b^k$; the other contributes $\binom n{k-1}a^{n+1-k}b^k$ after shifting the index. Interior terms combine using Pascal's identity, while the two endpoint terms remain $a^{n+1}$ and $b^{n+1}$. The resulting sum is exactly the formula for $n+1$.

For integers $n\ge1$, $n!=1\cdots n$; for integer $k$ outside $0\le k\le n$, set $\binom nk=0$.

For fixed integer $n\ge2$, this gives $(1+h)^n=1+nh+O(h^2)$ as $h\to0$. Indeed the finite remainder divided by $h^2$ is a polynomial in $h$, bounded near zero. This finite argument proves the derivative of $x^n$ by expanding $(x+h)^n$ at fixed $x$. It does not establish a binomial series for a noninteger power or justify an infinite remainder limit.

Bernoulli inequality

For real $t\ge-1$ and an integer $n\ge1$, Bernoulli's inequality is

$$(1+t)^n\ge1+nt.$$

At $n=1$, equality is immediate. In the step from $k\ge1$, multiplication by $1+t\ge0$ preserves the assumed inequality:

$$(1+t)^{k+1}\ge(1+kt)(1+t) =1+(k+1)t+kt^2\ge1+(k+1)t.$$

The nonnegative remainder proves the next case. The multiplier condition is indispensable; multiplying an inequality by a negative number would reverse its direction. For $t>0$ and $n\ge2$, the inequality is strict because the $k=1$ step already adds a positive $t^2$.

Worked examples

An exact remainder bound. Expanding gives $(1+h)^4=1+4h+6h^2+4h^3+h^4$. For $|h|\le1/10$, the error after $1+4h$ has absolute value at most $(6+0.4+0.01)h^2=6.41h^2$. This is an explicit local bound, not merely a claim that the error is “small.”

A sum formula used in Riemann sums. Prove $\sum_{k=1}^n k^2=n(n+1)(2n+1)/6$. It holds for $n=1$. Adding $(n+1)^2$ to the formula at $n$ gives $(n+1)[n(2n+1)+6(n+1)]/6=(n+1)(n+2)(2n+3)/6$, the next case. Substitution into $n^{-1}\sum(k/n)^2$ then gives a limit of $1/3$, matching $\int_0^1x^2\,dx$.

Graded practice

1. Foundation. Find the coefficient of $h^3$ in $(2+h)^5$.
2. Core. Prove by induction that $\sum_{k=1}^n(2k-1)=n^2$.
3. Core. Use Bernoulli's inequality to show $(1+1/n)^n\ge2$ for $n\ge1$. Does this prove convergence of the sequence?
4. Proof. For fixed $x\in\mathbb R$, use a finite binomial expansion to prove $\lim_{h\to0}[(x+h)^3-x^3]/h=3x^2$.

Full solutions

1. Choose three copies of $h$ and two copies of $2$, giving $\binom53 2^2=40$.
2. The first case is $1=1$. Assuming the formula at $n$, adding $2n+1$ gives $n^2+2n+1=(n+1)^2$. Induction proves all cases.
3. Set $x=1/n$ and exponent $n$. The lower bound is $1+n(1/n)=2$. A lower bound alone does not imply convergence; one would need further information such as monotonicity and an upper bound.
4. The numerator equals $3x^2h+3xh^2+h^3$. For $h\ne0$, dividing gives $3x^2+3xh+h^2$, whose limit is $3x^2$. This also covers $x=0$ without division by $x$.

Summary and term definitions

Induction links a proved base to every successive integer case. A binomial coefficient counts coefficient contributions in a finite expansion. The notation $O(h^2)$ means the magnitude is at most a fixed constant times $|h|^2$ for sufficiently small $|h|$. Finite identities support derivatives and Riemann-sum calculations, but infinite expansions require separate convergence and remainder theorems.