Are all recurrence relations solvable by generating functions? A tricky one

Question

I have found this recurrence relation:

$$r_0 = 0; \\ r_w = 1; \\r_{n+1} = 2r_n - r_{n-1};\; \text{for}\; 0 < n < w$$

(from section 20.1 here: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_notes.pdf)

The coefficient for the general $n$ term is solved by using linear recurrence relations. I have tried to solve it by generating function but I can't. It seems that the problem is that we don't have actual initial conditions but only a condition for 0 that does not add anything and then a jump until $w$. And we need a value for $r_1$ that you can't solve until you solve the entire recurrence relation.

My try: searching $G(x) = \sum_{n\geq 1}r_{n}x^{n}$, multiplying the recurrence by $x^{n+1}$ and summing from $n=1$:

$$\sum_{n\geq 1}r_{n+1}x^{n+1} = 2\sum_{n\geq 1}r_{n}x^{n+1} - \sum_{n\geq 1}r_{n-1}x^{n+1} $$

$$G(x) - r_1 = 2xG(x) - x^2(G(x) - r_0)$$

But how can you advance from here if you don't know $r_1$? Are all the recurrence relations solvable by generating functions?

Answer 1

Choosing conveniently the sum limits we have

$$ \frac 1x\left(G(x)-r_0\right)-2G(x) + x\left(G(x)-r_w x^w\right) = 0 $$

or

$$ G(x) = \frac{r_w x^{w+2}+r_0}{1-2x+x^2} $$

NOTE

$$ \sum_{k=0}^w\left(\frac 1x r_{k+1} x^{k+1}-2r_k x^k+x r_{k-1}x^{k-1}\right)=0 $$

NOTE

Considering $w = 5, r_0 = 0, r_5= 1$ we have

$$ \frac{x^7}{1-2x+x^2} = x^5+2x^4+3x^3+4x^2+5x+\cdots $$

so we have

$$ r_4 = 2, r_3 = 3, r_2 = 4, r_1 = 5 $$

and as we can easily verify, they obey the recurrence

$$ r_{k+1}-2r_k+r_{k-1} = 0 $$

Answer 2

In this case we can see that the general solution for arbitrary $r_0$ and $r_1$ is

$r_n = nr_1-(n-1)r_0$

Togather with $r_0=0$ and $r_w=1$ this gives us $r_1=\frac{1}{w}$ and $r_n=\frac{n}{w}$.