Proof by mathematical induction

1. Why induction proves infinitely many statements

Mathematical induction proves a proposition P(n) for every positive integer n by joining two logically different tasks. The initial statement verifies P(1). The inductive step proves the implication P(k) ⇒ P(k+1) for an arbitrary positive integer k. If both are established, P(1) gives P(2), then P(2) gives P(3), and so on. The conclusion is therefore about all positive integers even though the written proof has finitely many lines. Checking P(1), P(2) and P(3) only supplies examples; it never proves the universal claim.

A formal proof should name the proposition before using it. For example, for 1+3+⋯+(2n−1)=n², write P(n): 1+3+⋯+(2n−1)=n². The statement starts at n=1, so the initial statement is 1=1². In the inductive step assume P(k): 1+3+⋯+(2k−1)=k². The next sum contains exactly one new term, 2(k+1)−1=2k+1. Hence 1+3+⋯+(2k−1)+(2k+1)=k²+2k+1=(k+1)². This is P(k+1), so the identity holds for every positive integer n.

The phrase ‘assume P(k)’ is local to the implication; it does not assume the theorem for every n. The value k must remain arbitrary. Substituting k=4 proves only the transition from the fourth case to the fifth. Likewise, proving P(k+1) without using P(k) may establish a separate algebraic fact, but it does not display the required chain unless that fact independently proves every case. Close the proof by naming both completed parts and the domain: since P(1) is true and P(k) implies P(k+1), P(n) is true for all positive integers n.

When reading a proposed proof, test the implication separately from the first case. A flawless transition cannot begin the chain if the initial statement is false, and a true first case cannot carry the chain without a general transition. This separation is the quickest way to diagnose an incomplete argument.

2. Divisibility proofs

To prove divisibility, translate the claim into the existence of an integer multiplier. Consider P(n): 5 divides 6^n−1. The initial statement is 6^1−1=5, which is divisible by 5. For the inductive assumption, write 6^k−1=5m for some integer m. This equation is stronger and more useful than merely repeating ‘6^k−1 is divisible by 5’, because it supplies an expression that can be substituted into the next case.

Now 6^(k+1)−1=6·6^k−1=6(6^k−1)+5. Using the assumption gives 6(5m)+5=5(6m+1). Since m is an integer, 6m+1 is an integer, so the expression is divisible by 5. This establishes P(k+1). The rearrangement is purposeful: it exposes the earlier expression 6^k−1 and leaves a second visible multiple of 5. Writing only 6^(k+1)−1=5(…) without deriving the bracket from P(k) conceals the essential reasoning.

For a different modulus, search for the same structure. To prove 7 divides 8^n−1, write 8^(k+1)−1=8(8^k−1)+7. If 8^k−1=7m, the next expression is 7(8m+1). Always state why the new multiplier is an integer. Avoid decimal division or a calculator remainder as proof: a few computed cases cannot establish the result for arbitrary n. Divisibility induction is assessed through exact integer algebra and the explicit use of the inductive assumption.

A useful divisibility check is to reduce a few powers modulo the divisor, but present that only as verification after the algebraic proof. Modular patterns can suggest the factorisation; the induction marks come from expressing the k+1 case as an integer multiple of the required divisor.

3. Finite sums and the next term

A sum proof succeeds when the left side of P(k+1) is written as the left side of P(k) plus the new term. For P(n): 1+2+⋯+n=n(n+1)/2, the initial statement is 1=1·2/2. Assume 1+2+⋯+k=k(k+1)/2. Then 1+2+⋯+k+(k+1)=k(k+1)/2+(k+1). Factor rather than expand blindly: (k+1)(k/2+1)=(k+1)(k+2)/2, which is the stated formula with n replaced by k+1.

The target form matters. Before manipulating the inductive step, replace n by k+1 on the right-hand side and simplify it. If the claimed sum is n(n+1)(2n+1)/6, the target is (k+1)(k+2)(2k+3)/6. Knowing the destination helps choose a common denominator and useful factors. It also prevents the frequent error of writing k(k+1)(2k+1)/6 as the target, which is still P(k), not P(k+1).

