Build and check mathematical induction arguments

Use one proof principle across mathematical domains

Fix the parameters and integer range, verify the base, then derive the next case from the hypothesis. Apply this structure to sums, products, divisibility, inequalities, matrices, counting, complex numbers, vectors and derivatives

Keep four obligations visible

State P(n) and its integer domain. Verify the base directly. For an arbitrary allowed k, assume only P(k) and deduce P(k+1). Conclude exactly the range reached from the base. An empty sum is0 and an empty product is1; those conventions can make n=0 a useful base, but they must agree with the expression being defined

Identity

\(\displaystyle S_n=\frac{n(n+1)(n+2)}{3}\)

What is the next-case target for P(n)?

Prove a sum identity, ungraded

For integers n≥0, define Sₙ as the sum of j(j+1) for j=1,…,n, with S₀=0. Prove Sₙ=n(n+1)(n+2)/3 by induction. Show the exact next summand and the factorisation that reaches the target

Model: add the next indexed term

At n=0, both sides are0. Let k≥0 be an arbitrary integer and assume Sₖ=k(k+1)(k+2)/3. The next term is(k+1)(k+2). Thus Sₖ₊₁=(k+1)(k+2)[k/3+1]=(k+1)(k+2)(k+3)/3. This is P(k+1), so induction establishes the identity for every integer n≥0.

Find S₄=1×2+2×3+3×4+4×5.

Sum

\(\displaystyle S_n=\sum_{j=1}^{n}j(j+1)\)

Index domain and empty sum

\(\displaystyle n\in\mathbb Z_{\ge0},\quad S_0=0\)

Which numerical term is added when S₄ becomes S₅?

Prove a product identity, ungraded

For integers n≥0, define Pₙ as the product of(2j+1)/(2j−1) for j=1,…,n, with P₀=1. Prove Pₙ=2n+1 by induction. Explain the denominator conditions and why the next step multiplies rather than adds

Model: append a factor

The empty product gives P₀=1=2×0+1. Let k≥0 be an arbitrary integer and assume Pₖ=2k+1. Appending the factor at j=k+1 gives Pₖ₊₁=(2k+1)(2k+3)/(2k+1)=2k+3. Cancellation is valid because2k+1>0. This equals2(k+1)+1, proving the claim for every integer n≥0. Every original denominator2j−1 is positive for j≥1. Telescoping offers another proof, but a few computed products do not prove the universal claim

Product

\(\displaystyle \frac31\times\frac53\times\frac75\)

Find the product shown

Product

\(\displaystyle P_n=\prod_{j=1}^{n}\frac{2j+1}{2j-1},\quad n\in\mathbb Z_{\ge0}\)

Which factor is appended to Pₖ to obtain Pₖ₊₁?

Prove a divisibility claim, ungraded

Prove the displayed divisibility claim for every integer n≥0. Express the hypothesis using an integer quotient and construct an integer quotient for the next case

Model: expose the integer multiple

At n=0,3⁰−1=0=8×0. Let k≥0 be an arbitrary integer and assume3^(2k)−1=8q for an integer q. Then3^(2(k+1))−1=9(3^(2k)−1)+8=8(9q+1). Since9q+1 is an integer, the next case is divisible by8. Induction proves the stated claim for every integer n≥0. The factor9 follows from the exponent increasing by2.

Find the integer quotient(3⁴−1)/8.

Divisibility claim

\(\displaystyle 8\mid 3^{2n}-1,\quad n\in\mathbb Z_{\ge0}\)

Induction hypothesis

\(\displaystyle 3^{2k}-1=8q\)

Index and quotient

\(\displaystyle k\in\mathbb Z_{\ge0},\quad q\in\mathbb Z\)

If the quotient at k is q, which expression gives the next integer quotient?

Prove a parameter inequality, ungraded

Fix a real x≥−1. For every integer n≥1, prove(1+x)^n≥1+nx by induction. State why multiplication preserves the inequality and why your proof permits negative x in[−1,0]. Give a counterexample showing that the restriction on x cannot simply be removed

Model: inspect both signs needed in the step

At n=1, equality holds. Fix x≥−1 and let k≥1 be an arbitrary integer. Assume(1+x)^k≥1+kx. Multiplication by1+x≥0 preserves the weak inequality, giving(1+x)^(k+1)≥(1+kx)(1+x)=1+(k+1)x+kx²≥1+(k+1)x. The last step uses kx²≥0, so negative x in[−1,0] is allowed. Induction proves the result for every integer n≥1. Starting at1 avoids a0⁰ expression when x=−1. Without the x restriction, take x=−3,n=5: the two sides are−32 and−14, so the asserted inequality fails

For x=−1/2,n=2, find(1+x)^n−(1+nx)

Inequality claim

\(\displaystyle (1+x)^n\ge1+nx\)

Fixed parameter

\(\displaystyle x\in\mathbb R,\quad x\ge-1\)

Integer indices

\(\displaystyle n,k\in\mathbb Z_{\ge1}\)

Why does the proof allow x=−1/2?

