Pp5 - Induction for divisibility and other results | OCR A-Level Further Mathematics B (MEI)

Induction works beyond sequence formulae: it can establish divisibility, inequalities and identities involving complex numbers. You will prove explicitly stated results by choosing a useful connection between neighbouring cases. You will also see exactly how far an induction proof reaches, including the extra argument needed for negative powers in de Moivre's theorem.

Exposing an integer multiple

Can you prove that $11^{2027}-20271$ is divisible by $100$ , without writing out the power?

The small cases suggest something stronger than a last-digit pattern: $11^1-11=0$ , $11^2-21=100$ and $11^3-31=1300$ . In each case, subtracting $1+10n$ from $11^n$ leaves a multiple of $100$ . Induction can establish the pattern for every non-negative integer, including $2027$ .

You already know

In induction, check the first allowed integer, assume the result for an arbitrary $k$ , and use it to establish the $k+1$ case. The conclusion must say that if the result holds at $k$ , it holds at $k+1$ , and connect this implication to the base case.

For divisibility, give the quotient a name. This turns a verbal hypothesis into an algebraic expression that you can substitute.

Divisibility

An integer $N$ is divisible by a positive integer $d$ if $N=dm$ for some integer $m$ . For example, $0=6(0)$ is divisible by $6$ . Writing $N=6x$ with an unspecified real $x$ does not establish divisibility: $1=6(1/6)$ , but $1$ is not divisible by $6$ .

The quotient $m$ and the index $k$ do different jobs. The quotient need not equal $k$ , and it may change at each step. Your aim is simply to make the next expression an integer multiple of the divisor too.

Worked example 1: a power minus one

Question. Prove by mathematical induction that $7^n-1$ is divisible by $6$ for every integer $n\ge0$ .

Plan. Check $n=0$ , assume $7^k-1=6m$ , and express the next case using the whole assumed multiple.

7^0-1=0=6(0) \qquad \text{base case}

Assume $7^k-1=6m$ for an integer $m$ , where $k\ge0$ is an arbitrary integer. Then

\begin{aligned} 7^{k+1}-1&=7(7^k-1)+6 && \text{expose the hypothesis} \\ &=7(6m)+6 && \text{use the hypothesis} \\ &=6(7m+1) && \text{factor out }6 \end{aligned}

Why this step? Multiplying $7^k-1$ by $7$ gets close to the next expression. The correction is $6$ , another multiple of the divisor.

Answer. Since $7m+1$ is an integer, $7^{k+1}-1$ is divisible by $6$ . Thus if the result is true for $n=k$ , it is true for $n=k+1$ . It is true for $n=0$ , so it is true for all integers $n\ge0$ , by induction.

Check. At $n=2$ , $49-1=48=6(8)$ . Expanding the first line gives $7^{k+1}-7+6=7^{k+1}-1$ .

Worked example 2 keeps the same power but subtracts the additional linear term $6n$ . This correction allows a stronger divisor, $36$ . The main decision is still to expose seven times the assumed expression.

Worked example 2: a stronger divisibility result

Question. Prove that $7^n-1-6n$ is divisible by $36$ for every integer $n\ge0$ .

Plan. Assume the corrected expression equals $36m$ , then compare the next case with seven times that expression.

7^0-1-6(0)=0=36(0) \qquad \text{base case}

Assume $7^k-1-6k=36m$ for an integer $m$ , where $k\ge0$ is an arbitrary integer. Then

\begin{aligned} 7^{k+1}-1-6(k+1)&=7(7^k-1-6k)+36k && \text{regroup the next case} \\ &=7(36m)+36k && \text{use the hypothesis} \\ &=36(7m+k) && \text{factor out }36 \end{aligned}

Why this step? Seven times the previous expression contains $-42k$ , whereas the next expression contains $-6k$ . Adding $36k$ repairs the difference and stays divisible by $36$ .

Answer. Since $7m+k$ is an integer, the next expression is divisible by $36$ . If the result is true for $n=k$ , it is true for $n=k+1$ . Since it is true for $n=0$ , it is true for every integer $n\ge0$ , by induction.

Check. At $n=3$ , $343-1-18=324=36(9)$ . Expanding the regrouped line gives $7^{k+1}-7-6k$ , the required next expression.