For a geometric-type sum, P(n): 1+2+⋯+2^(n−1)=2^n−1, the new term is 2^k. Under the assumption, the next sum is (2^k−1)+2^k=2^(k+1)−1. Notice that the upper exponent changes from n−1 to k in the added term. Ellipses must be unambiguous: show the first terms, the general last term and the added term. When the indexing begins somewhere other than 1, verify the actual first permitted integer and state the conclusion from that starting value.

Keep the summation endpoints visible while forming P(k+1). If the sequence starts with a formula in r, evaluate that formula at r=k+1 to obtain the new term. This avoids copying the kth term and is especially important for powers, odd numbers and quadratic terms.

For the square sum, the added term is (k+1)², whereas the target contains the factor 2k+3. After taking a common denominator, factor out k+1 before comparing those expressions.

4. Products and derivative patterns

Product identities use the next factor in the same way that sums use the next term. Suppose P(n): product from r=1 to n of (r+1)/r equals n+1. The initial product is 2/1=2. Assume the product to k equals k+1. Multiplying by the factor for r=k+1 gives (k+1)·(k+2)/(k+1)=k+2, which is the target for P(k+1). Cancellation is valid because k+1 is a positive integer and therefore nonzero. Writing the added factor explicitly prevents an index shift.

Induction can also prove an nth-derivative formula. Let f(x)=(x+2)e^x and propose P(n): f^(n)(x)=(x+n+2)e^x for n≥0. At n=0 this is f(x)=(x+2)e^x. Assume f^(k)(x)=(x+k+2)e^x. Differentiate once: f^(k+1)(x)=1·e^x+(x+k+2)e^x=(x+k+3)e^x. Since x+k+3=x+(k+1)+2, the expression is exactly the target form.

If a question starts derivatives at n=1, test P(1), not P(0), unless the statement explicitly defines the zeroth derivative. Retain the derivative superscript clearly so it is not mistaken for a power. The product rule is the engine of the inductive implication, and both product-rule terms must appear. A calculator can differentiate several cases to suggest the pattern, but the proof must establish the base case and the arbitrary transition.

Derivative patterns should be tested for n=0,1,2 before the proposition is finalised. Those cases often reveal an offset such as n+2. Once the pattern is correct, induction proves it; observed derivatives alone remain evidence for a conjecture rather than a proof.

In the derivative example, n=1 gives (x+3)e^x and n=2 gives (x+4)e^x. These explicit cases establish the offset before the induction step handles arbitrary n.

5. De Moivre's theorem by induction

For a real angle θ, de Moivre’s theorem states [cis θ]^n=cis(nθ) for positive integers n, where cis θ=cos θ+i sin θ. The initial statement n=1 is immediate. Assume [cis θ]^k=cis(kθ). Then [cis θ]^(k+1)=[cis θ]^k cis θ=cis(kθ)cis θ. Multiplying Cartesian forms and using the compound-angle identities gives cos((k+1)θ)+i sin((k+1)θ)=cis((k+1)θ). This proves the inductive implication.

The compound-angle step can be shown explicitly: (cos kθ+i sin kθ)(cos θ+i sin θ)=(cos kθ cos θ−sin kθ sin θ)+i(sin kθ cos θ+cos kθ sin θ). The real part is cos((k+1)θ), and the imaginary part is sin((k+1)θ). Merely quoting the result being proved would be circular; multiplication plus the established angle formulas supplies an independent justification.

The induction establishes positive integer powers. Negative integer and rational-index extensions need additional reasoning about reciprocals and roots; they do not follow merely by changing n in the induction conclusion. In applications, keep the answer in exact cis form when requested and reduce an argument only after multiplication. For example, [2cis(3π/5)]^5=32cis(3π)=−32. The modulus becomes 2^5 and the argument becomes 5·3π/5; neither operation should be omitted.

In polar multiplication, distinguish equality of complex numbers from equality of written arguments. Arguments differing by 2pi describe the same direction. State any chosen argument interval when turning the induction result into a principal-argument answer.

At n=2, direct multiplication gives cis²θ=cos2θ+i sin2θ; it checks the first nontrivial case without replacing the arbitrary induction step.

6. Writing and checking a complete proof

