Identities, Inequalities, and Mathematical Induction

Motivation

You need algebraic expansion, sign reasoning, basic trigonometry and Chapter 5's notation. This chapter develops the logical work behind a calculation: deciding what must be proved, recording the assumptions that permit each step, and identifying equality cases. You should learn to verify identities and simple inequalities and to prove statements about every positive integer by induction.

Testing a formula at several values can reveal a mistake. It cannot prove a universal statement. A proof must explain why every value within its stated domain is covered, including boundaries and exceptional cases.

7.1 Identity, equation, implication and equivalence

Definition

An identity on a domain is an equality true at every input in that domain. An equation to solve asks which inputs in an allowed domain make an equality true. For example,

$$(x+1)^2=x^2+2x+1$$

is an identity for all real $x$, while $(x+1)^2=9$ has only two real solutions. The equality symbol alone does not specify which task is intended.

The statement $P\implies Q$ says that $P$ guarantees $Q$. The converse need not hold. For instance $x=2\implies x^2=4$, but $x^2=4$ also permits $x=-2$. The notation $P\iff Q$ asserts both implications. In algebra, a reversible transformation establishes equivalence on the stated domain. Squaring or dividing by a possibly zero quantity may not be reversible.

To verify a rational identity, first state where both original sides are defined. A simplified expression may have a larger natural domain, but simplification does not extend the original statement automatically.

Worked example

Worked example 1: a rational identity with a hole. Verify

$$\frac{x^2-4}{x-2}=x+2.$$

The left side requires $x\ne2$. For every such $x$, factoring and dividing by the nonzero factor $x-2$ proves the equality. At $x=2$ the left side is undefined, so this is an identity on $\mathbb R\setminus\{2\}$, not an equality between the two natural-domain functions on all real inputs.

Worked example

Worked example 2: a trigonometric domain. On the common domain of the two sides,

$$\frac{\sin\theta}{1+\cos\theta} =\frac{1-\cos\theta}{\sin\theta}.$$

The right side requires $\sin\theta\ne0$, equivalently $\theta\notin\pi\mathbb Z$. On that domain $\cos\theta\ne-1$, so the left denominator is also nonzero. Multiplying the left side by $(1-\cos\theta)/(1-\cos\theta)$ is permitted there, because $\cos\theta\ne1$ as well. Then

$$\frac{\sin\theta(1-\cos\theta)}{1-\cos^2\theta} =\frac{\sin\theta(1-\cos\theta)}{\sin^2\theta} =\frac{1-\cos\theta}{\sin\theta}.$$

At $\theta=0$ the left side alone equals zero but the right is undefined. The identity is not an assertion that their natural domains agree. Rationalizing a denominator without checking the newly used factor can conceal this difference.

A useful proof format is to transform one side into the other through identities with stated conditions. Another is to subtract the sides and prove the difference is zero. Starting from the desired equality can also work if every line is explicitly equivalent and the chain ends at an already established truth; merely repeating the desired equality in a different form is not a proof.

7.2 Inequalities come from nonnegative quantities

Proposition

For real $t$, $t^2\ge0$, with equality exactly when $t=0$. Consequently,

$$(a-b)^2\ge0\quad\implies\quad a^2+b^2\ge2ab \qquad(a,b\in\mathbb R),$$

with equality exactly when $a=b$. This is a general inequality, not a claim that $a,b$ are positive.

Proposition

For nonnegative $u,v$, insert $a=\sqrt u$ and $b=\sqrt v$. Then

$$\frac{u+v}{2}\ge\sqrt{uv},$$

with equality exactly when $u=v$. This is the two-number arithmetic–geometric mean inequality. Its square roots require $u,v\ge0$. Extending this particular formula to arbitrary real $u,v$ is not valid.

Worked example

Worked example 3: a positive reciprocal bound. If $x>0$, the square $(x-1)^2\ge0$ gives $x^2+1\ge2x$. Dividing by the positive number $x$ yields

$$x+\frac1x\ge2,$$

