4
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LutzL Aug 25 '16 at 11:57
  • $\begingroup$ 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. $\endgroup$ – CapitalPi Aug 25 '16 at 12:17
  • $\begingroup$ 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}$. $\endgroup$ – LutzL Aug 25 '16 at 13:14
  • $\begingroup$ No, you haven't counted the zeroth term. L terms would be term 1 to term L OR term 0 to term L-1. $\endgroup$ – CapitalPi Aug 25 '16 at 13:27
  • $\begingroup$ 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. $\endgroup$ – LutzL Aug 25 '16 at 13:40
1
$\begingroup$

Yes, this is the standard way using generating functions to get to the solution formula. One could also use a vector iteration with the companion matrix and the diagonalization of said matrix to arrive at this formula.

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.

$\endgroup$
  • $\begingroup$ Much obliged :) The vector/matrix method does seem tempting. $\endgroup$ – CapitalPi Aug 25 '16 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.