Mathematical Induction Notes

Mathematical Induction

Mathematical induction is a method of proof used to demonstrate that a statement is true for all natural numbers in a sequence.

Core Concept

If a statement is proven true for one instance in a sequence and it can be shown that if it's true for one instance, it is also true for the next consecutive instance, then the statement is true for all instances in that sequence.

Example Sequence

Consider the sequence:

1+3=41 + 3 = 4
3+5=83 + 5 = 8
5+7=125 + 7 = 12
7+9=167 + 9 = 16

Observation: The sum of any two consecutive odd numbers is a multiple of 4.

Mathematical Induction Steps

  1. Propose the statement: Clearly define the statement to be proven.

  2. Basis of Induction: Show that the statement is true for a simple case, typically n=1n = 1.

  3. Inductive Hypothesis: Assume that the statement is true for the case n=kn = k.

  4. Inductive Step: Prove that the statement is true for the case n=k+1n = k + 1, using the assumptions and foundations established in the basis of induction and inductive hypothesis.

  5. State the conclusion: Summarize that the statement is true for all nn based on the principle of mathematical induction.

Example Proof: Sum of Consecutive Odd Numbers

Statement: The sum of any two consecutive odd numbers is a multiple of 4.

Basis of Induction (n = 1):

1+3=4=4(1)1 + 3 = 4 = 4(1)

The statement holds true for n=1n = 1.

Inductive Hypothesis (Assume true for n = k):

Assume that (2k+1)+[2(k+1)+1]=4m(2k + 1) + [2(k + 1) + 1] = 4m, where mm is some natural number.

Inductive Step (Show true for n = k + 1):

[2(k+1)+1]+[2(k+2)+1]=2k+2+1+2k+4+1=4k+8=4(k+2)[2(k + 1) + 1] + [2(k + 2) + 1] = 2k + 2 + 1 + 2k + 4 + 1 = 4k + 8 = 4(k + 2)

Since k+2k + 2 is a natural number, 4(k+2)4(k + 2) is a multiple of 4. Thus, the statement holds true for n=k+1n = k + 1.

Conclusion:

The sum of any two consecutive odd numbers is a multiple of 4.

Example Proof: Series Summation

Prove that for all positive natural numbers nn:

12+14+18+…+12n=1−12n\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + … + \frac{1}{2^n} = 1 - \frac{1}{2^n}

Basis of Induction (n = 1):

12=1−121=12\frac{1}{2} = 1 - \frac{1}{2^1} = \frac{1}{2}

Inductive Hypothesis (Assume true for n = k):

Assume that 12+14+18+…+12k=1−12k\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + … + \frac{1}{2^k} = 1 - \frac{1}{2^k} is true for some natural number kk.

Inductive Step (Show true for n = k + 1):

12+14+18+…+12k+12k+1=(1−12k)+12k+1=1−22k+1+12k+1=1−12k+1\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + … + \frac{1}{2^k} + \frac{1}{2^{k+1}} = (1 - \frac{1}{2^k}) + \frac{1}{2^{k+1}} = 1 - \frac{2}{2^{k+1}} + \frac{1}{2^{k+1}} = 1 - \frac{1}{2^{k+1}}

Conclusion:

Therefore, for all positive natural numbers nn, 12+14+18+…+12n=1−12n\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + … + \frac{1}{2^n} = 1 - \frac{1}{2^n}.

Generalized Induction

  1. Formulate the statement: Clearly define the statement to be proven by induction.

  2. Show that there is at least one value of the natural numbers, nn, for which the statement is true.

  3. Assume it is true for any natural number mm, greater than or equal to nn.

  4. Show it must be true for the next value, m+1m+1.

Then, by induction, it is proven that the statement is true for all natural numbers greater than or equal to nn. Note that the initial case nn need not be 1.

/