with equality only at $x=1$. If $x<0$, division reverses the inequality and gives $x+1/x\le2$, but the sharper negative-side bound is $x+1/x\le-2$, obtained by applying the positive result to $-x$. At $x=0$ the expression is undefined. The sign hypothesis is part of the theorem.

Worked example

Worked example 4: a constrained product. Suppose $u,v\ge0$ and $u+v=10$. Then $(u-v)^2\ge0$ implies

$$100=(u+v)^2=(u-v)^2+4uv\ge4uv.$$

Hence $uv\le25$, with equality exactly at $u=v=5$. This determines the maximum and shows that it is achieved within the admissible domain. It does not assert the same maximum if the sum or the nonnegativity restrictions are changed.

A systematic strategy is to put the desired inequality in the form “nonnegative expression $\ge0$.” For $x\ge0$,

$$x-\frac{x}{1+x}=\frac{x^2}{1+x}\ge0,$$

because the numerator is nonnegative and the denominator positive. Thus $0\le x/(1+x)\le x$. Equality in the upper bound occurs exactly at $x=0$. For $x<-1$ the denominator has another sign, so this argument cannot be reused without a new analysis.

7.3 Absolute values and a two-dimensional inequality

Proof

From the definition, $-|a|\le a\le|a|$. Add this inequality for $a$ and $b$ to obtain

$$-(|a|+|b|)\le a+b\le|a|+|b|.$$

Since $|a|+|b|\ge0$, this is equivalent to the real triangle inequality

$$|a+b|\le|a|+|b|.$$

Equality occurs exactly when $ab\ge0$, including a zero input. For a direct check, square the two nonnegative sides: the difference of their squares is $2(|a||b|-ab)$, which is zero exactly when $ab\ge0$.

Applying the triangle inequality to $a=(a-b)+b$ gives $|a|-|b|\le|a-b|$. Interchanging $a,b$ gives the other side. Together they prove the reverse triangle inequality

$$\big||a|-|b|\big|\le|a-b|.$$

These estimates compare errors without needing their signs.

Worked example

Worked example 5: a combined measurement error. Suppose an ideal sum is $s=u+v$, and measured inputs are $\tilde u=u+e_1$, $\tilde v=v+e_2$, with $|e_1|\le0.03$ and $|e_2|\le0.05$ in a common unit. Then

$$|(\tilde u+\tilde v)-s|=|e_1+e_2|\le0.08.$$

The bound is attainable when errors have the same sign and reach their bounds. Cancellation may produce a smaller actual error, but it is not guaranteed.

For any real $a,b,c,d$, expansion gives

$$(a^2+b^2)(c^2+d^2)-(ac+bd)^2=(ad-bc)^2\ge0.$$

Both square-root sides are nonnegative, so this proves

$$|ac+bd|\le\sqrt{a^2+b^2}\sqrt{c^2+d^2}.$$

Equality holds exactly when $ad=bc$, which includes a zero vector. This two-dimensional Cauchy–Schwarz inequality gives a rigorous upper bound for the dot product used in Chapter 2. No assumption that all components are positive is needed.

7.4 Why induction covers infinitely many integers

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.

Common mistake

Checking the first hundred values gives a hundred facts but not the induction step. Proving the induction step without a base gives an implication but no starting truth. Using $P(k+1)$ in order to prove itself creates a circle rather than a step.

7.5 Induction for identities, divisibility and inequalities

Worked example

Worked example 6: a sum of squares. For every integer $n\ge1$,

$$\sum_{j=1}^{n}j^2=\frac{n(n+1)(2n+1)}6.$$

At $n=1$ both sides equal one. Suppose the formula holds for an arbitrary $k\ge1$. Splitting off the new term gives

$$\begin{aligned} \sum_{j=1}^{k+1}j^2 &=\frac{k(k+1)(2k+1)}6+(k+1)^2\\ &=\frac{(k+1)[k(2k+1)+6(k+1)]}{6}\\ &=\frac{(k+1)(k+2)(2k+3)}6. \end{aligned}$$

