HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Induction in Algebra, Calculus and Olympiad Problems
  1. 1Induction with binomials, matrices and derivatives
  2. 2Flawed inductions: finding the error
  3. 3Induction in olympiad problems
  1. Mathematics
  2. /Induction in Algebra, Calculus and Olympiad Problems
  3. /Induction with binomials, matrices and derivatives

Course 26.3·Lesson 1 of 3

Induction with binomials, matrices and derivatives

Induction proves results in algebra and calculus that hold for every whole number nnn. Pascal's rule carries the binomial theorem from nnn to n+1n + 1n+1

Lesson 1 of 3Show all lessonsHide
Induction in Algebra, Calculus and Olympiad Problems
  1. 1Induction with binomials, matrices and derivatives
  2. 2Flawed inductions: finding the error
  3. 3Induction in olympiad problems

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=0n(nr)an−rbr.\displaystyle (a + b)^n = \sum_{r = 0}^{n} \binom{n}{r} a^{n - r} b^r.(a+b)n=r=0∑n​(rn​)an−rbr.

Here is why it holds for every n≥1n \ge 1n≥1. The key is Pascal's rule: (kr−1)+(kr)=(k+1r)\dbinom{k}{r - 1} + \dbinom{k}{r} = \dbinom{k + 1}{r}(r−1k​)+(rk​)=(rk+1​) for 1≤r≤k1 \le r \le k1≤r≤k.

  1. Base case. For n=1n = 1n=1: (10)a+(11)b=a+b\dbinom{1}{0}a + \dbinom{1}{1}b = a + b(01​)a+(11​)b=a+b.
  2. Step. Assume the theorem for n=kn = kn=k. Multiply both sides by (a+b)(a + b)(a+b). The term ak+1−rbra^{k + 1 - r}b^rak+1−rbr appears twice: once from (kr)ak−rbr×a\dbinom{k}{r}a^{k - r}b^r \times a(rk​)ak−rbr×a and once from (kr−1)ak+1−rbr−1×b\dbinom{k}{r - 1}a^{k + 1 - r}b^{r - 1} \times b(r−1k​)ak+1−rbr−1×b.
  3. Its coefficient is (kr)+(kr−1)=(k+1r)\dbinom{k}{r} + \dbinom{k}{r - 1} = \dbinom{k + 1}{r}(rk​)+(r−1k​)=(rk+1​), by Pascal's rule. The first and last terms are ak+1a^{k + 1}ak+1 and bk+1b^{k + 1}bk+1.

So the theorem holds for k+1k + 1k+1, and by induction for every n≥1n \ge 1n≥1.

Powers of a matrix

To find AnA^nAn, work out A2A^2A2 and A3A^3A3, guess the pattern and prove it with Ak+1=AkAA^{k + 1} = A^k AAk+1=AkA.

Example. Let $A =

(1101)\displaystyle \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}(10​11​)

.Then. Then .ThenA² =

(1201)\displaystyle \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}(10​21​)

and and andA³ =

(1301)\displaystyle \begin{pmatrix} 1 & 3 \\ 0 & 1 \end{pmatrix}(10​31​)

.Weguess. We guess .WeguessA^n =

(1n01)\displaystyle \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}(10​n1​)

$. The step is one multiplication:

(1k01)(1101)=(1k+101).\displaystyle \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & k + 1 \\ 0 & 1 \end{pmatrix}.(10​k1​)(10​11​)=(10​k+11​).

A harder one. Let $B =

(3−41−1)\displaystyle \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}(31​−4−1​)

$. A classic exercise proves

Bn=(1+2n−4nn1−2n).\displaystyle B^n = \begin{pmatrix} 1 + 2n & -4n \\ n & 1 - 2n \end{pmatrix}.Bn=(1+2nn​−4n1−2n​).

Check n=1n = 1n=1: it gives BBB. For the step, multiply the formula for kkk by BBB. The top-left entry is 3(1+2k)−4k=1+2(k+1)3(1 + 2k) - 4k = 1 + 2(k + 1)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. dndxn(xex)=(x+n)ex\dfrac{d^n}{dx^n}\big(xe^x\big) = (x + n)e^xdxndn​(xex)=(x+n)ex. For n=1n = 1n=1 the product rule gives ex+xex=(x+1)exe^x + xe^x = (x + 1)e^xex+xex=(x+1)ex. If the formula holds for kkk, differentiate (x+k)ex(x + k)e^x(x+k)ex: the result is ex+(x+k)ex=(x+k+1)exe^x + (x + k)e^x = (x + k + 1)e^xex+(x+k)ex=(x+k+1)ex.

Example 2. dndxnsin⁡x=sin⁡(x+nπ2)\dfrac{d^n}{dx^n}\sin x = \sin\left(x + \dfrac{n\pi}{2}\right)dxndn​sinx=sin(x+2nπ​). For n=1n = 1n=1: cos⁡x=sin⁡(x+π2)\cos x = \sin\left(x + \dfrac{\pi}{2}\right)cosx=sin(x+2π​). The step: the derivative of sin⁡(x+kπ2)\sin\left(x + \dfrac{k\pi}{2}\right)sin(x+2kπ​) is cos⁡(x+kπ2)=sin⁡(x+(k+1)π2)\cos\left(x + \dfrac{k\pi}{2}\right) = \sin\left(x + \dfrac{(k + 1)\pi}{2}\right)cos(x+2kπ​)=sin(x+2(k+1)π​).