Use a fixed proof layout under examination conditions. First state P(n) with its permitted integers. Second verify the initial statement by evaluating both sides. Third write ‘Assume P(k) is true for an arbitrary positive integer k’ and record the assumption as an equation. Fourth begin with the P(k+1) expression, expose the P(k) part, invoke the assumption, and simplify to the target. Finally state the induction conclusion. This order lets a marker see the logical dependency without reconstructing it from scattered algebra.

Do not manipulate both sides of the desired identity in parallel until they match, because that can assume the very equality being proved. Work from the P(k+1) left side to its right side, or make a sequence of explicitly equivalent transformations. In a divisibility proof introduce an integer multiplier. In a sum or product proof identify the new term or factor. In a derivative proof differentiate the assumed kth formula once. Each genre has a visible bridge from k to k+1.

A final audit should answer five questions. Is the first value correct for the stated domain? Is k arbitrary? Does the step actually use P(k)? Is the final expression recognisably P(k+1)? Does the conclusion name all permitted n? Mathematical induction proofs involving inequalities or recursion formulae are outside this SACE subject’s required scope, so revision time should centre on divisibility, finite sums, products, nth derivatives and de Moivre’s theorem. Those included forms still demand exact notation and a complete chain of logic.

7. Extended proof studio: three inductions with different invariants

Why these examples belong together. An induction proof is a machine for moving from one integer to the next, but the algebra that makes the move possible depends on the claimed invariant. Divisibility wants an explicit multiple of the divisor; a sum wants the next summand separated from the old sum; a product wants the next factor separated from the old product. Work through all three rather than memorising one generic “assume true for k” sentence. In every case state the starting integer, the proposition P(n), the base calculation, the precise hypothesis and the deduction for k+1.

Problem A: divisibility. Prove that 48 divides 7^(2n)−1 for every integer n≥1. For n=1, 7²−1=49−1=48, so the base case is a multiple of48. Assume at some integer k≥1 that 7^(2k)−1=48m for an integer m. The next exponent is 2(k+1)=2k+2, not 2k+1. Rearrange 7^(2k+2)−1=49·7^(2k)−1=49[7^(2k)−1]+48=49(48m)+48=48(49m+1). Since 49m+1 is an integer, P(k+1) holds. Base plus implication proves all n≥1. This is stronger than checking n=1,2,3 numerically: no finite list of calculations covers infinitely many integers. It is also more precise than writing 7²≡1 mod48 and stopping; that congruence suggests the proof but the induction step shows how the invariant persists.

Independent modular check. Because 7²=49≡1 (mod48), 7^(2n)=(7²)^n≡1^n≡1 (mod48), confirming the statement by modular arithmetic. The modular observation can guide the induction, but if the task asks specifically for induction, present base and step as above. The factorisation 7^(2n)−1=(7^n−1)(7^n+1) is true but does not immediately show a factor48 for every n without further parity analysis. Choose the transformation that naturally exposes the inductive hypothesis. If the base were claimed at n=0, it would also be true because 7⁰−1=0 is divisible by48; the proof can be started there too, but the stated domain begins at1.

Problem B: cubic sum. Prove Σ_{j=1}^{n}j³=[n(n+1)/2]² for n≥1. At n=1, left side1³=1 and right side[1·2/2]²=1. Assume Σ_{j=1}^{k}j³=[k(k+1)/2]². Add the next cube to both sides: Σ_{j=1}^{k+1}j³=[k(k+1)/2]²+(k+1)³. Factor (k+1)²: (k+1)²[k²/4+(k+1)]=(k+1)²[k²+4k+4]/4=(k+1)²(k+2)²/4=[(k+1)(k+2)/2]². The final line is the proposed formula with n replaced by k+1, which closes the step. Writing a correct expression for the k-case without showing this factorisation leaves the essential deduction absent.

As a numerical check at n=4, 1³+2³+3³+4³=1+8+27+64=100 and [4·5/2]²=10²=100. This check can catch an arithmetic slip in a draft, but it is not a substitute for induction. The formula implies the sum of the first n cubes equals the square of the nth triangular number. That pattern explains why the algebraic target contains (k+1)²(k+2)² and suggests factoring (k+1)² rather than expanding every term. General proof often becomes easier when the target expression guides the manipulation.