These divisibility results are not in the formula booklet; the statement to prove is supplied in the question. In the second proof, saying “both terms are divisible by $36$ ” is less explicit than exhibiting their sum as the single integer multiple $36(7m+k)$ .

Watch out

Wrong: assume $7^k-1-6k=36k$ . The quotient is not generally the index; at $k=3$ it is $9$ . Right: introduce an integer $m$ , then finish with $36$ times a clearly integer-valued expression.

The next question changes the power's base to $11$ . The linear correction and divisor are given; your task is to prove the statement, using the same regrouping idea.

Keeping an inductive bound valid

An inequality can also pass from one integer to the next, but the assumption supplies a bound rather than an equality.

For example, $2^4=16>4$ . On advancing one integer, the left side doubles while the right side increases by $1$ . The proof must justify that this advantage continues, instead of relying on a sketch of growth.

You already know

Multiplying an inequality by a positive number preserves its direction. A chain $a>b\ge c$ establishes $a>c$ : the strict inequality in the first link is enough, even if the second link is an equality.

Write the next target in your rough work. After using the induction hypothesis, compare the bound it gives with that target explicitly.

Worked example 3: an exponential exceeds a linear bound

Question. Prove by induction that $2^n>n$ for all positive integers $n$ .

Plan. Start at $1$ , double the assumed inequality, and compare $2k$ with $k+1$ .

2^1=2>1 \qquad \text{base case}

Assume $2^k>k$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} 2^{k+1}&=2\times2^k && \text{one more factor} \\ &>2k && \text{use the hypothesis} \\ &\ge k+1 && k-1\ge0 \end{aligned}

Why this step? Doubling the hypothesis gives $2k$ , not $k+1$ . The final comparison closes that gap on the stated domain.

Answer. If the inequality holds for $n=k$ , it holds for $n=k+1$ . Since it holds for $n=1$ , it holds for all positive integers $n$ , by induction.

Check. At $k=1$ , the last comparison is equality, $2=1+1$ , but the earlier strict inequality still gives $2^2>2$ .

Worked example 4 changes only the coefficient in the linear bound, from $1$ to $3$ . This changes the first valid integer, so the supplied range must be checked afresh.

Worked example 4: a bound with a later starting point

Question. Prove that $2^n>3n$ for every integer $n\ge4$ .

Plan. Check $4$ , double the hypothesis, then compare $6k$ with $3(k+1)$ .

2^4=16>12=3(4) \qquad \text{base case}

Assume $2^k>3k$ for an arbitrary integer $k\ge4$ . Then

\begin{aligned} 2^{k+1}&=2\times2^k && \text{one more factor} \\ &>6k && \text{use the hypothesis} \\ &\ge3(k+1) && 3(k-1)\ge0 \end{aligned}

Why this step? The positive difference $6k-3(k+1)=3(k-1)$ verifies the comparison needed after the hypothesis has been used.

Answer. If the result holds for $n=k$ , it holds for $n=k+1$ . It holds for $n=4$ , so it holds for every integer $n\ge4$ , by induction.

Check. At $n=3$ , $8<9$ , so the strict inequality cannot start there. At $n=5$ , $32>15$ .

These particular inequalities are not in the formula booklet. They illustrate how the same induction structure handles a given bound, with its sign and starting integer kept intact.

Watch out

Wrong: “Assume $2^k=3k$ .” This replaces the claim by a different, usually false statement. Right: assume $2^k>3k$ , then retain the strict sign when multiplying by $2$ .

The following bound changes the coefficient again. Its base case is later, but the comparison in the inductive step has the same shape.

Proving de Moivre's theorem

To prove de Moivre's theorem by induction, expand one more complex factor and let the compound-angle identities produce the next angle.

You already know

You have used de Moivre's theorem to calculate powers. For its proof, return to complex multiplication and the compound-angle identities: $\cos(a+b)=\cos a\cos b-\sin a\sin b$ and $\sin(a+b)=\sin a\cos b+\cos a\sin b$ . These identities are in the formula booklet.

For a concrete check, take $\theta=\pi/2$ . The number $\cos\theta+i\sin\theta$ is $i$ , its square is $-1$ , and the proposed next angle is $2\theta=\pi$ , which gives $\cos\pi+i\sin\pi=-1$ . The general proof must work for every real $\theta$ , not only this convenient angle.

