Categories

How to do induction proofs

Proofs by Induction A proof by induction is just like an ordinary proof in which every step must be justified. However it employs a neat trick which allows you to prove a statement about an arbitrary number n by first proving it is true when n is 1 and then assuming it is true for n=k and showing it is true for n=k+1. The idea is that if you want to show that someone can climb to the nth floor of a fire escape, you need only show that you can climb the ladder up to the fire escape (n=1) and then show that you know how to climb the stairs from any level of the fire escape (n=k) to the next level (n=k+1).

If you’ve done proof by induction before you may have been asked to assume the n-1 case and show the n case, or assume the n case and show the n+1 case. This is the same as what I’m explaining here but I will use a different letter because I think it avoids some confusion when trying to figure out what each case is.

Example 1: Prove 1+2+. +n=n(n+1)/2 using a proof by induction.

n=1: 1=1(2)/2=1 checks.

Assume n=k holds: 1+2+. +k=k(k+1)/2 (Induction Hyypothesis)
Show n=k+1 holds: 1+2+. +k+(k+1)=(k+1)((k+1)+1)/2
I just substitute k and k+1 in the formula to get these lines. Notice that I write out what I want to prove.

Now I start with the left side of the equation I want to show and proceed using the induction hypothesis and algebra to reach the right side of the equation. 1+2+. +(k+1)=1+2+. +k+(k+1)
=k(k+1)/2 + (k+1) by the Induction Hypothesis
=(k(k+1)+2(k+1))/2 by 2/2=1 and distridution of division over addition
=(k+2)(k+1)/2 by distribution of multiplication over addition
=(k+1)(k+2)/2 by commutativity of multiplication

Example 2: Prove that if P1 P2. Pn are colinear points in a space satisfying the axioms of incidence and betweeness such that each Pj is between P(j-1) and P(j+1) for j=2. (n-1), then Pj is between P1 and Pn for any j=2. (n-1).

This is a different kind of proof by induction because it doesn’t make sense until n=3. So we start at n=3, and then show if n=k we get n=(k+1), thus proving the statement for n=3,4,5,6.

n=3: P2 is between P1 and P3 implies P2 is between P1 and P3. Done

Assume n=k: if P1 P2. Pk are colinear points such that each Pj is between P(j-1) and P(j+1) for j=2. (k-1), then Pj is between P1 and Pk for any j=2. (k-1). Induction Hypothesis.

Show n=k+1: if P1 P2. P(k+1) are colinear points such that each Pj is between P(j-1) and P(j+1) for j=2. k, then Pj is between P1 and P(k+1) for any j=2. (k).

The k points P1, P2. P(k-1) P(k+1) satisfy the conditions of the induction hypothesis so we know Pj is between P1 and P(k+1) for any j=2. (k-1).

The k points P1, P3, P4. Pk P(k+1) also satisfy the conditions of the induction hypothesis so we know Pj is between P1 and P(k+1) for any j=3. (k).

Example 3: Prove that any space satisfying the Axioms of Incidence and the Betweeness which contains a point has an infinite number of distinct colinear points.

If I can show that the space contains n points for any number n then it must have an infinite number of points. So I will do a proof by induction on the number of points, n.

n=1: Does the space contain at least one point? Yes it does by the hypothesis (“which contains a point”)

Assume we have found n=k colinear points (Induction Hypothesis)
Show we can find n=k+1 colinear points. We need only find one more point.

Now let us draw a picture. If we put all the points on a line then it is easy to add one more point on the end. To do this it is easier if the points are in order. In other words it would be easier to prove: any space satisfying the Axioms of Incidence and the Betweeness which contains a point has an infinite number of distinct colinear points P1, P2. such that each Pi is between P(i+1) and P(i-1) for i>1. So we will change our induction hypothesis.

Assume n=k:that we have n=k colinear points P1, P2. Pk such that P2 is between P1 and P3, P3 is between P4 and P2. P(k-1) is between P(k-2) and Pk. (New Induction Hypothesis)

Show n=k+1: that we have n=k+1 colinear points P1, P2. P(k+1) such that P2 is between P1 and P3, P3 is between P4 and P2. P(k) is between P(k-1) and P(k+1).

By the induction hypothesis we have k colinear points. We find the k+1 point using Axiom B2 which says that given B=P(1) and D=Pk we can find a new point E=P(k+1) such that Pk is between P(1) and P(k+1). *

Now we need to show P(k+1) is distinct from Pj for any j=1,2. k.

By Example 2,. we know that Pj is between P1 and Pk for j=2,3. k-1.*

However P(k) is between P1 and P(k+1) so by Axiom B3 P(k+1) cannot be Pj for j=2,3. k-1.

Since P(k+1) was already distince from P1 and Pk, we are done.

There are two mistakes in this proof! When we quoted Example 2, we could only do this if k was greater than or equal to 3! Also in the very first step we assume k was greater then or equal to 2! See the *’s in the proof.

We must then do these cases at the beginning in addition to n=1.

n=2: By Axiom I3, there exists three points which are not colinear. Let P1 and P2 be two of those points. These points are “in order” because there are only two of them.

n=3: By the n=2 case we know we have two colinear points P1 and P2. By Axiom B3 we can find P3 such that P2 is between P1 and P3. These are already in order just by Axiom B3.

Note that the space of one point with one line satisfies all the axioms of betweeness and incidence except I3, so it was necessary for us to use I3 in the n=2 step to prove this example.

1) Try to prove that if f(x)=5x+3 and g(x)=5(x-2) +8 then f(n)=g(n) by assuming it is true for n=k and showing it is true for n=k+1. What is wrong?

2) Prove that d/dx (x^n)=nx^(n-1) using the definition of derivative.

3) Prove that a space with n points whose lines are any pair of distinct points satisfies the axioms of incidence.

4) Prove that in a space satisfying the axioms of incidence and betweeness given two points A and B there are infinitely many points between them.