Problem C: a rational product. Show ∏_{j=1}^{n}(1+1/j)=n+1 for n≥1. The first factor is1+1=2, matching n+1=2 at n=1. Assume ∏_{j=1}^{k}(1+1/j)=k+1. Then ∏_{j=1}^{k+1}(1+1/j)=[∏_{j=1}^{k}(1+1/j)](1+1/(k+1))=(k+1)(k+2)/(k+1)=k+2. The denominator k+1 is nonzero because k≥1. That is exactly P(k+1). A direct telescoping check gives ∏(j+1)/j=(2/1)(3/2)…[(n+1)/n]=n+1; the cancellation helps discover the conjecture, while the induction demonstrates the required recursive structure.

Proof audit. Each induction used P(k) only after declaring it for an arbitrary k in the permitted range. None assumed P(k+1) or substituted the desired conclusion before deriving it. If an expression is rearranged by dividing, check the divisor is nonzero on the domain. If the property is about integers, finish by identifying the integer multiplier, not merely a decimal quotient that happens to look whole for examples. An exam marker needs to see the logical bridge, not just a box around the final formula.

Problem D: a polynomial sum whose next term drives the factorisation. Prove Σ_{j=1}^{n}j(j+1)=n(n+1)(n+2)/3 for n≥1. The base n=1 is1·2=2, while1·2·3/3=2. Assume Σ_{j=1}^{k}j(j+1)=k(k+1)(k+2)/3. The new summand is(k+1)(k+2), so Σ_{j=1}^{k+1}j(j+1)=k(k+1)(k+2)/3+(k+1)(k+2). Factor the shared pair to get(k+1)(k+2)(k/3+1)=(k+1)(k+2)(k+3)/3. This equals the asserted formula with n=k+1. Note that writing j(j+1) at j=k+1 gives(k+1)(k+2), not(k+1)²; the latter would silently change the sequence being summed. For n=3, the direct terms2+6+12=20, while3·4·5/3=20.

The sum also has a non-inductive derivation: j(j+1)=j²+j, so known formulas for squares and linear terms give n(n+1)(2n+1)/6+n(n+1)/2=n(n+1)(2n+4)/6=n(n+1)(n+2)/3. That cross-check does not remove the need to prove the step when induction is requested, but it detects a wrong conjectured denominator. It also helps decide which structure to factor in the induction: the product n(n+1)(n+2) tells us to preserve the two factors shared by the old formula and the new summand.

Problem E: Bernoulli’s inequality with a domain condition. For x>−1 and integer n≥0, show(1+x)ⁿ≥1+nx. Base n=0 gives1≥1. Suppose(1+x)ᵏ≥1+kx. Since x>−1, the multiplier1+x is positive; multiplying preserves the inequality. Thus(1+x)^(k+1)≥(1+kx)(1+x)=1+(k+1)x+kx²≥1+(k+1)x, because kx²≥0 for k≥0. The condition x≥−1 is used exactly where multiplication occurs. If x<−1, multiplying can reverse the inequality, and the induction argument collapses. For example x=−3 and n=3 gives(−2)³=−8 while1+3(−3)=−8, equality there, but at n=2 the two sides4 and−5 behave differently; isolated cases do not restore a universal proof outside the stated domain.

Inspect equality: x=0 makes both sides1 for all n; n=0 or1 also yields equality for all permitted x. For n≥2 and x≠0 with x>−1, the added kx² term is positive after at least one nontrivial step, giving a strict inequality. The excluded boundary x=−1 can be checked separately for n≥1: the left side is0 while the right is1−n, equal at n=1 and strictly greater for n≥2. The n=0 expression at x=−1 would contain the convention-dependent 0⁰, so the main quantified claim deliberately avoids it. These boundary cases matter if a question asks “when equality holds”, which is a stronger task than proving ≥. Avoid dividing by1+x in a reverse argument at x=−1 because that value is zero.

Logical comparison. The divisibility proof needed an integer multiplier49m+1; the sum proof needed a factorisation; the Bernoulli proof needed a nonnegative multiplier and an extra nonnegative term. They share the same base-and-step logic but not interchangeable algebra. In a complete solution, an induction hypothesis is a conditional statement for an arbitrary k, not a claim that the theorem has been assumed true for every n. The last line “hence P(k+1)” must be justified by a displayed expression that actually matches the target and by every restriction used on the way. This is the substantive difference between induction and merely spotting a pattern from initial examples.

