- #1
Miranden
- 5
- 0
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!
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!