Induction proofs

Question

Exercise 2.25: P(n) is the number of regions in the plane formed by n lines in general position: n=1, p(n)=2; n=2, p(n)=4; n=3, p(n)=7; n=4, p(n)=11; n=5, p(n)=16; n=6, p(n)=22.

2.76) Finish the process begun in 2.25, where it's outlined how experimentation might lead to the conjecture that n line in general position divide the plane into p(n) pieces, with p(1)=2 and p(n) = p(n-1)+n for n>=2. First write down the details of the induction argument; then write the work in theorem-proof style that suitable for others to read.

2.87) prove that p(n)=n^2+n+2/2 is a non-recursive solution to the lines in the plane problem of 2.25 and 2.76.

Answer 1

Proof by induction setup:

---------------------------

p(1) = 2

p(2) = 4

p(3) = 7

p(4) = 11

 

Clearly  p(n) = p(n-1) + n    for  2≤n≤4   (we don't need this many but its nice to see the pattern)

 

Induction Hypothesis:

Assume  p(k) = p(k-1) + k     for n=k    (1)

 

What we need to show:

p(k+1) = p(k) + (k+1)      (2)

 

If it can be shown that (2) follows from (1) then it can be said that

p(n) = p(n-1) + n    for  n≥2

 

That's the setup portion

=============================

 

Carrying out the proof:

Let n=k+1.   

 

Temporarily remove one line.   That leaves p(k) regions with k lines.  

 

Redraw the (k+1)'th line in segments.

The first segment goes from  -∞ until it hits line #1.  That splits some region in two, thereby adding one new region.

The next segment goes from line #1 to line #2.  That again splits some region in two, thereby adding one more new region.

...

The penultimate segment goes from line #(k-1) to line #k.  Again adding one more new region.

The final segment goes from line #k to +∞.  Adding one more new region.

 

Thus, adding the (k+1)'th line  adds  k+1 new regions.

 

Therefore,   p(k+1) = p(k) + (k+1)   and therefore (by letting n=k+1):   p(n) = p(n-1) + n   for  n≥2

 

 

=====================================

 

Closed form solution:   p(n) = (n²+n+2)/2     (please note you should provide parenthesis to make your equations accurate) 

 

This *can* be done by induction but I did it directly:

 

p(n) = p(n-1) + n

       = p(n-2) + (n-1) + n

       = p(n-3) + (n-2) + (n-1) + n

  ….

       = 1 + (1 + 2 + 3 + … + (n-2) + (n-1) + n)

 

There are n terms for p(1) … p(n) and the 1 outside the parenthesis counts the case of no lines (before drawing any lines at all, we have one undivided planar region).

 

 

Using (1+2+…+n) = n(n+1)/2:

  p(n) = 1 + n(n+1)/2      

  p(n) = 1 + (n²+n)/2 

  p(n) = (n²+n+2)/2