There's a famous problem "How many regions n lines could make at most in euclidean plane?"
I solved it into below recurrent relation:
$r_n = 2(r_{n-1} - _{n-1}\mathbf C_2) + _{n-1}\mathbf C_2$
embeded intuition in above relation is simple.
Line makes 2 regions when meets one region.
however there's some region that my additional line doesn't meet :
which are they? the answer is the combinations of each line that my additional line has already met.
That's it.
But my problem is.. I don't know how to make this recurrence into formula.
I thought if the coefficient of each $r_n$, $r_{n-1}$ is different it's impossible, however, there's already exsiting formula for this region division.
Any theoretical ground about how to formularize the recurrence relation?
