4.01b - Harder proofs by induction

You already know

An induction proof needs a base case and the implication from an arbitrary $k$ to $k+1$. For derivatives, $f^{(n)}(x)$ means the derivative of order $n$, not a power. The product and chain rules, and $\dfrac{d}{dx}e^{ax} = ae^{ax}$, are assumed A-level Mathematics results.

Conjecture

A conjecture is a statement suggested by evidence or a pattern that has not yet been proved. For example, the table suggests $f^{(n)}(x) = \bigl(x^2 + 2nx + n(n-1)\bigr)e^x$. Checking a fifth derivative would give another test, not a proof for all $n$.

Key idea

A conjecture predicts the form of the answer. The inductive step must establish that form from the assumed previous case.

You already know

$\displaystyle\sum_{r=1}^{n} a_r$ means $a_1 + a_2 + \cdots + a_n$. The index $r$ runs through the terms, whereas $n$ is the upper limit. In particular, the term added when the limit changes from $k$ to $k+1$ is $a_{k+1}$.

The next partial sum

For a sequence $a_r$ and positive integer $k$, if $S_k = \displaystyle\sum_{r=1}^{k} a_r$, then

This follows from the meaning of a finite sum.
Not in the formula booklet: learn it.

Worked example 1: proving a conjectured sum

Question. Prove by induction that, for every positive integer $n$,

Plan. Check the one-term sum, assume the $k$-term formula and add the term with $r = k+1$.

Assume $\displaystyle\sum_{r=1}^{k}\dfrac{1}{r(r+1)} = \dfrac{k}{k+1}$, where $k \ge 1$. Then

Why this step? The new term has denominator $(k+1)(k+2)$, so using that denominator makes the numerator factor into exactly what the next formula needs.

Answer. This is the required formula for $n = k+1$. Truth for $k$ implies truth for $k+1$; the base case $n = 1$ is true, so the result holds for all positive integers, by induction.

Check. At $n = 3$, $\dfrac12 + \dfrac16 + \dfrac1{12} = \dfrac34$.

Worked example 2: shifted denominator factors

Question. Prove by induction that, for every positive integer $n$,

Plan. Verify the first term, then add the term whose denominator is $(k+2)(k+3)$ to the assumed sum.

Assume the result for $n = k$, where $k \ge 1$. Then

Why this step? The added term is obtained by substituting $r = k+1$ into the summand, not by copying the formula for the whole sum.

Answer. Truth for $n = k$ implies truth for $n = k+1$. The result is true for $n = 1$, so it holds for all positive integers, by induction.

Check. At $n = 3$, $\dfrac16 + \dfrac1{12} + \dfrac1{20} = \dfrac3{10} = \dfrac{3}{2(5)}$.

Watch out

Wrong: $S_{k+1} = S_k + \dfrac{1}{k(k+1)}$ in worked example 1. That term is already included in $S_k$. Right: add $\dfrac{1}{(k+1)(k+2)}$, the term with index $k+1$.

Worked example 3: a linear factor times an exponential

Question. For $g(x) = xe^x$, prove by induction that $g^{(n)}(x) = (x+n)e^x$ for all integers $n \ge 0$, where $g^{(0)} = g$.

Plan. Check the undifferentiated function, then apply the product rule to the assumed derivative of order $k$.

Assume $g^{(k)}(x) = (x+k)e^x$ for an arbitrary integer $k \ge 0$, for every real $x$. Then

Why this step? The derivative of $x+k$ is $1$, so the product rule increases the constant in the bracket by exactly one.

Answer. This is the formula for $n = k+1$. Truth for $k$ implies truth for $k+1$; since the formula is true for $n = 0$, it holds for every integer $n \ge 0$, by induction.

Check. Direct differentiation gives $g''(x) = (x+2)e^x$, matching $n = 2$.

Worked example 4: proving the opening conjecture

Question. For $f(x) = x^2e^x$, prove that

for all integers $n \ge 0$, where $f^{(0)} = f$.

Plan. Start at $0$, differentiate the assumed formula and regroup its coefficients into the form with $n = k+1$.

Assume $f^{(k)}(x) = \bigl(x^2 + 2kx + k(k-1)\bigr)e^x$ for an integer $k \ge 0$, for every real $x$. Then

Why this step? The constant required in the next case is $(k+1)((k+1)-1) = (k+1)k$. Seeing that $k(k-1)+2k$ equals this completes the step.

Answer. Truth for $n = k$ implies truth for $n = k+1$. The formula is true for $n = 0$, so it holds for all integers $n \ge 0$, by induction.

