2
$\begingroup$

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.

3 Answers 3

3

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

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

  • 0
    Do you put $k$ lines that are parallel in your answer?2012-12-21
  • 0
    @Maya: I **started** with $k$ parallel lines and then added non-parallel lines one by one.2012-12-21
  • 0
    But i think that answer should be $R_n=R_{n-1}+n - $something?2012-12-21
  • 0
    @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$.2012-12-21
0

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.

  • 0
    thanks, can you explain more how to get recurrence relation ? I don not know how to get recurrence relation? I need the algorithm.2012-12-21
  • 0
    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.2012-12-21
  • 0
    @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$.2012-12-21
  • 0
    @BrianM.Scott can you recommend links about this subject?2012-12-21
  • 0
    @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.)2012-12-21
0

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