#22 Mathematical Induction



Mathematical Induction Video Lecture


Mathematical induction is explained in video and well as the examples are solved in very easy way in the notes below:

Let’s begin with an example.

Example: A Sum Formula

Theore. For any positive integer n, 1 + 2 + … + n = n(n+1)/2.

Proof. (Proof by Mathematical Induction) Let’s let P(n) be the statement “1 + 2 + … + n = (n (n+1)/2.” (The idea is that P(n) should be an assertion that for any n is verifiably either true or false.) The proof will now proceed in two steps: the initial step and the inductive step.

Initial Step. We must verify that P(1) is True. P(1) asserts “1 = 1(2)/2”, which is clearly true. So we are done with the initial step.

Inductive Step. Here we must prove the following assertion: “If there is a k such that P(k) is true, then (for this same k) P(k+1) is true.” Thus, we assume there is a k such that 1 + 2 + … + k = k (k+1)/2. (We call this the inductive assumption.) We must prove, for this same k, the formula 1 + 2 + … + k + (k+1) = (k+1)(k+2)/2.

This is not too hard: 1 + 2 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2 (k+1))/2 = (k+1)(k+2)/2. The first equality is a consequence of the inductive assumption.


The Math Induction Strategy

Mathematical Induction works like this: Suppose you want to prove a theorem in the form “For all integers n greater than equal to a, P(n) is true”. P(n) must be an assertion that we wish to be true for all n = a, a+1, …; like a formula. You first verify the initial step. That is, you must verify that P(a) is true. Next comes the inductive step. Here you must prove “If there is a k, greater than or equal to a, for which P(k) is true, then for this same k, P(k+1) is true.”

Since you have verified P(a), it follows from the inductive step that P(a+1) is true, and hence, P(a+2) is true, and hence P(a+3) is true, and so on. In this way the theorem has been proved.

Example: A Recurrence Formula

Math induction is of no use for deriving formulas. But it is a good way to prove the validity of a formula that you might think is true. Recurrence formulas are notoriously difficult to derive, but easy to prove valid once you have them. For example, consider the sequence a0, a1, a2, … defined by a0 = 1/4 and an+1 = 2 an(1-an) for n ≥ 0.

Theorem. A formula for the sequence an defined above, is an = (1 – 1/22n)/2 for all n greater than or equal to 0.

Proof. (By Mathematical Induction.)

Initial Step. When n = 0, the formula gives us (1 – 1/22n)/2 = (1 – 1/2)/2 = 1/4 = a0. So the closed form formula ives us the correct answer when n = 0.

Inductive Step. Our inductive assumption is: Assume there is a k, greater than or equal to zero, such that ak = (1 – 1/22k)/2. We must prove the formula is true for n = k+1.

First we appeal to the recurrsive definition of ak+1 = 2 ak(1-ak). Next, we invoke the inductive assumption, for this k, to get

ak+1 = 2 (1 – 1/22k)/2 (1 – (1 – 1/22k)/2) = (1 – 1/22k)(1 + 1/22k)/2 = (1 – 1/22k+1)/2. This completes the inductive step.



Prove each of the following by Mathematical Induction.

  1. For all positive integers n, 12 + 22 + … + n2 = (n)(n+1)(2n+1)/6.
  2. Define a sequence a0, a1, a2 by the recurrsive formula an+1 = 2 an – an2. Then, a closed form formula for an is an = 1 – (1 – a0)2n for all n = 0, 1, 2, ….
Buying essays online is safe, it makes our writers enjoy their work and also changes students’ lives for the better. Have fun with your friends, enjoy outdoor activities with your family or work on new projects – BuyEssayFriend allows for multitasking and gives you an opportunity to set priorities. Sometimes, you may lack the inspiration to end another piece of paperwork and you might forget something about your assignment. If you wake up thinking “I need an essay ASAP!” – there’s no need to check a Dream Book! Our top essay writing service can find a way to provide you with papers – professional writers can do it!best essay writing service. Our quizlets will also use this information to reach you to clarify any questions regarding your order, if necessary. To learn additional information about your privacy please view our Privacy Policy page here.