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.
 A: 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$.
A: 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.
A: 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}$$
