Simple Proofs By Induction

The simplest prrof by induction involve finding a simple formula for the nth term of a sequence.

Proofs by induction have three parts.

1. Asumeis true. Oftenor 1 so we are assumingorcould be the statement that the nth term of a sequence is some formula for that nth term – for example, the nth even number issois the statement that the first even number is 2.

2. Assumeis true for some

3. Proveis true.

For the simple example above,

is true since the first even number is 2.

Ifis true then the nth even number is

Given an even number, to find the succeeding even number, add 2, so the (n+1)th even number isso thatis true.

Example: Prove that the sum of the firstnumbers is

is the statement that the sum of the first 1 numbers is 1. Obviously this is true. Substituteinto (1) to givesois true.

Assumeis true for someso that the sum of the first n numbers is

The (n+1)th number isWe can add this to the sum of the firstnumbers to get the sum of the firstnumbers.

The statementis the statement that the sum of the firstnumbers isso thatis true.