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
  1. Notes
  2. /Induction in Algebra, Calculus and Olympiad Problems: Quick Revision
Mathematics

Induction in Algebra, Calculus and Olympiad Problems: Quick Revision

A brief note on induction with matrices, derivatives and the binomial theorem, on flawed proofs, and on olympiad problems with boards, lines and towers. With practice, a program and questions.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Induction in Algebra, Calculus and Olympiad Problems. Read it before a test. Try each question at the end before you open its answer.

Algebra and calculus

  • Binomial theorem: the step uses Pascal's rule (kr−1)+(kr)=(k+1r)\binom{k}{r - 1} + \binom{k}{r} = \binom{k + 1}{r}(r−1k​)+(rk​)=(rk+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. Example: dndxn(xex)=(x+n)ex\dfrac{d^n}{dx^n}(xe^x) = (x + n)e^xdxndn​(xex)=(x+n)ex.
  • 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θ.

Flawed proofs: the checklist

  • A true base case? A working step alone proves nothing.
  • Does the step work for the smallest kkk? The horses fail from 111 to 222.
  • Enough base cases for a step that looks back further?
  • Does the step end at P(k+1)P(k + 1)P(k+1) rather than start from it?
  • A pattern is not a proof: points on a circle give 1,2,4,8,16,311, 2, 4, 8, 16, 311,2,4,8,16,31.

Olympiad tools

  • L-shaped tiling: four quarters and one piece in the middle; 4n−13\dfrac{4^n - 1}{3}34n−1​ pieces.
  • Lines: line kkk adds kkk regions, so n2+n+22\dfrac{n^2 + n + 2}{2}2n2+n+2​ in all.
  • Tower of Hanoi: H(n)=2H(n−1)+1=2n−1H(n) = 2H(n - 1) + 1 = 2^n - 1H(n)=2H(n−1)+1=2n−1.
  • Stuck step: strengthen the claim, or induct on another quantity.

Practice with new numbers

A program to try

The program tests a matrix power formula and prints two region counts.

Read it first. Then run it. Where does the circle count stop doubling?

1. Change A to [[1, 2], [0, 1]] and the formula to [[1, 2 * n], [0, 1]]. Does it still say True?

Mistakes to avoid

  • Raising each entry of a matrix to the power nnn.
  • Dropping a term of the product rule.
  • Trusting a step without testing it at the smallest kkk.
  • Believing a pattern from five cases.

Check yourself

  1. What is the top-right entry of $
(1201)\displaystyle \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}(10​21​)

^{7}$?

  1. What is the third derivative of xexxe^xxex?
  1. How many L-shaped pieces cover an 8×88 \times 88×8 board with one square removed?
  1. How many moves does the Tower of Hanoi need for 333 discs?

Sources

  • Arthur Engel, Problem-Solving Strategies, Chapter 8.
  • Richard Hammack, Book of Proof, Chapter 10.
← All Notes
← Strong Induction, Inequalities and Recursion: Quick RevisionDivision, Divisibility Rules and Primes: Quick Revision →
More onMathematical Induction

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. Algebra and calculus
  2. Flawed proofs: the checklist
  3. Olympiad tools
  4. Practice with new numbers
  5. A program to try
  6. Mistakes to avoid
  7. Check yourself
  8. Sources

Goes with the lesson

  1. Induction in olympiad problemsInduction in Algebra, Calculus and Olympiad Problems

More notes on this topic

  1. Strong Induction, Inequalities and Recursion: Quick Revision
  2. Induction for Sums and Divisibility: Quick Revision
All notes on this topic →