# How to solve this recurrence problem?

problem:
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.

-

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.

\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

$$R_n=1+\frac12(n+k)(n-k+1)$$

for $n\ge k$.

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

-
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.

-
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
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}$$