2

$$r_n = 2\left(r_{n-1} - \binom{n-1}{2}\right) + \binom{n-1}{2}$$

which is equal to $$r_n - 2r_{n-1} = -\frac{n^2-3n+2}{2}$$

This given recurrence relation is derived from the question "How many regions line n could make at most in Euclidean plane?"

To solve this relation and make it into non-recurrent form,

I had looked in Wikipedia but I only get to the point of solving the homogeneous part only.

$r_n - 2r_{n-1} = 0$ gives $\alpha \cdot2^n$ as a solution of homogenous part.

How should one deal with non-homogeneous part?

rtybase
  • 16,907
Beverlie
  • 2,645

2 Answers2

1

Using generating functions $$f(x)=\sum\limits_{n=0}^{\infty}r_nx^n=r_0+r_1x+r_2x^2+\sum\limits_{n=3}^{\infty}r_nx^n=r_0+r_1x+r_2x^2+\sum\limits_{n=3}^{\infty}\left(2r_{n-1}-\binom{n-1}{2}\right)x^n=\\ r_0+r_1x+r_2x^2+2\left(\sum\limits_{n=3}^{\infty}r_{n-1}x^n\right)-\sum\limits_{n=3}^{\infty}\binom{n-1}{2}x^n=\\ r_0+r_1x+r_2x^2+2x\left(\sum\limits_{n=3}^{\infty}r_{n-1}x^{n-1}\right)-x^3\left(\sum\limits_{n=3}^{\infty}\binom{n-1}{2}x^{n-3}\right)=\\ r_0+r_1x+r_2x^2+2x\left(\sum\limits_{n=2}^{\infty}r_{n}x^{n}\right)-x^3\left(\sum\limits_{n=0}^{\infty}\binom{n+2}{2}x^{n}\right)=...$$ which is, according to this $$...=r_0+r_1x+r_2x^2+2x\left(f(x)-r_0-r_1x\right)-\frac{x^3}{(1-x)^3}$$ or $$f(x)=r_0+r_1x+r_2x^2+2xf(x)-2xr_0-2r_1x^2-\frac{x^3}{(1-x)^3}$$ $$f(x)(1-2x)=r_0(1-2x)+r_1x(1-2x)+r_2x^2-\frac{x^3}{(1-x)^3}$$ $$f(x)=r_0+r_1x+\frac{r_2x^2}{1-2x}-\frac{x^3}{(1-x)^3(1-2x)}$$ $$f(x)=r_0+r_1x+\frac{r_2x^2}{1-2x}-\left(\frac{1}{1-2x}-\frac{1}{1-x}+\frac{1}{(1-x)^2}-\frac{1}{(1-x)^3}\right)$$ $$f(x)=r_0+r_1x+r_2x^2\left(\sum\limits_{n=0}^{\infty}(2x)^{n}\right)-\left(\sum\limits_{n=0}^{\infty}(2x)^n\right)+\left(\sum\limits_{n=0}^{\infty}x^n\right)-\left(\sum\limits_{n=0}^{\infty}(n+1)x^n\right)+\left(\sum\limits_{n=0}^{\infty}\binom{n+2}{2}x^{n}\right)$$ Now, by comparing powers of $x$ we have $$r_0=r_0$$ $$r_1=r_1-2+1-2+\binom{3}{2}=r_1$$ $$r_2=r_2-4+1-3+\binom{4}{2}=r_2$$ $$r_3=2r_2-8+1-4+\binom{5}{2}=2r_2-1$$ $$...$$ $$r_n=2^{n-2}r_2-2^n+1-(n+1)+\binom{n+2}{2}$$ Or $$r_n=2^{n-2}r_2+\binom{n+2}{2}-2^n-n$$

Note I had to consider arbitrary $r_0, r_1, r_2$, especially $r_2$, to avoid troubles with $\binom{n-1}{2}$, which makes sense for $n\geq 3$.

rtybase
  • 16,907
0

By induction easy to prove that $$r_n=r_12^{n-1}+2^n-\frac{n^2+n+2}{2}.$$ Also, you can use the following telescopic sum, but it's very ugly, I think: $$r_n=2r_{n-1}+\frac{(n-2)(n-1)}{2}$$ $$2^1r_{n-1}=2^2r_{n-2}+2^1\cdot\frac{(n-2)(n-3)}{2}$$ $$2^2r_{n-2}=2^3r_{n-3}+2^2\cdot\frac{(n-3)(n-4)}{2}$$ $$.$$ $$.$$ $$.$$

Michael Rozenberg
  • 194,933
  • You have a tiny typo $r_n=2r_{n-1}-...$ – rtybase Sep 13 '17 at 11:15
  • @rtybase It's not typo. I just solved another problem. The original problem was changed. See an history of editing. But thank you for your interest. – Michael Rozenberg Sep 13 '17 at 12:16
  • There was also a typo in the original question, straight after "which is equal to", which I corrected ... otherwise, generating functions were driving me mad, not coming close to your result :) – rtybase Sep 13 '17 at 12:24
  • @rtybase I think now it's not relevant already, but the solution of the right problem is the same. – Michael Rozenberg Sep 13 '17 at 12:27