One more divisibility diagnostic. The expression7^(2n)−1 is not generally divisible by49. At n=1 it is48, already disproving that stronger claim. The induction step produces48(49m+1), and the bracket can vary with n; it proves exactly a factor48, not every factor suggested by the appearance of49 in an intermediate line. Distinguish a multiplier used in the step from the divisor in the conclusion. If a proposed theorem fails its first permitted case, record the counterexample before attempting to “prove” it.

8. Induction with powers and identities: bridge the exact next case

Problem A: geometric sum with a parameter. Let r be a real number with r≠1. Prove by induction that 1+r+r²+⋯+rⁿ=(r^(n+1)−1)/(r−1) for every integer n≥0. At n=0, the left is1 and the right is(r−1)/(r−1)=1. Assume the statement at n=k. Add r^(k+1), the one term not yet included: S_{k+1}=S_k+r^(k+1)=[r^(k+1)−1]/(r−1)+r^(k+1). On common denominator r−1 the numerator is r^(k+1)−1+r^(k+1)(r−1)=r^(k+2)−1. Thus S_{k+1}=[r^(k+2)−1]/(r−1), the required formula with n=k+1. The restriction r≠1 is required because the displayed quotient is undefined at r=1; when r=1 the sum has n+1 terms and equals n+1 by a separate trivial case. A proof that writes the quotient at r=1 has a domain error even though the underlying sum exists.

Check a negative parameter to ensure the sign has been handled: at r=−2 and n=3, direct sum is1−2+4−8=−5. The formula gives [(-2)^4−1]/(-2−1)=(16−1)/(−3)=−5. The proof itself did not require r>0, only r≠1. A common wrong step is adding r^k rather than r^(k+1), which duplicates the final term of S_k. Explicitly writing the set of terms in S_k and the single new term avoids this indexing mistake.

Problem B: de Moivre from multiplication. For any real θ and integer n≥1, prove (cosθ+i sinθ)^n=cos(nθ)+i sin(nθ). Base n=1 is immediate. Suppose the equality holds at k. Multiply by cosθ+i sinθ to obtain [cos(kθ)+i sin(kθ)](cosθ+i sinθ). Its real part is cos(kθ)cosθ−sin(kθ)sinθ=cos((k+1)θ). Its imaginary part is sin(kθ)cosθ+cos(kθ)sinθ=sin((k+1)θ). The addition identities give the desired k+1 formula. State the identities used; simply writing “by de Moivre” in a proof of de Moivre is circular. The argument also explains why complex multiplication adds angles while moduli multiply.

Apply the proved identity to w=(1+i√3)/2=cos(π/3)+i sin(π/3). Then w⁶=cos(2π)+i sin(2π)=1. More generally w^(6m)=1 for each positive integer m, but the induction above works for every n, not only multiples of6. As a direct check, w²=−1/2+(√3/2)i and w³=−1. It is useful to compute one low power by Cartesian multiplication to catch a sign error in the assigned argument π/3. A complex number at argument −π/3 has the conjugate and produces different intermediate powers despite also having sixth power1.

Problem C: a parameter-dependent inequality. Prove 2ⁿ≥n+1 for every integer n≥0. Base n=0 gives1≥1. If 2ᵏ≥k+1, then 2^(k+1)=2·2ᵏ≥2(k+1). For k≥0, 2(k+1)≥k+2 because their difference is k≥0. Therefore 2^(k+1)≥k+2. The second inequality is necessary: doubling the lower bound k+1 does not literally produce the target k+2, so the bridge must be shown. At n=0 and1 equality holds; for n≥2 the inequality is strict. This simple case illustrates that an induction step can need an auxiliary comparison, not just substitution.

Where the method could fail. To prove a stronger inequality such as 2ⁿ≥n² for all n≥1 would fail already at n=3, since8<9. Induction cannot repair a false universal statement. Another claimed induction might start at n=5 and prove all later cases but say “therefore all n≥0”; the earlier n=0,…,4 remain unproved. Finally, a recurrence that depends on both P(k) and P(k−1) requires enough base cases and a strong or two-step hypothesis. The hypothesis must match the dependency of the next step. Write the quantified conclusion exactly: “for every integer n≥0” is more precise than “for all n” if negative or noninteger values were never considered.