Example 3. dndxn(11+x)=(−1)nn!(1+x)n+1\dfrac{d^n}{dx^n}\left(\dfrac{1}{1 + x}\right) = \dfrac{(-1)^n n!}{(1 + x)^{n + 1}}dxndn​(1+x1​)=(1+x)n+1(−1)nn!​. The step differentiates (1+x)−(k+1)(1 + x)^{-(k + 1)}(1+x)−(k+1), which brings down −(k+1)-(k + 1)−(k+1).

De Moivre's theorem

For every whole number n≥1n \ge 1n≥1,

(cos⁡θ+isin⁡θ)n=cos⁡nθ+isin⁡nθ.\displaystyle (\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta.(cosθ+isinθ)n=cosnθ+isinnθ.

For the step, multiply cos⁡kθ+isin⁡kθ\cos k\theta + i\sin k\thetacoskθ+isinkθ by cos⁡θ+isin⁡θ\cos\theta + i\sin\thetacosθ+isinθ. The real part is cos⁡kθcos⁡θ−sin⁡kθsin⁡θ=cos⁡(k+1)θ\cos k\theta\cos\theta - \sin k\theta\sin\theta = \cos(k + 1)\thetacoskθcosθ−sinkθsinθ=cos(k+1)θ. The imaginary part is sin⁡kθcos⁡θ+cos⁡kθsin⁡θ=sin⁡(k+1)θ\sin k\theta\cos\theta + \cos k\theta\sin\theta = \sin(k + 1)\thetasinkθ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=kn = kn=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 BBB to the powers 111 to 666 and compares each with the formula. Then sympy differentiates xexxe^xxex five times.

Read it first. Then run it. Does every row say True? Do the derivatives follow the pattern (x+n)ex(x + n)e^x(x+n)ex?

1. Change B to [[1, 2], [0, 1]] and the formula to [[1, 2 * n], [0, 1]]. Does it still match?

2. Change x * sp.exp(x) to x * sp.exp(3 * x). Guess the pattern from the printed derivatives.

Common mistakes

  • Raising entries to a power. AnA^nAn is not the matrix of the entries to the power nnn.
  • Multiplying in the wrong order. AkAA^kAAkA and AAkAA^kAAk are equal for powers of one matrix, but keep one order in a proof.
  • Forgetting the product rule. The derivative of (x+k)ex(x + k)e^x(x+k)ex has two terms.
  • Skipping the end terms. In the binomial step, ak+1a^{k + 1}ak+1 and bk+1b^{k + 1}bk+1 come from one product each.

Remember these

  • Pascal's rule carries the binomial theorem from kkk to k+1k + 1k+1.
  • Matrix powers: guess from A2A^2A2 and A3A^3A3, prove with Ak+1=AkAA^{k + 1} = A^kAAk+1=AkA.
  • nth derivatives: differentiate the formula for kkk once more.
  • De Moivre: (cos⁡θ+isin⁡θ)n=cos⁡nθ+isin⁡nθ(\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta(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.

  1. Guess CnC^nCn for $C =
(2003)\displaystyle \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}(20​03​)

$ and prove the step.

(2n003n)\displaystyle \begin{pmatrix} 2^n & 0 \\ 0 & 3^n \end{pmatrix}(2n0​03n​)

.Step:multiplyby. Step: multiply by .Step:multiplybyCtoget to get toget2^{k + 1}and and and3^{k + 1}$ on the diagonal.

  1. Check the bottom-right entry of Bk+1B^{k + 1}Bk+1 for $B =
(3−41−1)\displaystyle \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}(31​−4−1​)

$.

  1. Find dndxne2x\dfrac{d^n}{dx^n}e^{2x}dxndn​e2x and prove the step.
  1. Use De Moivre's theorem to find (cos⁡θ+isin⁡θ)4(\cos\theta + i\sin\theta)^4(cosθ+isinθ)4 when θ=π8\theta = \dfrac{\pi}{8}θ=8π​.
  1. What is the fourth derivative of sin⁡x\sin xsinx at x=0x = 0x=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.
No payment. You can leave at any time.

Problems (4)

Let A = 2, 1; 0, 2. A computer prints A² = 4, 4; 0, 4 and A³ = 8, 12; 0, 8…Hard · High School (11–12) · by StemPy Lab
A function is f(x) = xe²ˣ. A student writes the first derivatives: f'(x) = (2x + 1)e²ˣ and f''(x) =…Advanced · High School (11–12) · by StemPy Lab
Let z = cosπ/12 + i sinπ/12. Prove De Moivre's theorem, (cosθ + i sinθ)ⁿ = cos nθ + i sin nθ, by…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2Flawed inductions: finding the error
← Induction in Algebra, Calculus and Olympiad Problems
← PreviousFlawed inductions: finding the error →

Discussion (0)

Log in to join the discussion.

Loading…

. A matrix power
AnA^nAn
is found by guessing from
A2A^2A2
and
A3A^3A3
and proving with
Ak+1=AkAA^{k + 1} = A^k AAk+1=AkA
. The nth derivative of a function is proved by differentiating the formula for
kkk
once more. De Moivre's theorem is proved the same way.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

In Pascal's triangle, start at (n, 0) and walk down a diagonal: (n, 0), (n + 1, 1), (n + 2, 2), ……Hard · High School (11–12) · by StemPy Lab

Python Labs (1)

Matrix powers against a formulaPython Lab · by StemPy Lab