Prove a matrix-power formula, ungraded

For a fixed real t, let A have rows(1,t) and(0,1). Prove that Aⁿ has rows(1,nt) and(0,1) for every integer n≥0. Verify the identity-matrix base and show the multiplication order in the inductive step

Model: multiply the whole matrix

At n=0, A⁰=I, matching rows(1,0) and(0,1). Fix real t and let k≥0 be an arbitrary integer. Assume Aᵏ has rows(1,kt) and(0,1). Multiplying Aᵏ on the right by A gives rows(1,t+kt) and(0,1), which is the formula at k+1. By induction it holds for every integer n≥0 and each fixed real t. This proof uses associativity and the definition of a power of one matrix; it does not assume that arbitrary matrices commute

Matrix

\(\displaystyle A=\begin{pmatrix}1&t\\0&1\end{pmatrix}\)

For t=−3, find the(1,2)entry of A⁴

What is the base A⁰ for this square matrix?

Prove a counting identity, ungraded

Using Pascal’s identity, prove that the sum of C(n,r) for r=0,…,n is2ⁿ for every integer n≥0. Explain the shifted summation index and the convention C(k,r)=0 when r<0 or r>k. You may also give a separate subset-counting argument

Model: split the next row into two shifted sums

At n=0, C(0,0)=1=2⁰. Let k≥0 be arbitrary and assume the sum over row k is2ᵏ. Pascal’s identity gives C(k+1,r)=C(k,r)+C(k,r−1). Summing for r=0,…,k+1 gives two sums. The first has an extra zero at r=k+1. In the second set s=r−1; s runs from−1 to k, with a zero at−1. Both remaining sums equal2ᵏ by the hypothesis, so their total is2^(k+1). Induction proves the identity. Independently, an n-element set has2ⁿ subsets; partitioning them by size r counts the same subsets with the displayed sum

Find the sum of all binomial coefficients in row n=4.

Counting identity

\(\displaystyle \sum_{r=0}^{n}\binom nr=2^n\)

Pascal’s identity

\(\displaystyle \binom{k+1}{r}=\binom kr+\binom{k}{r-1}\)

Which convention handles the extra boundary terms in the step from row k to row k+1?

Repair a reachability gap, ungraded

A proposed induction verifies only P(0) and proves P(k)⇒P(k+2) for every integer k≥0. Explain why this does not establish all nonnegative cases. State a sufficient repair and the exact conclusion after that repair

Model: provide both starting chains

From0, steps of2 reach only even nonnegative integers. For a counterexample to the original claim of sufficiency, let P(n) mean “n is even”: P(0) and the step-two implication hold, but P(1) is false. Verify both P(0) and P(1), retaining a step valid for every k≥0, to start the even and odd chains. Every nonnegative integer lies in exactly one of those chains, so the repaired argument reaches every n≥0.

Use complex multiplication in an induction step

Derive the complex multiplication identity, then use it to advance an integer power. State the induction hypothesis at an arbitrary allowed index, and check the nonzero-base restriction before extending to zero or negative exponents

Prove the multiplication and power rules, ungraded

Use sine/cosine addition identities to prove cis α cis β=cis(α+β). Then prove the integer-power rule for positive, zero and negative integers, stating the zero-base restrictions

Model: addition identities and induction

Expansion gives real part cos α cos β−sin α sin β and imaginary part sin α cos β+cos α sin β, hence cis(α+β). Induct on positive n: multiply cis(nθ) by cis θ. For n=0 and nonzero base the result is 1. Since cis θ cis(−θ)=1, reciprocals prove negative powers. The usual real exponent laws give rⁿ. Positive powers of zero are zero; the other zero-base cases are excluded

Make the induction hypothesis precise

Fix a real θ. Let P(n) be (cis θ)^n=cis(nθ) for integers n≥1. At n=1 the two sides are identical. For an arbitrary k≥1 assume only P(k). Then (cis θ)^(k+1)=(cis θ)^k cis θ=cis(kθ)cis θ=cis((k+1)θ), by the multiplication identity. This proves the positive-integer statement

Extend the proof with valid inverses

For a nonzero base z=r cis θ, r>0. The zero power is 1=r⁰cis 0. If n=−m with m positive, z^(−m)=1/[r^m cis(mθ)]=r^(−m)cis(−mθ), since cis(mθ)cis(−mθ)=1. Positive powers of zero are zero, but zero has no polar direction and its nonpositive powers are excluded. This supplies the complex-power induction application; later vector/calculus applications remain separate

In the induction step, which statement may be assumed?

Prove a vector-sum identity, ungraded

Fix vectors a and b in R² or R³. For integers n≥0, define Sₙ=Σⱼ₌₁ⁿ(a+jb), with S₀ the zero vector. Prove Sₙ=na+[n(n+1)/2]b by induction. State how scalar distributivity and vector addition justify the step; do not replace vectors by their magnitudes

Model: add the next vector while fixing the parameters