This is exactly the formula with $n=k+1$. The principle now proves all positive integer cases. The symbol $j$ is the summation index and $k$ the current endpoint; distinguishing their jobs avoids ambiguity.

Worked example

Worked example 7: divisibility. For every integer $n\ge0$, $7^n-1$ is divisible by six. At zero the expression is zero, equal to $6\cdot0$. Suppose $7^k-1=6m$ for an integer $m$. Then

$$7^{k+1}-1=7(7^k-1)+6=6(7m+1),$$

which is divisible by six since $7m+1$ is an integer. This proves the statement. Divisibility means an integer multiple; an unverified decimal approximation is irrelevant.

Worked example

Worked example 8: Bernoulli's inequality. For every real $h\ge-1$ and integer $n\ge1$,

$$(1+h)^n\ge1+nh.$$

Fix such an $h$. The base $n=1$ is equality. Suppose the statement holds at $k\ge1$. Since $1+h\ge0$, multiplication preserves the inequality:

$$(1+h)^{k+1}\ge(1+kh)(1+h) =1+(k+1)h+kh^2\ge1+(k+1)h.$$

The last step uses $k\ge1$ and $h^2\ge0$. Induction completes the proof. Equality holds for every $h$ at $n=1$; for $n\ge2$ it holds exactly at $h=0$, because a nonzero $h$ makes the displayed $kh^2$ term strictly positive in the step to any exponent at least two. The boundary $h=-1$ is allowed: its positive powers are zero and the right side is $1-n\le0$.

This example explains why one must state sign hypotheses before multiplying an induction inequality. If $h<-1$, the multiplier is negative and the same step is invalid; indeed the claim fails at $h=-4,n=3$, where the left side is $(-3)^3=-27$ and the right side is $1-12=-11$. A proposed counterexample must itself be checked.

7.6 Recurrences and deliberately false claims

For a recurrence, an explicit formula is proved by checking the initial value and the recurrence relation. This is induction in a natural form.

Worked example

Worked example 9: an accumulating odd increment. Let $x_0=0$ and $x_{n+1}=x_n+2n+1$ for integers $n\ge0$. Claim $x_n=n^2$. At zero it is true. If $x_k=k^2$, then

$$x_{k+1}=k^2+2k+1=(k+1)^2.$$

Therefore the formula holds for all allowed indices. An input sequence of odd increments has produced square totals. The formula does not follow merely from matching its first two values.

Induction proves a particular proposition, not a vague visual pattern. Suppose someone claims $2^n\ge n^2$ for every $n\ge1$. The base $n=1$ works but $n=3$ fails: $8<9$. The corrected statement is true for every integer $n\ge4$. At four there is equality. For $k\ge4$,

$$2k^2-(k+1)^2=k^2-2k-1=(k-1)^2-2>0.$$

Assuming $2^k\ge k^2$ gives $2^{k+1}\ge2k^2\ge(k+1)^2$. The later base and the step now match. One must not claim the missing small indices as a consequence.

For some recurrences it is helpful to assume all statements from the base through $k$ when proving $k+1$. This is strong induction; it has the same least-counterexample justification. We do not need it to strengthen any of the single-step proofs above, but it explains why some induction hypotheses legitimately contain more than one earlier case.

7.7 Graded exercises

Foundation

Checkpoint

Exercise 1

1. State the common real domain and verify $(x^2-1)/(x+1)=x-1$.

Checkpoint

Exercise 2

2. Is $\sqrt{x^2}=x$ an identity for real $x$? Give the correct identity and a counterexample to the proposed one.

Checkpoint

Exercise 3

3. Prove $a^2+4b^2\ge4ab$ for real $a,b$. Give every equality case.

Checkpoint

Exercise 4

4. A student tests $n^2+n+41$ for $n=0,1,2$ and claims it is prime for every nonnegative integer $n$. Explain why the argument is insufficient and find a composite value at $n=41$.

Core

Checkpoint

Exercise 5

