Start by reading the overview below to learn how proof by
induction works or to get a refresher.
Select a mode on the form below, then select a proof by
induction problem and click 'Start' to begin.
Modes:
Question: Perform the proof by induction yourself.
Example: Watch a proof by induction performed for the
chosen problem.
If you get stuck on a line in the proof, try the help
button [?]. It will display a help section specific to the
current part of the proof, and may have hints on what
you need to do next.
Hovering the mouse over a button will give a description
of what it does and how to use it.
The fastest way to master the interface is to open two
browser windows, one with a problem in 'Example' mode
and one with the same problem in 'Question' mode. By
going through the example step-by-step in one window,
you can try each step in the other window at the
same time.
Overview of Proof by Induction:
▽
Introduction
Proof by induction is a method used to prove a statement is
true for all natural numbers, or sometimes for all natural
numbers that are greater than some specific value.
The natural numbers are all positive integers: 1, 2, 3, 4,
5, 6, ..., ∞. Sometimes zero will also be included.
The components of a proof by induction are the
base case and the
induction step.
The induction step includes the
induction hypothesis and
induction claim.
Base Case
Let the statement to be proven be represented by (*).
As an example, in the course of this explanation we
will prove the following statement:
n
∑
i
=
1
(
2
i
)
=
2
(
n
+
1
)
−
2
(*)
for
all
n
>
0.
The first step in the proof is the base case. It involves
proving that (*) is true for the lowest possible value of
n, which we will call n0.
Usually the question will ask for the statement (*) to be
proven for all natural numbers, so for n0 = 0 or
n0 = 1.
Since this example asks for all n > 0, choose
n0 = 1.
If the question specifies another number, like asking you
to prove for n ≥ 5 or n > 3, then you just make
the base case n0 = 5 or n0 = 4
instead.
Once the value of the base case n0 has been
identified, the statement (*) must be proven true for
n = n0.
So we replace n with the number chosen for n0
in (*). Each side is then simplified until the truth of the
statement is trivial.
Left
side:
n0
∑
i
=
1
(
2
i
)
=
1
∑
i
=
1
(
2
i
)
=
2
1
=
2
.
Right
side:
2
(
n0
+
1
)
−
2
=
2
(
1
+
1
)
−
2
=
2
2
−
2
=
4
−
2
=
2
.
Since both sides are equal when n = n0, (*)
is true for the base case.
Inductive Step
We now assume that the statement (*) is known to be true
for all values of n up to some fixed number k, but is not
known to be true for any values of n greater than k.
So we replace n with k in (*) and assume this new statement
(**) to be true. This is called the induction hypothesis.
Assume
k
∑
i
=
1
(
2
i
)
=
2
(
k
+
1
)
−
2
(**)
is
true
for
all
n = n0, ..., k;
especially
n = k.
To complete the induction step, it must then be proven that
(*) is true for n = k + 1, using the induction hypothesis
(**).
We replace n with k + 1 in (*) and call this statement the
induction claim (***). Proving that (***) is true using the
induction hypothesis (**) is the goal of the induction step.
Then
prove
for
n = k + 1
that
k
+
1
∑
i
=
1
(
2
i
)
=
2
(
k
+
1
+
1
)
−
2
(***)
is
true
if
the
induction
hypothesis
is
true.
We start by rearranging the left side of (***) to contain
the left side of the induction hypothesis (**). This allows
us to use (**) for substitution.
k
+
1
∑
i
=
1
(
2
i
)
=
k
∑
i
=
1
(
2
i
)
+
2
(
k
+
1
)
.
Since the induction hypothesis (**) is assumed to be true,
each side of (**) can replace the other.
k
∑
i
=
1
(
2
i
)
+
2
(
k
+
1
)
=
2
(
k
+
1
)
−
2
+
2
(
k
+
1
)
by
the
induction
hypothesis.
The induction hypothesis (**) can be used repeatedly. It
must be cited whenever it is used in the proof!
In this way, the left side of the induction claim (***) is
transformed into the right side of (***).
2
(
k
+
1
)
−
2
+
2
(
k
+
1
)
=
2
*
2
(
k
+
1
)
−
2
=
2
(
k
+
1
+
1
)
−
2
,
which
is
the
right
side
of
the
claim
(***).
The induction step is now complete. We have proven that if
(*) is true when n is some natural number k, then (*) is
also true for n = k + 1.
Therefore
if
k
∑
i
=
1
(
2
i
)
=
2
(
k
+
1
)
−
2
is
true,
then
k
+
1
∑
i
=
1
(
2
i
)
=
2
(
k
+
1
+
1
)
−
2
is
true.
We already know from the base case that the statement (*)
is true for n = n0. Now, using the induction step,
we know that (*) must also be true for n = n0 + 1.
Since the statement (*) is true for n = n0 + 1, then
by the induction step it must also be true for n = n0
+ 2, and then for n = n0 + 3, and so on for all the
infinitely many natural numbers greater than n0.
So, using proof by induction, the original statement (*) is
shown to be true for all natural numbers greater than or
equal n0.
Therefore
n
∑
i
=
1
(
2
i
)
=
2
(
n
+
1
)
−
2
for
all
n > 0.
Further Comments
To show that two expressions A and B are equal, you need to
rearrange A into the form of B, B into the form of A, or
both A and B into the form of C. It will not prove anything
to start with A = B and derive an identity.
Example:
5 = -5
since
5
2
=
25
=
(-5)
2
.
Example:
1 = 2
since
1
*
0
=
0
=
2
*
0
.
Both conclusions are wrong.
Correct statements can be derived from incorrect
statements, but incorrect statements cannot be derived
from correct ones.
A variation of induction is
strong induction.
For some problems, to prove the induction claim for
n = k + 1 it is not enough to assume that the induction
hypothesis is true for n = k. Instead it needs to be
assumed true for all n = n0, ..., k.
The procedure is the same. After proving the
induction claim for n = k + 1, you
then know that if the statement is true for
n = n0, ..., k, it is also true for
n= n0, ..., k, (k + 1).
Not all problems require this more comprehensive form
of proof by induction. An example that does is the
proof that all positions in the game 'Chomp' are
either winning or losing positions, seen
here under
Some food for thought >
Some theorems and proofs
> Is it possible that there are
positions where neither side can enforce a win?
Proof by induction is not only applicable for formulas
with one parameter n, but also for formulas with multiple
parameters.
For example, a proof that the number of staircases
that are P steps high and Q steps wide is (P+Q)!/(P!Q!)
is given for the game 'Chomp'
here under
Some food for thought >
Some More Math Around Chomp
> How many different positions
... fit into a rectangle with P rows and Q columns?
> Proof of Explicit Formula by
Induction.
△
Mode:Problem:
01000.Sum of Integers.json|01005.Sum of (3i - 2).json|01010.Sum of Halves.json|01015.Sum of Squares.json|01016.Sum of Cubes.json|01020.Sum of Odd Integers.json|01025.Sum of Products of Sequential Integers.json|01030.Sum of Squares of Even Integers.json|01031.Sum of Squares of Odd Integers.json|01035.Sum of Squares with Alternating Signs.json|01050.Sum of Powers of Two.json|01051.Sum of Powers of Three.json|01052.Sum of Powers of Four.json|01054.Sum of (i + 1) (2 ^ i).json|01055.Geometric Series.json|01400.Sum of 1 over i (i + 1).json|01420.Sum of 1 over (2i - 1) (2i + 1).json|01500.Sum of 1, 2, ..., n, ..., 2, 1.json|02010.Product of Sequence of i over (i + 1).json|02020.Product of Sequence of (i - 1) over (i + 1).json|02050.Product of Sequence of (i^2 - 1) over (i^2).json|03006.Divisibility of (5^n - 2^n) by 3.json|03017.Divisibility of (7^n - 3^n) by 4.json|03020.Divisibility of (a^n - 1) by (a - 1).json|03021.Divisibility of (a^n - b^n) by (a - b).json|03022.Divisibility of (11^n - 6) by 5.json|03024.Divisibility of (n^2 - n) by 2.json|03025.Divisibility of (n^3 - n) by 3.json|03026.Divisibility of (n^3 + 2n) by 3.json|03030.Divisibility of ((2n - 1)^2 - 1) by 8.json|03033.Divisibility of (3^2n - 1) by 8.json|03035.Divisibility of (10^(n+1) + 10^n + 1) by 3.json|03040.Divisibility of (5^n + 2 (11^n)) by 3.json|03050.Divisibility of (n (n^2 +5)) by 3.json|03055.Divisibility of (n^3 + (n+1)^3 + (n+2)^3) by 9.json|03060.Divisibility of (2 ^ (2n) - 1) by 3.json|03065.Divisibility of (2^(n+2) + 3^(2n+1)) by 7.json|03070.Divisibility of (2 (n^3) + 3 (n^2) + n) by 6.json|03073.Divisibility of (3 (5^(2n+1)) + 2^(3n+1)) by 17.json|03075.Divisibility of (5^(2n + 1) + 2^(2n + 1)) by 7.json|04000.Sum of Fibonacci Terms.json|04001.Sum of Even Fibonacci Terms.json|04002.Sum of Odd Fibonacci Terms.json|04010.Sum of (Fibonacci(i) ^ 2).json|04050.Sum of (Fibonacci(i) ^ 2) (Fibonacci(i + 1)).json|04100.((Fibonacci(n+1)) (Fibonacci(n-1)) - Fibonacci(n)^2) Identity.json|
01000.Sum of Integers.json|01005.Sum of (3i - 2).json|01010.Sum of Halves.json|01015.Sum of Squares.json|01016.Sum of Cubes.json|01020.Sum of Odd Integers.json|01025.Sum of Products of Sequential Integers.json|01030.Sum of Squares of Even Integers.json|01031.Sum of Squares of Odd Integers.json|01035.Sum of Squares with Alternating Signs.json|01050.Sum of Powers of Two.json|01051.Sum of Powers of Three.json|01052.Sum of Powers of Four.json|01054.Sum of (i + 1) (2 ^ i).json|01055.Geometric Series.json|01400.Sum of 1 over i (i + 1).json|01420.Sum of 1 over (2i - 1) (2i + 1).json|01500.Sum of 1, 2, ..., n, ..., 2, 1.json|02010.Product of Sequence of i over (i + 1).json|02020.Product of Sequence of (i - 1) over (i + 1).json|02050.Product of Sequence of (i^2 - 1) over (i^2).json|03006.Divisibility of (5^n - 2^n) by 3.json|03017.Divisibility of (7^n - 3^n) by 4.json|03020.Divisibility of (a^n - 1) by (a - 1).json|03021.Divisibility of (a^n - b^n) by (a - b).json|03022.Divisibility of (11^n - 6) by 5.json|03024.Divisibility of (n^2 - n) by 2.json|03025.Divisibility of (n^3 - n) by 3.json|03026.Divisibility of (n^3 + 2n) by 3.json|03030.Divisibility of ((2n - 1)^2 - 1) by 8.json|03033.Divisibility of (3^2n - 1) by 8.json|03035.Divisibility of (10^(n+1) + 10^n + 1) by 3.json|03040.Divisibility of (5^n + 2 (11^n)) by 3.json|03050.Divisibility of (n (n^2 +5)) by 3.json|03055.Divisibility of (n^3 + (n+1)^3 + (n+2)^3) by 9.json|03060.Divisibility of (2 ^ (2n) - 1) by 3.json|03065.Divisibility of (2^(n+2) + 3^(2n+1)) by 7.json|03070.Divisibility of (2 (n^3) + 3 (n^2) + n) by 6.json|03073.Divisibility of (3 (5^(2n+1)) + 2^(3n+1)) by 17.json|03075.Divisibility of (5^(2n + 1) + 2^(2n + 1)) by 7.json|04000.Sum of Fibonacci Terms.json|04001.Sum of Even Fibonacci Terms.json|04002.Sum of Odd Fibonacci Terms.json|04010.Sum of (Fibonacci(i) ^ 2).json|04050.Sum of (Fibonacci(i) ^ 2) (Fibonacci(i + 1)).json|04100.((Fibonacci(n+1)) (Fibonacci(n-1)) - Fibonacci(n)^2) Identity.json|
Follow or subscribe for updates: