Using Proof by Induction

Understanding Proof by Induction

Proof by induction is a mathematical technique used primarily to prove a statement about any integer n is true for all values of n greater than or equal to some integer k.
The method involves two steps: the base step (base case) and the induction step.
During the base step, the statement is proven true for the initial value of n, typically n=1 or n=0.
In the induction step, the property is proven to hold true for n = k + 1 assuming it is true for n = k. This is often called the inductive hypothesis.

Role of Proof by Induction

The principle of induction is a significant tool in number theory and is frequently used in studying arithmetic and geometric sequences, divisibility, algebra, and more.
It’s a powerful method and offers a systematic way of proving otherwise complex mathematical concepts and theorems.
It helps us make mathematical statements for an infinite set of cases.

Applying Proof by Induction

Define the statement to be proven, and identify the initial integer value, typically denoted as k.
Prove the statement is true when n equals to your base case (k). This is sometimes referred to as the basis of induction.
Assume the statement is true for n=k. This is your inductive hypothesis.
Prove the statement under the assumption that it is true for n=k+1. This is often the hardest step, you may need to manipulate the equations and apply your inductive hypothesis.
Your proof is now complete! If you have shown the base case is true, and that true for n=k means it is true for n=k+1, you can state that it is true for all n greater than or equal to k.

Example

Prove by induction that 1 + 2 + 3 … + n = n(n + 1) / 2:

For the base case, when n = 1, the left side is equal to 1 and the right side is also equal to 1.

For the inductive step, assume the statement is true for n=k (1 + 2 + … + k = k(k + 1) / 2), then you need to show it remains true for n=k+1.

Adding k+1 to both sides of our inductive hypothesis gives us (1 + 2 + … + k + (k+1) = (k(k + 1) / 2) + k + 1), simplify the right side to get ((k+1)(k+2)/2). This confirms the original statement holds for n=k+1, which completes the proof.

Note: Always remember the process of induction - establish the base case, assume the property for n=k, and show it for n=k+1. Keep practising to get comfortable with the method!