Take the 2-minute tour ×
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.

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.

share|improve this question
add comment

3 Answers

up vote 1 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

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

share|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
add comment

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.