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 in olympiad problems

Course 26.3·Lesson 3 of 3

Induction in olympiad problems

Olympiad problems use induction on boards, lines, puzzles and games. Split a 2k+12^{k + 1}2k+1 board into four 2k2^k2k

Lesson 3 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

  • use induction on boards, lines and puzzles;
  • set up a recursion from the structure of a problem;
  • strengthen a statement so that the induction goes through.

Tiling a board with L-shaped pieces

An L-shaped piece covers three squares of a board: two in a row and one beside them. Take a 2n×2n2^n \times 2^n2n×2n board and remove any one square. Claim: the rest can always be covered by L-shaped pieces, with no overlaps.

  1. Base case. For n=1n = 1n=1, a 2×22 \times 22×2 board with one square removed is exactly one L-shaped piece.
  2. Step. Take a 2k+1×2k+12^{k + 1} \times 2^{k + 1}2k+1×2k+1 board with one square removed. Cut it into four 2k×2k2^k \times 2^k2k×2k quarters. The removed square is in one quarter.
  3. Put one L-shaped piece in the middle of the board so that it covers one square of each of the other three quarters, at their corners next to the centre.
  4. Now each quarter is a 2k×2k2^k \times 2^k2k×2k board with exactly one square taken. By the hypothesis, each can be tiled.

The number of pieces is 4n−13\dfrac{4^n - 1}{3}34n−1​, because each piece covers 333 of the 4n−14^n - 14n−1 squares.

An 8 by 8 board with one square, in row 3 and column 6 counted from the top left, marked with a black cross as removed. The other 63 squares are covered by 21 L-shaped pieces of three squares, each piece in its own colour. Thick lines divide the board into four 4 by 4 quarters, and the L-shaped piece at the centre covers one corner square of each of the three quarters that do not hold the removed square.

Lines in the plane

Draw nnn lines, no two parallel and no three through one point. How many regions do they make? With 000 lines there is 111 region. Line number kkk crosses each of the k−1k - 1k−1 earlier lines once. The crossings cut it into kkk pieces, and each piece splits a region in two. So line kkk adds kkk regions:

R(k)=R(k−1)+k.\displaystyle R(k) = R(k - 1) + k.R(k)=R(k−1)+k.

Induction then gives R(n)=1+(1+2+⋯+n)=n2+n+22R(n) = 1 + (1 + 2 + \dots + n) = \dfrac{n^2 + n + 2}{2}R(n)=1+(1+2+⋯+n)=2n2+n+2​.

Four straight lines drawn across a square window, no two parallel and no three through one point. The regions they make are numbered 1 to 11. A caption says that the fourth line, drawn in red, crosses the three earlier lines and adds 4 regions.

A colouring. The regions made by any lines can be coloured black and white so that neighbours always differ. Add the lines one at a time. When a new line goes in, swap the two colours on one side of it and keep the other side. Neighbours along the new line now differ, and all old neighbours still differ.

The Tower of Hanoi

Three pegs, and nnn discs of different sizes on one peg, the largest at the bottom. A move takes the top disc of a peg to another peg, never onto a smaller disc. To move the whole tower:

  1. move the top n−1n - 1n−1 discs to the spare peg;
  2. move the largest disc;
  3. move the n−1n - 1n−1 discs on top of it.

So H(n)=2H(n−1)+1H(n) = 2H(n - 1) + 1H(n)=2H(n−1)+1 with H(1)=1H(1) = 1H(1)=1, and induction proves H(n)=2n−1H(n) = 2^n - 1H(n)=2n−1. Fewer moves are impossible: the largest disc must move at least once, and before that the other n−1n - 1n−1 discs must all leave it.

When the step fails, strengthen

Course 2 proved ∑1r2≤2−1n\sum \dfrac{1}{r^2} \le 2 - \dfrac{1}{n}∑r21​≤2−n1​, a stronger claim than "<2< 2<2". Olympiad problems often need this trick. Ask what extra fact would make the step work, and add it to the statement.

Another trick is to choose what to induct on. In a game you may induct on the number of coins, in a graph on the number of points, in a board on its side. Pick the quantity that gets smaller when you take one part of the problem away.

A third trick is forward and backward induction, used by Cauchy for the AM-GM inequality. Prove it for n=2n = 2n=2, then from nnn to 2n2n2n, which covers every power of 222. Then show that the case nnn gives the case n−1n - 1n−1. Together these reach every nnn.

Practise with new numbers

Try it in Python

The program tiles an 8×88 \times 88×8 board with one square removed, in the way the proof does, and prints the pieces with numbers. Then it counts the Hanoi moves by the recursion.

Read it first. Then run it. Does every number from 111 to 212121 appear exactly three times, in an L shape?

1. Change board[2][5] = -1 and the hole (2, 5) to another square, such as (7, 0). Does the tiling still work?

2. Change n = 3 to n = 4. How many pieces does the program use now? Check with 4n−13\dfrac{4^n - 1}{3}34n−1​.

Common mistakes

  • Losing the removed square. In the tiling step, the middle piece must avoid the quarter that already has the hole.
  • Counting crossings wrong. Line kkk crosses k−1k - 1k−1 lines and so adds kkk regions, not k−1k - 1k−1.
  • Proving only an upper bound. In Hanoi, also show that fewer moves are impossible.
  • Inducting on the wrong thing. Choose a quantity that gets smaller in the step.

Remember these

  • L-shaped tiling: cut into four quarters, one piece in the middle.
  • Lines: R(n)=n2+n+22R(n) = \dfrac{n^2 + n + 2}{2}R(n)=2n2+n+2​, since line kkk adds kkk regions.
  • Hanoi: H(n)=2n−1H(n) = 2^n - 1H(n)=2n−1.
  • If the step fails, strengthen the claim or change what you induct on.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. How many L-shaped pieces cover a 4×44 \times 44×4 board with one square removed?
  1. How many regions do 555 lines in general position make?
  1. Find H(4)H(4)H(4) from the recursion H(n)=2H(n−1)+1H(n) = 2H(n - 1) + 1H(n)=2H(n−1)+1 with H(1)=1H(1) = 1H(1)=1.
  1. Why does a 2n×2n2^n \times 2^n2n×2n board with no square removed never have an L-shaped tiling?
  1. In the colouring argument, why do two regions that meet along an old line still differ after the swap?

References

  • Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle.
  • Richard Hammack, Book of Proof, third edition, Chapter 10, Mathematical 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 (3)

An L-shaped piece covers three squares: two side by side and one more next to one of them…Advanced · High School (11–12) · by StemPy Lab
A designer draws n straight lines across a large sheet, no two parallel and no three through one…Advanced · High School (11–12) · by StemPy Lab
Let Pn = 1/2 × 3/4 × 5/6 × … × (2n - 1)/2n…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Induction in Algebra, Calculus and Olympiad Problems
← Flawed inductions: finding the errorNext →

Discussion (0)

Log in to join the discussion.

Loading…

boards and place one L-shaped piece in the middle. Add one line at a time to count regions. Move
n−1n - 1n−1
discs out of the way in the Tower of Hanoi. When the step fails, prove a stronger statement, or do induction on a different quantity.
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.

Python Labs (1)

The Tower of Hanoi, move by movePython Lab · by StemPy Lab

Question Sets (1)

Induction in Algebra and Olympiad Problems: Think It Through10 questions · by StemPy Lab

Notes (1)

Induction in Algebra, Calculus and Olympiad Problems: Quick RevisionNote · by StemPy Lab