5. For $x>0$, prove $(x+2)^2/x\ge8$ and determine equality.

Checkpoint

Exercise 6

6. For $0\le t\le1$, prove $t(1-t)\le1/4$ and give the equality case.

Checkpoint

Exercise 7

7. Prove $|a-b|\le|a|+|b|$ for real $a,b$. Give its equality condition.

Checkpoint

Exercise 8

8. State the exact domain and verify $(1-\cos2\theta)/\sin2\theta=\tan\theta$ on that domain.

Checkpoint

Exercise 9

9. Use induction to prove $\sum_{j=1}^{n}(2j-1)=n^2$ for integers $n\ge1$.

Checkpoint

Exercise 10

10. Use induction to prove $3^n-1$ is even for all integers $n\ge0$.

Checkpoint

Exercise 11

11. Use induction to prove $n!\ge2^{n-1}$ for integers $n\ge1$. Determine exactly when equality holds.

Checkpoint

Exercise 12

12. Let $a_0=2$ and $a_{n+1}=3a_n+1$. Prove $a_n=(5\cdot3^n-1)/2$ for every integer $n\ge0$.

Synthesis

Checkpoint

Exercise 13

13. For $a,b>0$, prove $(a+b)(1/a+1/b)\ge4$, with equality characterized. Make every division condition explicit.

Checkpoint

Exercise 14

14. For real $a\le x\le b$, prove $x^2\le(a+b)x-ab$. Give all equality cases, including $a=b$.

Checkpoint

Exercise 15

15. Prove $(2u-v)^2\le5(u^2+v^2)$ for real $u,v$, using an identity or the two-dimensional inequality. Give equality cases.

Checkpoint

Exercise 16

16. Prove by induction that $2^n>n$ for all integers $n\ge1$. Explain why multiplying an inequality by two is safe here.

Checkpoint

Exercise 17

17. A purported induction says: “All groups of $n$ readings have the same value. A singleton does. To prove it for $n+1$, remove the first reading and then the last; the two $n$-reading groups overlap, so they have the same value.” Identify the exact step where the overlap argument fails.

Checkpoint

Exercise 18

18. Using Bernoulli's inequality, give an explicit tail index that proves $(3/4)^n\to0$ for positive integer $n$. Your index must ensure strict error below a prescribed $\varepsilon>0$.

7.8 Full solutions

Solution · Exercise 1

1. Require $x\ne-1$. Factoring $x^2-1=(x-1)(x+1)$ and cancelling the nonzero denominator proves the identity on that domain. At $x=-1$ the original quotient is undefined.

Solution · Exercise 2

2. The correct identity is $\sqrt{x^2}=|x|$ for all real $x$. At $x=-2$ the left side is two but the proposed right side is minus two. The original formula holds only on $x\ge0$.

Solution · Exercise 3

3. The difference is $a^2+4b^2-4ab=(a-2b)^2\ge0$. Equality occurs exactly when $a=2b$, including $a=b=0$.

Solution · Exercise 4

4. Finitely many tests do not establish all integer cases. At $n=41$, $41^2+41+41=41(41+2)=41\cdot43$, a product of integers greater than one, hence composite.

Solution · Exercise 5

5. Since $x>0$, $(x+2)^2/x-8=(x^2-4x+4)/x=(x-2)^2/x\ge0$. Equality occurs exactly when $x=2$.

Solution · Exercise 6

6. The identity $t(1-t)=1/4-(t-1/2)^2$ gives the bound, with equality exactly at $t=1/2$. The stated domain also ensures the product is nonnegative; the upper bound alone actually holds for every real $t$.

Solution · Exercise 7

7. Apply the triangle inequality to $a+(-b)$. Equality occurs when $a(-b)\ge0$, equivalently $ab\le0$, including either value zero.

Solution · Exercise 8

