Suppose I am trying to prove a theorem using Induction by proof. Usual induction proof by induction examples follow the following steps :
- First show that Base case is true, let's say P(0) is true
- Then Assume P(K) is true
- Then in the inductive step we start with P(K+1) and break it into P(K) + ( Some Things) else to show P(K) is true.
I am wondering can we do it the other way around. In the inductive step can we start from the P(K) and then we add something to the P(K) to make it P(K+1) by following the conditions of the proof. Then prove that the statement holds true for P(K+1).
For an example proof :
Let's take the Sylvester–Gallai theorem.
Given a finite set of points in Euclidian plane such that any line passing through two of the points shall pass through at least one more of them, then all points have to be collinear.
- First we show that P(3) is true, base case
- Induction Hypothesis P(K): Assumed for K set of points the statement holds. Every line passes through two points also pass through a third point in the set. K points are collinear.
- In the induction step I am adding an external point to set and making sure the added point follows the conditions to satisfy the SG theorem. That is for an external point in the same plane to pass through any line passing through two of the points in the K-points set in P(K), it has to pass through the line passing through all of them. Hence all K+1 points are collinear.K