Hi,(adsbygoogle = window.adsbygoogle || []).push({});

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**