De Moivre's theorem

For real $\theta$ , positive real $r$ , and any integer $n$ :

\bigl[r(\cos\theta+i\sin\theta)\bigr]^n =r^n\bigl(\cos(n\theta)+i\sin(n\theta)\bigr)

For positive integers $n$ , the equality also holds when $r=0$ . Zero and negative powers require a non-zero base.

In the formula booklet.

First prove the unit-modulus case for positive integer powers. Keep $\theta$ fixed during the induction; the integer exponent is what changes.

Worked example 5: the unit-modulus theorem

Question. Prove by mathematical induction that

(\cos\theta+i\sin\theta)^n=\cos(n\theta)+i\sin(n\theta)

for every positive integer $n$ and every real $\theta$ .

Plan. Check $n=1$ , multiply the assumed expression by $\cos\theta+i\sin\theta$ , and use the compound-angle identities.

Fix any real $\theta$ , and put $w=\cos\theta+i\sin\theta$ . At $n=1$ ,

w^1=\cos\theta+i\sin\theta =\cos(1\theta)+i\sin(1\theta) \qquad \text{base case}

Assume $w^k=\cos(k\theta)+i\sin(k\theta)$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} w^{k+1}&=w^k w && \text{one more factor} \\ &=(\cos(k\theta)+i\sin(k\theta))(\cos\theta+i\sin\theta) && \text{use the hypothesis} \\ &=\cos(k\theta)\cos\theta-\sin(k\theta)\sin\theta && i^2=-1 \\ &\quad+i\bigl(\sin(k\theta)\cos\theta+\cos(k\theta)\sin\theta\bigr) && \text{collect imaginary terms} \\ &=\cos(k\theta+\theta)+i\sin(k\theta+\theta) && \text{compound angles} \\ &=\cos((k+1)\theta)+i\sin((k+1)\theta) && \text{required next form} \end{aligned}

Why this step? Expanding the product produces exactly the real and imaginary combinations in the two compound-angle identities. Using de Moivre's theorem itself to simplify the product would assume the result being proved.

Answer. If the identity holds for $n=k$ , it holds for $n=k+1$ . It holds for $n=1$ , so it holds for all positive integers $n$ , by induction. Since $\theta$ was any real number, the proof applies to every real $\theta$ .

Check. With $\theta=\pi/2$ and $n=3$ , the two sides are $i^3=-i$ and $\cos(3\pi/2)+i\sin(3\pi/2)=-i$ .

Worked example 6 changes only the modulus, from $1$ to $2$ . One more multiplication now also contributes a scalar factor of $2$ .

Worked example 6: a modulus different from one

Question. Prove by induction that

\bigl[2(\cos\theta+i\sin\theta)\bigr]^n =2^n\bigl(\cos(n\theta)+i\sin(n\theta)\bigr)

for all positive integers $n$ and real $\theta$ .

Plan. Keep the scalar factor outside the complex product, then use the compound-angle identities in the inductive step.

Fix real $\theta$ , and put $z=2(\cos\theta+i\sin\theta)$ . The proposed right side at $n=1$ is

2^1(\cos(1\theta)+i\sin(1\theta))=z^1 \qquad \text{base case}

Assume $z^k=2^k(\cos(k\theta)+i\sin(k\theta))$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} z^{k+1}&=z^k z && \text{one more factor} \\ &=2^{k+1}(\cos(k\theta)+i\sin(k\theta))(\cos\theta+i\sin\theta) && \text{use the hypothesis} \\ &=2^{k+1}\bigl(\cos(k\theta)\cos\theta-\sin(k\theta)\sin\theta && \text{real terms} \\ &\qquad+i(\sin(k\theta)\cos\theta+\cos(k\theta)\sin\theta)\bigr) && \text{imaginary terms} \\ &=2^{k+1}\bigl(\cos((k+1)\theta)+i\sin((k+1)\theta)\bigr) && \text{compound angles} \end{aligned}

Why this step? The extra factor has modulus $2$ , so $2^k$ becomes $2^{k+1}$ . The angle advances from $k\theta$ to $(k+1)\theta$ through the same expanded product as before.