Answer-check discipline. Before finalising a proof, test the first few cases to detect a false conjecture, confirm the base belongs to the requested domain, inspect the k→k+1 algebra for omitted restrictions, and compare the final expression literally with P(k+1). These checks are not boilerplate; each prevents a concrete logical error illustrated above. A polished induction is a chain of implications grounded at a valid base, not merely correct algebra written in the language of induction.

Problem D: a nontrivial finite product. Prove, for n≥1, that ∏_{j=1}^{n}(1−1/(j+1)²)=(n+2)/[2(n+1)]. Before using induction, check each factor is defined and positive: j+1≥2, so there is no zero denominator and1−1/(j+1)²>0. At n=1, left=1−1/4=3/4 and right=(1+2)/[2(1+1)]=3/4. Assume product through j=k is(k+2)/[2(k+1)]. The next factor is1−1/(k+2)²=[(k+2)²−1]/(k+2)²=(k+1)(k+3)/(k+2)². Multiplying, P_{k+1}=[(k+2)/(2(k+1))][(k+1)(k+3)/(k+2)²]=(k+3)/[2(k+2)], precisely the formula with n=k+1. Every cancellation uses positive integers, so no illegal division occurs.

There is a direct telescoping route: each factor [(j+1)²−1]/(j+1)²=j(j+2)/(j+1)²=[j/(j+1)]·[(j+2)/(j+1)]. The first product over j=1,…,n gives1/(n+1); the second gives(n+2)/2, and their product is(n+2)/[2(n+1)]. This second method independently checks the induction algebra. As n grows, the expression approaches1/2 from above, since(n+2)/[2(n+1)]=½[1+1/(n+1)]. The limit is not obtained by claiming each factor is “almost1” and therefore the entire infinite product is1; infinitely many small reductions can accumulate. The exact finite formula settles the limit.

Problem E: recurrence form. Let a₁=2 and a_{n+1}=3a_n+1 for n≥1. Conjecture a_n=(5·3^(n−1)−1)/2. Test n=1: (5−1)/2=2. Suppose a_k=(5·3^(k−1)−1)/2. Then a_{k+1}=3[(5·3^(k−1)−1)/2]+1=[5·3^k−3+2]/2=(5·3^k−1)/2, which is the conjectured expression at index k+1. This is an induction proof of an explicit solution to the recurrence. Numerically, a₂=3(2)+1=7 and a₃=3(7)+1=22; the formula gives(15−1)/2=7 and(45−1)/2=22. A wrong guess a_n=2·3^(n−1) would match only n=1 and fail at n=2, showing why initial testing precedes proof.

A complementary solution method shifts the recurrence by its fixed point: if b_n=a_n+½, then b_{n+1}=3a_n+1+½=3(a_n+½)=3b_n. Since b₁=2.5, b_n=2.5·3^(n−1), hence a_n=(5·3^(n−1)−1)/2. This derivation suggests the same closed form but does not change the induction requirements if a proof by induction is requested. It also explains why the expression contains −1/2: the affine recurrence becomes a geometric one after a shift. This form of reasoning extends to a_{n+1}=ra_n+c when r≠1, with fixed-point shift c/(r−1), provided the index and initial condition are carried through correctly.

Boundary and notation checks. The product formula begins at n=1; n=0 would be an empty product conventionally equal to1, and the displayed right-hand expression at n=0 also equals1, so the identity could be extended if that convention were stated. The recurrence formula uses 3^(n−1), which is well-defined at n=1; replacing it by 3^n would ruin the base. In the de Moivre proof above, the base is n=1, while the geometric sum naturally starts at n=0. These are genuinely different starting domains. Always write the first term or first product factor explicitly when shifting from k to k+1, and simplify the final expression to the target’s exact index before claiming completion.

Recurrence integrality check. The closed form (5·3^(n−1)−1)/2 always yields an integer for n≥1 because 3^(n−1) is odd, five times it is odd, and subtracting one produces an even numerator. This property is also automatic from the integer recurrence, but checking the expression independently guards against a missing factor of two. At n=4 the recurrence gives3(22)+1=67, while the formula gives(5·27−1)/2=67. These checks support the algebra without replacing the base-and-step proof.