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