Help me understand the inductive solution to the lines in the plane problem?

Miranden

Hi,

This is my first post, but I'm not sure this is the right place for it. I am studying (independently, not in school) the lines in the plane problem that was originally solved by Jakob Steiner in 1826, which is a recurrence. The problem is to find the maximum number L[n] of regions defined by n lines in the plane. I will describe the problem, and then my difficulty.

The recurrence for this problem is derived by realizing that each line n can intersect the previous n - 1 lines in at most n - 1 places, thus dividing n old regions and increasing the number of regions by n. So if the new lines never go through any existing intersection point (so they always create a new point of intersection) and they are never parallel to any existing lines (and thus intersect all of them), we have the recurrence:

L[0] = 1;
L[n] = L[n-1] + n;

Now we "unwind" the recurrence, generating

L[n] = L[n - 1] + n

= L[n - 2] + (n - 1) + n
= L[n - 3] + (n - 2) + (n - 1) + n
. . .
= L[0] + S[n] {where S[n] is the sum of the first n numbers, the triangular numbers}

= 1 + S[n]

So since we have the triangular numbers, we know the solution should be L[n] = (n(n + 1)/2) + 1 {Because it is just the old Gauss trick about the triangular numbers, plus the 1}.


But we want to prove it by induction. And here is where I get messed up. All my book says is:

"The key induction step is

L[n] = L[n - 1] + n = ((1/2)(n -1) n + 1) + n = (1/2)n(n + 1) + 1.

Now there can be no doubt about the closed form {from the Gauss trick above}."

So what the heck is going on in that last part? I thought I understood induction, but I do not see how exactly it is being applied here. I would really appreciate a step-by-step explanation. Please help me understand this proof. Thank you!

Mandlebra

The n-1 l term is gotten by plugging in n-1 into your l(n) formula. The induction hypoth. guarantees that the previous terms obey the closed formula. So the right side of the last line you have there is the recurrence, then you plug in n-1, perform algebra, and rearrange the terms to have it look like l(n+1)

Miranden

Oh, I see now. After squinting at your post for a long while, I finally realized I had made an error in my algebra that was preventing me from getting from the middle part of the equation to the last part. It made it look like there was something mystical going on, but I guess it's pretty simple. Thank you, that was driving me crazy!