Guess, Then Prove

In one sentence

For a problem about a positive integer $n$ , the answer is often not given in the question. Then:

compute: work out the cases $n = 1, 2, 3, \dots$ honestly;
guess: look at the data and guess the general formula, by analogy and by trial;
prove: prove the guess by mathematical induction.

The first two steps are discovery; the third is proof. A guess you cannot prove is only a conjecture.

Example: a₁ = 1/2, aₙ₊₁ = 1/(2 − aₙ). Find the general term

Step 1 / 6

Compute the first term
$a_{1} = \frac{1}{2}$ . With one term you cannot see anything.
Two more terms
Guess
Prove: base case
Prove: inductive step
Conclusion

Predict first

Join $n$ points on a circle by all possible chords (no three chords through one point). For $n = 1, 2, 3, 4, 5$ the disc is cut into $1, 2, 4, 8, 16$ regions. How many regions for $n = 6$ ?

regions

Choose an answer first; then you can see the result.

Stop 1 · Recursive sequences: guess the general term

A recurrence tells you “how the next term comes from this one”, which is exactly what the inductive step needs. So for recursive sequences, “guess, then prove” almost always works: once the guess is right, the proof is just substituting it into the recurrence.

a_{1} = 1

a_{n + 1} = 2 a_{n} + 1

. Hint: add

1

to each term. Once you have a guess, the inductive step is

2 (2^{k} - 1) + 1 = 2^{k + 1} - 1

Stop 2 · Sums: guess the degree, then the coefficients

$S_{n} = 1 \cdot 2 + 2 \cdot 3 + \dots + n (n + 1)$ . Each added term is quadratic in $n$ , so guess that $S_{n}$ is a cubic polynomial — just as $1 + 2 + \dots + n$ (adding linear terms) is quadratic.

The data are

2, 8, 20, 40, \dots

. Try dividing each term by

n

and look again.

One problem, several solutions

Find $S_{n} = 1 \cdot 2 + 2 \cdot 3 + \dots + n (n + 1)$ .

Guess + induction

$\frac{S _{n}}{n} = 2, 4, \frac{20}{3}, 10, \dots$ ; times $3$ that is $6, 12, 20, 30$ , which is exactly $(n + 1) (n + 2)$ . Guess $S_{n} = \frac{n ( n + 1 ) ( n + 2 )}{3}$ .

Inductive step: $\frac{k ( k + 1 ) ( k + 2 )}{3} + (k + 1) (k + 2) = \frac{( k + 1 ) ( k + 2 ) ( k + 3 )}{3}$ .

CostYou need a guess first; with a guess, the proof is one line of algebra.

Telescoping

$k (k + 1) = \frac{1}{3} [k (k + 1) (k + 2) - (k - 1) k (k + 1)]$ . Add from $k = 1$ to $n$ : everything in the middle cancels, leaving $\frac{1}{3} n (n + 1) (n + 2)$ .

CostNo guessing, but you must think of this way of splitting the term.

Stop 3 · Products: guess a fraction

$P_{n} = (1 - \frac{1}{2 ^{2}}) (1 - \frac{1}{3 ^{2}}) \dots (1 - \frac{1}{n ^{2}})$ , $n \geq 2$ .

\frac{3}{4}, \frac{2}{3}, \frac{5}{8}, \dots

— try writing

\frac{2}{3}

\frac{4}{6}

Once you have guessed $P_{n} = \frac{n + 1}{2 n}$ , the inductive step is $\frac{k + 1}{2 k} \cdot \frac{( k + 1 ) ^{2} - 1}{( k + 1 ) ^{2}} = \frac{k + 1}{2 k} \cdot \frac{k ( k + 2 )}{( k + 1 ) ^{2}} = \frac{k + 2}{2 ( k + 1 )}$ .

Guessing without proving

Break it

Counterexample lab: remove one condition

Conclusion: It holds for every $n$

$a_{n} = \frac{n}{n + 1}$ has a base case and an inductive step: however many terms you test, it never fails.

Practice

Exercise 1Basic

$a_{1} = 1$ , $a_{n + 1} = \frac{a _{n}}{1 + a _{n}}$ . Find $a_{10}$ .

Exercise 2Basic

Compute $1 + 3 + 5 + \dots + 39$ .

Exercise 3Advanced

$a_{1} = 2$ , $a_{n + 1} = 2 - \frac{1}{a _{n}}$ . Find $a_{20}$ .

Exercise 4Challenge

Find $1 \cdot 1! + 2 \cdot 2! + \dots + n \cdot n!$ and prove your answer.

In one sentence

Example: a₁ = 1/2, aₙ₊₁ = 1/(2 − aₙ). Find the general term

Stop 1 · Recursive sequences: guess the general term

Stop 2 · Sums: guess the degree, then the coefficients

Guess + induction

Telescoping

Stop 3 · Products: guess a fraction

Guessing without proving

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Checking five cases and calling it a proof

Secretly using the formula you are proving