Answer. If the identity holds for $n=k$ , it holds for $n=k+1$ . It holds for $n=1$ , so it holds for all positive integers $n$ , by induction, for every real $\theta$ .

Check. With $\theta=\pi/2$ and $n=2$ , the base is $2i$ , so its square is $-4$ . The right side gives $4(\cos\pi+i\sin\pi)=-4$ .

For the general booklet result, replace the scalar $2$ in this proof by a fixed $r>0$ : the base case becomes $r^1w=rw$ , and the scalar multiplication in the inductive step is $r^k r=r^{k+1}$ . The expanded trigonometric product is unchanged, so this establishes the stated general result for every positive integer $n$ . If $r=0$ , both sides are zero for positive $n$ . Part 4 handles the remaining integer exponents for $r>0$ .

Watch out

Wrong: $(\cos\theta+i\sin\theta)^{k+1}=\cos((k+1)\theta)+i\sin((k+1)\theta)$ , “by de Moivre”. That is the target, not a proof of it. Right: start from $w^k w$ , use the hypothesis only for $w^k$ , expand, and apply compound angles.

The next proof changes the modulus again. Show the intermediate product rather than citing the theorem whose special case you are proving.

Reaching zero and negative exponents

Induction starting at $1$ and advancing by $1$ proves a result for positive integers; it does not automatically reach $0$ or a negative integer.

For de Moivre's theorem, these other cases follow from the meanings of zero and negative powers. Let $z=r(\cos\theta+i\sin\theta)$ with $r>0$ , so $z\ne0$ . At $n=0$ ,

\begin{aligned} z^0&=1 && \text{non-zero base} \\ r^0(\cos(0\theta)+i\sin(0\theta))&=1(1+0i)=1 && \text{same value} \end{aligned}

For negative exponents, first take a reciprocal. Since $(\cos\theta+i\sin\theta)(\cos\theta-i\sin\theta)=\cos^2\theta+\sin^2\theta=1$ ,

\begin{aligned} \frac{1}{z}&=\frac{1}{r}(\cos\theta-i\sin\theta) && \text{multiply by the conjugate} \\ &=\frac{1}{r}(\cos(-\theta)+i\sin(-\theta)) && \text{cosine even, sine odd} \end{aligned}

This reciprocal identity is not a separate formula in the booklet; it follows from conjugation and $\cos^2\theta+\sin^2\theta=1$ . The negative angle is the important change. Put $n=-m$ , where $m$ is a positive integer, and apply the positive-integer theorem to this reciprocal:

\begin{aligned} z^{-m}&=\left(\frac{1}{z}\right)^m && \text{definition of a negative power} \\ &=r^{-m}\bigl(\cos(-m\theta)+i\sin(-m\theta)\bigr) && \text{positive-power theorem at }-\theta \end{aligned}

This is exactly the booklet formula for $n=-m$ . Together with the positive proof and the separate zero case, it covers every integer exponent when the base is non-zero. For $z=0$ , positive integer powers are defined, but a negative power would require division by zero; the zero-power step above also does not apply to a zero base.

Key idea

The proof's range comes from its starting case and its direction of travel. Extending de Moivre to all integers needs a separate zero case and a reciprocal argument for negative exponents.

The opening number has a similarly precise justification: the proved divisibility statement applies at $n=2027$ , and $1+10(2027)=20271$ . Even a power with thousands of digits can have its divisibility settled by a few lines about the index. No expansion of that power is needed.

Quick Recap

For divisibility, assume an integer multiple of the divisor and expose that expression inside the next case.
For an inequality, preserve the sign of the hypothesis and justify the comparison with the next target.
To prove de Moivre, multiply one more factor, expand using $i^2=-1$ , and apply compound-angle identities.
Positive induction reaches positive exponents; the zero case and reciprocals establish the other integer exponents for non-zero bases.
A complete induction conclusion links the conditional step to the checked starting integer and the exact stated range.

The opening expression is $11^{2027}-1-10(2027)$ , so it is divisible by $100$ by the proved result.

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

Pp5 - Induction for divisibility and other results

Exposing an integer multiple

Keeping an inductive bound valid

Proving de Moivre's theorem

Reaching zero and negative exponents

Quick Recap

Learn faster with Nova