Induction with binomials, matrices and derivatives
Induction proves results in algebra and calculus that hold for every whole number n. Pascal's rule carries the binomial theorem from n to n+1
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
prove the binomial theorem by induction with Pascal's rule;
find and prove a formula for the nth power of a matrix;
find and prove a formula for the nth derivative of a function.
The binomial theorem
You met the binomial theorem in its own chapter:
(a+b)n=r=0∑n(rn)an−rbr.
Here is why it holds for every n≥1. The key is Pascal's rule: (r−1k)+(rk)=(rk+1) for 1≤r≤k.
Base case. For n=1: (01)a+(11)b=a+b.
Step. Assume the theorem for n=k. Multiply both sides by (a+b). The term ak+1−rbr appears twice: once from (rk)ak−rbr×a and once from (r−1k)ak+1−rbr−1×b.
Its coefficient is (rk)+(r−1k)=(rk+1), by Pascal's rule. The first and last terms are ak+1 and bk+1.
So the theorem holds for k+1, and by induction for every n≥1.
Powers of a matrix
To find An, work out A2 and A3, guess the pattern and prove it with Ak+1=AkA.
Example. Let $A =
(1011)
.ThenA² =
(1021)
andA³ =
(1031)
.WeguessA^n =
(10n1)
$. The step is one multiplication:
(10k1)(1011)=(10k+11).
A harder one. Let $B =
(31−4−1)
$. A classic exercise proves
Bn=(1+2nn−4n1−2n).
Check n=1: it gives B. For the step, multiply the formula for k by B. The top-left entry is 3(1+2k)−4k=1+2(k+1). Check the other three entries yourself.
The nth derivative
A formula for the nth derivative is proved by differentiating once more.
Example 1.dxndn(xex)=(x+n)ex. For n=1 the product rule gives ex+xex=(x+1)ex. If the formula holds for k, differentiate (x+k)ex: the result is ex+(x+k)ex=(x+k+1)ex.
Example 2.dxndnsinx=sin(x+2nπ). For n=1: cosx=sin(x+2π). The step: the derivative of sin(x+2kπ) is cos(x+2kπ)=sin(x+2(k+1)π).
Example 3.dxndn(1+x1)=(1+x)n+1(−1)nn!. The step differentiates (1+x)−(k+1), which brings down −(k+1).
De Moivre's theorem
For every whole number n≥1,
(cosθ+isinθ)n=cosnθ+isinnθ.
For the step, multiply coskθ+isinkθ by cosθ+isinθ. The real part is coskθcosθ−sinkθsinθ=cos(k+1)θ. The imaginary part is sinkθcosθ+coskθsinθ=sin(k+1)θ. A-Level Further Mathematics and IB Higher Level both prove it this way.
What the exams ask
A-Level Further Mathematics and IB Higher Level often set induction questions on sums of series, divisibility, matrix powers and nth derivatives. The marks go to the same four parts as before: the base case, the assumption for n=k, the step, and the conclusion. Indian entrance exams more often ask for the value that a proved formula gives.
Practise with new numbers
Try it in Python
The program raises B to the powers 1 to 6 and compares each with the formula. Then sympy differentiates xex five times.
Common mistakes
Raising entries to a power.An is not the matrix of the entries to the power n.
Multiplying in the wrong order.AkA and AAk are equal for powers of one matrix, but keep one order in a proof.
Forgetting the product rule. The derivative of (x+k)ex has two terms.
Skipping the end terms. In the binomial step, ak+1 and bk+1 come from one product each.
Remember these
Pascal's rule carries the binomial theorem from k to k+1.
Matrix powers: guess from A2 and A3, prove with Ak+1=AkA.
nth derivatives: differentiate the formula for k once more.
De Moivre: (cosθ+isinθ)n=cosnθ+isinnθ.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Guess Cn for $C =
(2003)
$ and prove the step.
(2n003n)
.Step:multiplybyCtoget2^{k + 1}and3^{k + 1}$ on the diagonal.
Check the bottom-right entry of Bk+1 for $B =
(31−4−1)
$.
Find dxndne2x and prove the step.
Use De Moivre's theorem to find (cosθ+isinθ)4 when θ=8π.
What is the fourth derivative of sinx at x=0?
References
NCERT, Mathematics Textbook for Class XI (2006 edition), Chapter 4, and Class XII Part I, Chapter 3, the exercises on powers of a matrix.
Cambridge International AS and A Level Further Mathematics 9231, syllabus, Further Pure Mathematics 1, topic 1.7, Proof by induction.
Enroll free in Induction in Algebra, Calculus and Olympiad Problems
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.