Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Find the recurrence relation satisfied by $R_n$ , where $R_n$ is the number of regions that a plane is divided into by $n$ lines , such that There are $k$ lines among $n$ lines that are parallel to each other and no two of the $n-k$ lines are parallel,(no three of the lines go through the same point).

I get answer for "if no two of the $n$ lines are parallel" is : $R_n=R_{n-1}+n$
Can somebody help me?
Thank you.

share|cite|improve this question
up vote 2 down vote accepted

Suppose that you have $k$ parallel lines. Then we might as well consider $R_n$ only for $n\ge k$. Clearly $R_k=k+1$. Suppose that you have $n$ lines for some $n\ge k$, and you add a new line that is not parallel to any of the $n$ existing lines. It will cross each of those lines. In order to cross $n$ lines, it must pass through $n+1$ regions. (Why?) It cuts each of those $n$ regions in two, so it adds $n+1$ new regions. Thus, the recurrence is the same as in the case of no parallel lines: $R_{n+1}=R_n+n+1$, or, if you prefer, $R_n=R_{n-1}+n$. Only the initial value has changed.

Added: Specifically, you have

$$\begin{align*} &R_k=k+1\\ &R_n=R_{n-1}+n\quad\text{if }n>k\;. \end{align*}$$

You didn’t ask about getting a closed form for $R_n$, but that’s not too hard to do by very elementary techniques. Look at the first few values:

$$\begin{align*} R_k&=k+1\\ R_{k+1}=R_k+(k+1)&=(k+1)+(k+1)\\ R_{k+2}=R_{k+1}+(k+2)&=(k+1)+(k+1)+(k+2)\\ R_{k+3}=R_{k+2}+(k+3)&=(k+1)+(k+1)+(k+2)+(k+3)\;. \end{align*}$$

At this point it’s not hard to guess the general formula:

$$\begin{align*} R_{k+m}&=(k+1)+\sum_{i=1}^m(k+i)\\ &=k+1+\sum_{i=1}^mk+\sum_{i=1}^mi\\ &=k+1+km+\frac{m(m+1)}2\\ &=1+k(m+1)+\frac{m(m+1)}2\\ &=1+\frac12(m+2k)(m+1)\;. \end{align*}$$

Set $n=k+m$, and this becomes


for $n\ge k$.

To prove that the closed form is actually correct you would use induction on $n$ with base case $n=k$.

share|cite|improve this answer
Do you put $k$ lines that are parallel in your answer? – Maya Dec 21 '12 at 9:32
@Maya: I started with $k$ parallel lines and then added non-parallel lines one by one. – Brian M. Scott Dec 21 '12 at 9:40
But i think that answer should be $R_n=R_{n-1}+n - $something? – Maya Dec 21 '12 at 9:49
@Maya: Not if you’ve stated the problem correctly: once you have the $k$ parallel lines, each new line adds the same number of new regions as if there were no parallel lines. Draw some sketches, say with $2$ or $3$ parallel lines, and and you’ll see this. The only thing that changes is what happens when $n\le k$. – Brian M. Scott Dec 21 '12 at 9:56

You could guess the solution, then prove it is correct with mathematical induction or you could continue substituting in values iteratively until you find a pattern that you can solve. For example, see that $R_{n-1} = R_{n-2} + n - 1$, then plug that in, etc.

share|cite|improve this answer
thanks, can you explain more how to get recurrence relation ? I don not know how to get recurrence relation? I need the algorithm. – Maya Dec 21 '12 at 8:48
well with the given recurrence, you would need to reduce it down to a base case. When you iterate enough times, you can see a pattern such that the equation can be written as $R_i = $ something. Then you can plug in some value for i that gives you the base case. – Ken Dec 21 '12 at 8:54
@Maya: There really isn’t an algorithm in general. The details depend on the setting, and recurrence relations arise in a great variety of settings. Here you have two reasonable approaches. (1) Use reasoning similar to the no two lines parallel case. (2) Look at small examples for $k=2,3$, and $4$, say, to guess the recurrence for each of those, and then try to generalize to arbitrary $k$. – Brian M. Scott Dec 21 '12 at 8:56
@BrianM.Scott can you recommend links about this subject? – Maya Dec 21 '12 at 9:01
@Maya: I’m more familiar with books, but I might be able to find something helpful. What kind of mathematical background do you have at this point? (By the way, I added an answer.) – Brian M. Scott Dec 21 '12 at 9:05

we have recurrence $R_{n} = R_{n-1} + n $ if $n>0$,$R_0=0$ denote by $$s(x)=\sum_{n=1}^{\infty}R_nx^n$$ generating function $$s(x)=\sum_{n=1}^{\infty}R_nx^n=\sum_{n=1}^{\infty}(R_{n-1}+n)x^n=\sum_{n=1}^{\infty}nx^n+x\sum_{n=1}^{\infty}R_{n-1}x^{n-1}={x\over(1-x)^2}+xs(x)$$ $$s(x)={x\over(1-x)^3}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.