Check. At $n = 4$, the formula gives $(x^2 + 8x + 12)e^x$, matching the table. At $x = 0$, it gives $f^{(n)}(0) = n(n-1)$.

Watch out

Wrong: $\dfrac{d}{dx}(2kx) = 2x$. The derivative variable is $x$, and $k$ is a fixed integer during the step. Right: $\dfrac{d}{dx}(2kx) = 2k$. Also, changing $n$ to $k+1$ means replacing every occurrence of $n$, including factorials and exponents.

Worked example 5: a cubic target

Question. Prove by induction that $3^n > n^3$ for all integers $n \ge 4$.

Plan. Verify $n = 4$, then bound the ratio $(k+1)^3/k^3$ to bridge the gap from the assumed case to the next target.

Assume $3^k > k^3$, where $k \ge 4$. Since $k > 0$,

Hence

Why this step? The assumption alone gives $3k^3$. The ratio bound proves that this intermediate value is already larger than the next target.

Answer. Truth for $n = k$ implies truth for $n = k+1$. The result is true for $n = 4$, so it holds for all integers $n \ge 4$, by induction.

Check. At $n = 3$, $3^3 = 3^3$, so strict inequality cannot start there. At $n = 5$, $243 > 125$.

Worked example 6: a fourth-power target

Question. Prove by induction that $4^n > n^4$ for all integers $n \ge 5$.

Plan. Start at $5$ and show that the polynomial's step factor is smaller than the exponential's factor $4$.

Assume $4^k > k^4$, where $k \ge 5$. Then

Therefore

Why this step? Bounding $1 + 1/k$ by its largest possible value on the domain proves the needed comparison for every $k$, not just one trial value.

Answer. Truth for $n = k$ implies truth for $n = k+1$. Since the result is true for $n = 5$, it holds for every integer $n \ge 5$, by induction.

Check. At $n = 4$, both sides equal $256$. At $n = 6$, $4096 > 1296$.

Watch out

Wrong: $3^{k+1} > 3k^3$, “therefore $3^{k+1} > (k+1)^3$”. The comparison between $3k^3$ and $(k+1)^3$ is missing. Right: establish $\left(1+1/k\right)^3 < 3$ on the stated domain before joining the inequalities.

Worked example 7: a fixed positive increment

Question. Prove by induction that $\left(\dfrac32\right)^n \ge 1 + \dfrac n2$ for all positive integers $n$.

Plan. Verify $n = 1$, multiply the assumed bound by $3/2$, then separate the next target from a non-negative remainder.

Assume $\left(\dfrac32\right)^k \ge 1 + \dfrac k2$ for an integer $k \ge 1$. Then

Why this step? The extra term $k/4$ is non-negative, so the product bound is at least as large as the next target.

Answer. Truth for $n = k$ implies truth for $n = k+1$. The result is true for $n = 1$, so it holds for all positive integers, by induction.

Check. At $n = 2$, $9/4 \ge 2$; the difference is $1/4$, matching the remainder when $k = 1$.

Bernoulli's inequality

For every real $x > -1$ and every positive integer $n$,

Equality holds when $n = 1$ or $x = 0$; for $n > 1$ and $x \ne 0$, the inequality is strict.
Not in the formula booklet: learn it.

Worked example 8: positive and negative increments

Question. Prove Bernoulli's inequality for real $x > -1$ and positive integers $n$.

Plan. Fix any permitted $x$, use the positive multiplier $1+x$, and show that the extra term $kx^2$ is non-negative.

Assume $(1+x)^k \ge 1+kx$ for an integer $k \ge 1$, with this same fixed $x > -1$. Then

Why this step? Even if $x$ is negative, its square is non-negative and the multiplier $1+x$ is positive. Both inequality directions are therefore justified on the whole stated domain.

Answer. For this fixed permitted $x$, truth for $n = k$ implies truth for $n = k+1$. The result is true for $n = 1$, so it holds for all positive integers $n$. Since $x > -1$ was arbitrary, it holds for every real $x$ in that range.

Check. For $x = -1/2$ and $n = 2$, the comparison is $1/4 \ge 0$, which is true. If $x = 0$, every step is equality. If $x \ne 0$ and $k \ge 1$, the remainder $kx^2$ is positive, establishing the stated strictness for $n > 1$.

Watch out

Wrong: “If $x < 0$, reverse the inequality when multiplying by $1+x$.” The multiplier is $1+x$, not $x$. Right: for $-1 < x < 0$, $1+x > 0$, so the direction stays the same. Nor may you discard $kx^2$ by calling it zero: it is non-negative.