# Solve the following recurrence relation

Given that $$a_{n+1}=(r+1)a_n-ra_{n-1}$$ where $$r$$ is a known parameter, I have to find an expression for $$a_n$$ knowing that $$a_0=0$$, $$a_T=1$$ (where $$T$$ is also a known parameter).

• And what are your thoughts? What happens when you try the standard techniques on the recursion? – lulu May 27 '20 at 16:45

$$a_{n+1}=(r+1)a_n−ra_{n−1}$$ Being a classic linear recurrence, the characteristic equation is $$x^2-(r+1)x=r \iff \left(x-\frac{r+1}{2}\right)^2=r+\frac{(r+1)^2}{4}$$ $$\iff x=\frac{r+1}{2} \pm \sqrt{r+\frac{(r+1)^2}{4}}$$ So one can conclude $$a_n=b_1\left(\frac{r+1}{2} + \sqrt{r+\frac{(r+1)^2}{4}}\right)^n+b_2\left(\frac{r+1}{2} - \sqrt{r+\frac{(r+1)^2}{4}}\right)^n$$ $$a_0=1 \implies b_1+b_2=1 \implies b_1=1-b_2$$ and for the sake of algebraic simplicity, let $$r_1=\frac{r+1}{2} + \sqrt{r+\frac{(r+1)^2}{4}}, \ \ r_2=\frac{r+1}{2} - \sqrt{r+\frac{(r+1)^2}{4}}$$ $$a_T=1 \implies b_1(r_1)^T+b_2(r_2)^T=1$$ $$\implies (1-b_2)(r_1)^T+b_2(r_2)^T=1 \iff b_2=\frac{(r_1)^T-1}{(r_1)^T-(r_2)^T}$$ $$b_1=1-b_2 \implies b_1=\frac{1-(r_2)^T}{(r_1)^T-(r_2)^T}$$ and by the definitions of $$a_n,r_1$$ and $$r_2$$ given above, you're done!
Here's a big hint: divide by $$(r+1)!$$ to get $$(b_n = \frac{a_n}{(r+1)!}$$) $$b_{n+1} = b_n - \frac{1}{r+1}b_{n-2}$$ Cam you handle from here?