8. The left denominator requires $\sin2\theta=2\sin\theta\cos\theta\ne0$, so both $\sin\theta$ and $\cos\theta$ must be nonzero. This is equivalent to $\theta\notin(\pi/2)\mathbb Z$ and already guarantees tangent is defined. Using $1-\cos2\theta=2\sin^2\theta$ and cancelling nonzero $2\sin\theta$ gives $\sin\theta/\cos\theta=\tan\theta$. Tangent alone is defined at some additional points, which does not enlarge the identity's common domain.

Solution · Exercise 9

9. At one the sum is one. If the sum through $k$ is $k^2$, the next sum is $k^2+[2(k+1)-1]=k^2+2k+1=(k+1)^2$. Thus every positive integer case follows by induction.

Solution · Exercise 10

10. At zero the expression is zero, an even integer. If $3^k-1=2m$ for an integer $m$, then $3^{k+1}-1=3(3^k-1)+2=2(3m+1)$, also even. This proves all cases.

Solution · Exercise 11

11. At one there is equality. If $k!\ge2^{k-1}$, multiply by $k+1\ge2$ to get $(k+1)!\ge(k+1)2^{k-1}\ge2^k$. Equality holds at $n=1$ and $n=2$. For every $n\ge3$, the last step leading to that exponent uses $k+1\ge3$, making it strict; hence these are the only equality cases.

Solution · Exercise 12

12. At zero the formula gives $(5-1)/2=2$. If true at $k$, then $a_{k+1}=3(5\cdot3^k-1)/2+1=(5\cdot3^{k+1}-1)/2$. This matches the claimed next term and completes the proof.

Solution · Exercise 13

13. Positive $a,b$ ensure $ab>0$. Expand and subtract four: $(a+b)(1/a+1/b)-4=a/b+b/a-2=(a-b)^2/(ab)\ge0$. Equality holds exactly when $a=b$.

Solution · Exercise 14

14. The interval conditions imply $x-a\ge0$ and $b-x\ge0$. Their product is nonnegative: $(x-a)(b-x)=(a+b)x-ab-x^2\ge0$. Equality holds exactly when $x=a$ or $x=b$. If $a=b$, the only allowed point is that common endpoint and equality still holds.

Solution · Exercise 15

15. Subtract the left side from the proposed right side: $5(u^2+v^2)-(2u-v)^2=(u+2v)^2\ge0$. Equality occurs exactly when $u=-2v$. This also follows by Cauchy–Schwarz with component vectors $(u,v)$ and $(2,-1)$.

Solution · Exercise 16

16. At one, $2>1$. If $2^k>k$, multiply by the positive number two to obtain $2^{k+1}>2k$. For $k\ge1$, $2k\ge k+1$, so $2^{k+1}>k+1$. No inequality reverses because the multiplier is positive.

Solution · Exercise 17

17. In the step from one to two readings, the two one-reading groups have no shared reading. Thus nothing forces their values to agree. The argument needs an overlap but lacks it exactly at the first extension; a valid base alone cannot repair a failed induction step.

Solution · Exercise 18

18. Since $4/3=1+1/3$, Bernoulli gives $(4/3)^n\ge1+n/3$. Taking positive reciprocals yields $(3/4)^n\le1/(1+n/3)$. Choose a positive integer $N$ with $N>3/\varepsilon$. Then for all $n\ge N$, $1/(1+n/3)<3/n\le3/N<\varepsilon$. This proves convergence using an explicit, though not sharp, tail threshold.

Summary

An identity needs a domain; an equation needs a solution set. Reversible steps prove equivalence only where their operations are permitted. Squares, factorizations and absolute-value estimates give inequalities with explicit equality cases. Induction requires a correctly placed base and a valid implication for an arbitrary later integer. It can verify formulas, divisibility, recurrences and bounds, but cannot make an incorrect proposition true or replace a missing convergence argument.

Connections. Chapter 5's finite formulas are natural induction statements. Bernoulli's inequality supports geometric sequence limits in Chapter 6. Triangle and Cauchy–Schwarz inequalities support the coordinate and complex-modulus calculations of Chapters 2 and 8. Sign-aware transformations remain essential in Chapter 9's logarithmic inequalities.