# General method for solving linear recurrence relations of n terms

Firstly: I realize this is similar to other questions on the site but I am SPECIFICALLY asking if the method below ever breaks down and if there is a quicker method.

I derived this method (whilst trying to find a closed-form solution for Fibonacci numbers) for converting linear recurrence relations of the form $a_0U_n+a_1U_{n-1}+a_2U_{n-2}+...+a_{L-1}U_{n-L+1}=0$ where $U_0,U_1,...,U_{L-1}$are known (Where U_n are the terms, L is the total number of U_n in the recurrence and a_n are the coefficients (real) of the recurrence).

I.e. convert the recurrence $\sum_{r=0}^{L-1} a_rU_{n-r}=0$ into a closed-form equation for U_n

STEP 1:

Define $p(x)=\sum_{r=0}^{\infty} U_rx^r \$

Then define $q(x)=p(x) \sum_{r=0}^{L-1} a_rx^r$ $$q(x) = a_0 \sum_{r=0}^{\infty} U_rx^r+a_1 \sum_{r=0}^{\infty} U_rx^{r+1} +a_2 \sum_{r=0}^{\infty} U_rx^{r+2}+...+a_{L-1} \sum_{r=0}^{\infty} U_rx^{r+L-1}$$ Separating enough terms from each series to make the exponents of x the same and then combining the sums with common exponent:$$q(x) = a_0 \sum_{r=0}^{L-2} U_rx^r+a_1 \sum_{r=0}^{L-2} U_rx^{r+1} +a_2 \sum_{r=0}^{L-3} U_rx^{r+2}+...+\\a_{L-1} \sum_{r=0}^{\infty}(\sum_{k=0}^{L-1}a_kU_{r+k+L-1}) U_rx^{r+L-1}$$ From the definition of the recurrence, the nested sigma =0 thus: $$q(x)=\sum_{k=0}^{L-2} a_k(\sum_{r=0}^{L-2-k} U_rx^r)x^k=\sum_{k=0}^{L-2} \sum_{r=0}^{L-2-k} a_kU_rx^{r+k}$$ From how we defined q(x) above, we can eliminate q(x): $$p(x)=\frac{\sum_{k=0}^{L-2} \sum_{r=0}^{L-2-k} a_kU_rx^{r+k}}{\sum_{r=0}^{L-1} a_rx^r}$$

Before continuing to step 2, it's probably best to use an example: $$U_{r+3}-6U_{r+2}+11U_{r+1}-6U_r=0, \ U_0=1,\ U_1=-1, \ U_2=0 \therefore L=4\\ \therefore p(x)=\frac{\sum_{k=0}^{2} \sum_{r=0}^{2-k} a_kU_rx^r}{\sum_{r=0}^{3} a_rx^r}=\frac{1-7x+17x^2}{1-6x+11x^2-6x^3}=\frac{1-7x+17x^2}{(1-x)(1-2x)(1-3x)}$$

STEP 2:

Decompose p(x) using partial fractions (will this ever break down?). With our example: $$p(x)=\frac{1-7x+17x^2}{(1-x)(1-2x)(1-3x)}=\frac{11}2\frac1{1-x}-7\frac1{1-2x}+\frac{5}2\frac1{1-3x}$$

STEP 3:

Use the binomial theorem to produce power series for all the fraction terms. With our example: $$p(x)=\frac{1-7x+17x^2}{(1-x)(1-2x)(1-3x)}=\frac{11}2\sum_{r=0}^{\infty}x^r-7\sum_{r=0}^{\infty}2^rx^r+\frac52\sum_{r=0}^{\infty}3^rx^r \\ =\sum_{r=0}^{\infty}(\frac{11}2-7( 2^r)+\frac52( 3^r))x^r$$

STEP 4:

From the definition of p(x), we can extract the closed-form solution: $$p(x)=\sum_{r=0}^{\infty} U_rx^r=\sum_{r=0}^{\infty}(\frac{11}2-7( 2^r)+\frac52( 3^r))x^r \\ \therefore U_n=\frac{11}2-7( 2^r)+\frac52( 3^r) \ for \ r \ge 0$$

• With your counting, $U_{L-1}$ is not an initial value but is a result of the previous $L-1$ values. It is notationally simpler to increase the order of the iteration to $L$ than to reduce the number of initial values. – LutzL Aug 25 '16 at 11:57
• By initial values you mean the known U_n? With any less than L initial values (U_0,...U_(L-l)) the recurrence cannot work in the first place. – CapitalPi Aug 25 '16 at 12:17
• An $L$ order recurrence relation $a_0U_{n}+a_1U_{n-1}+…+a_{L-1}U_{n-L+1}\color{red}{+a_LU_{n-L}}=0$ or more generally $U_{n}=f(U_{n-L},…U_{n-1})$ requires and is completely determined $L$ initial values $U_0,…U_{L-1}$. – LutzL Aug 25 '16 at 13:14
• No, you haven't counted the zeroth term. L terms would be term 1 to term L OR term 0 to term L-1. – CapitalPi Aug 25 '16 at 13:27
• An order 1 linear recurrence $a_0U_n+a_1U_{n-1}=0$ has 2 terms, a linear recurrence of order $L$ has (generically/formally) $L+1$ terms. Similarly: a general polynomial of degree $d$ has $d+1$ coefficients. – LutzL Aug 25 '16 at 13:40

Usually one would not carry out the full computation but only compute the zeroes $q_1,…,q_L$ of the characteristic polynomial $a_0q^L+…+a_{L-1}q+a_L$ and then solve the system $$U_0=c_1q_1^0+…+c_Lq_L^0\\ \vdots\\ U_{L-1}=c_1q_1^{L-1}+…+c_Lq_L^{L-1}.$$
This only works if the roots are distinct, for repeated roots $q_{j+1}=q_j$ you have to replace $q_{j+1}^k$ by $kq_{j+1}^k$ etc.