At n=0 the empty sum and the proposed expression are both the zero vector. Fix a,b and let k≥0 be arbitrary. Assume Sₖ=ka+[k(k+1)/2]b. Append a+(k+1)b, obtaining Sₖ₊₁=(k+1)a+[k(k+1)/2+(k+1)]b=(k+1)a+[(k+1)(k+2)/2]b. This is the target at k+1. Induction proves every integer n≥0 for each fixed pair of vectors. Only associative addition and scalar distributivity were used; no linear-independence assumption is needed

Sum of the fixed vectors

\(\displaystyle \mathbf S_n=\sum_{j=1}^{n}(\mathbf a+j\mathbf b)\)

Index domain and empty sum

\(\displaystyle n\in\mathbb Z_{\ge0},\quad\mathbf S_0=\mathbf0\)

For a=(1,−2), b=(2,1) and n=3, find the x component of S₃

Sum of the fixed vectors

\(\displaystyle \mathbf S_n=\sum_{j=1}^{n}(\mathbf a+j\mathbf b)\)

Index domain and empty sum

\(\displaystyle n\in\mathbb Z_{\ge0},\quad\mathbf S_0=\mathbf0\)

First fixed vector

\(\displaystyle \mathbf a=(1,-2)\)

Second fixed vector

\(\displaystyle \mathbf b=(2,1)\)

For the same vectors and n=3, find the y component of S₃

Sum of the fixed vectors

\(\displaystyle \mathbf S_n=\sum_{j=1}^{n}(\mathbf a+j\mathbf b)\)

Integer indices and empty sum

\(\displaystyle n,k\in\mathbb Z_{\ge0},\quad\mathbf S_0=\mathbf0\)

Which vector must be appended to Sₖ?

Separate the numerical diagram from the proof

The diagram checks three particular vectors by head-to-tail addition. The induction model proves the formula for every allowed integer and every fixed a,b. It includes zero vectors, dependent vectors and cancellation; the resultant need not have length equal to the sum of individual lengths

Prove a repeated trigonometric derivative formula, ungraded

Fix real a≠0 and b. For f(x)=sin(ax+b), prove for all integers n≥0 and real x that Dⁿf(x)=aⁿ sin(ax+b+nπ/2), where D⁰f=f. State what is fixed in the induction and why the chain rule introduces exactly one extra factor of a at each step

Model: rotate the phase by one quarter-turn

For n=0 the formula is f(x), since a⁰=1. Fix a≠0,b and let k≥0 be arbitrary. Assume the formula at k holds as a differentiable identity for all real x. Differentiating it gives Dᵏ⁺¹f=aᵏ⁺¹ cos(ax+b+kπ/2)=aᵏ⁺¹ sin(ax+b+(k+1)π/2). The chain rule supplies a and the angle identity supplies the phase shift. Thus induction proves the formula for all n≥0. Negative a is allowed. If a=0, handle the constant function separately: D⁰f=sin b and every positive-order derivative is zero

For f(x)=sin(2x), find f‴(0)

Function

\(\displaystyle f(x)=\sin(2x)\)

For the same function, find its fourth derivative at x=π/4.

Assumed identity for all real x

\(\displaystyle D^k\sin(ax+b)=a^k\sin\left(ax+b+\frac{k\pi}{2}\right),\quad k\in\mathbb Z_{\ge0},\ a,b\in\mathbb R,\ a\ne0\)

Why may the assumed formula be differentiated in this proof?

Prove a repeated reciprocal derivative formula, ungraded

Fix real a≠0,b and an open interval I on which ax+b≠0. For f(x)=1/(ax+b), prove Dⁿf(x)=(-1)ⁿ n!aⁿ/(ax+b)ⁿ⁺¹ for every integer n≥0 and x in I. Include the n=0 base, factorial step and pole restriction

Model: retain the domain while differentiating

At n=0, 0!=1 and the expression is 1/(ax+b). Fix a≠0,b and an interval avoiding the pole, and let k≥0 be arbitrary. Assume the function identity Dᵏf=(-1)ᵏ k!aᵏ(ax+b)⁻ᵏ⁻¹ on I. Differentiate: the power and chain rules multiply the coefficient by (−k−1)a and reduce the power to −k−2. Since (k+1)k!=(k+1)!, the result is (-1)ᵏ⁺¹(k+1)!aᵏ⁺¹/(ax+b)ᵏ⁺². This proves the next identity on the same interval. Induction proves all n≥0 there. The pole x=−b/a remains excluded at every order; negative nonzero denominators are permitted

For f(x)=1/(2x+1), find f″(1)

Function

\(\displaystyle f(x)=\frac1{2x+1}\)

For the same function, find f‴(0)

Function

\(\displaystyle f(x)=\frac1{ax+b}\)

Fixed real parameters

\(\displaystyle a,b\in\mathbb R,\quad a\ne0\)

Which restriction must remain in every derivative formula?

Check your written proof

Complete written proofs are ungraded and need human review. Fix the parameters, state the integer range, verify the base and derive the next case without assuming it. Justify each operation using the relevant domain conditions