Generalization of recursive formula

Question

Ok, here is the problem, I have formula: $a_n=a_{n-1}+2^{n-4}-a_{n-4}$ with initial variables $a_0=0$, $a_1=0$,$a_2=0$ and $a_3=1$

If not for $2^{n-4}$ member in recursion, I probably would manage to get general form, but $2^{n-4}$ makes things way more complicated.

Is it generally possible to transform $a_n=a_{n-1}+2^{n-4}-a_{n-4}$ into nonrecursive form, and if possible - how?

Answer 1

As suggested in my comment above, for such problems (linear recurrences involving tedious terms) the concept of generating functions is useful. Define $$A(x)=\sum_{k=0}^{\infty} a_nx^n$$ Now, the recursion implies $a_{n+4}x^n+a_nx^n=a_{n+3}x^n+2^nx^n$. Summing this over all $n$, we obtain $$A(x)+\frac{A(x)-x^3}{x^4}=\frac{A(x)}{x^3}+\frac{1}{1-2x}$$ Now, this is a linear equation in $A(x)$ and we can solve for it and obtain $$A(x)=\frac{x^4-x^3}{(2x-1)(x^4-x+1)}$$ Now, using partial fractions decomposition we can (in principal) reversely obtain the coefficient of $x^n$ in the series of $A(x)$ (which is just $a_n$). In this way, you can obtain (in principal) a closed form for $a_n$ although (in this case) the partial fractions might become slightly tedious...

Given the non-existence of nice closed form you might ask for a "nicer" (i.e. homogenous) recursion not involving those terms like $2^{n-4}$ for $a_n$. But this is easily obtained: We have $a_{n+1}+a_{n+5}-a{n+4}=2^{n+1}=2 \cdot 2^n=2(a_n+a_{n+4}-a_{n+3})$ and hence obtain the homogenous recursion: $$a_{n+5}=3a_{n+4}-2a_{n+3}-a_{n+1}+2a_n$$ But this is also not useful to compute a closed form using the standard way since the characteristic equation will be $0=x^5-3x^4-2x^3+x-2=(x-2)(x^4-x^3+1)$ where the second factor (similar to the one from our first attempt) is irreducible.

Remark: Note that the problems arise only from the irreducibility of the characteristic equation and not really from the $2^{n-4}$ term in the original recurrence since the latter can be easily handled by both approaches.

Answer 2

First method

Like differential equations, that do not admit a general method to solve them, recursive definitions do not admit general procedures allowing to find the general term. Nevertheless, the one that you post does have an answer, and this is obtained with the Mathematica command

RSolve[a[n] == a[n - 1] - a[n - 4] + 2^(n - 4), a[n], n].

The solution is the following: let $r_1, r_2, r_3, r_4$ be the complex solutions of the equation $x^4-x^3+1=0$; then $a_n = \frac {2^n} 9 + C_1 r_1 ^n + C_2 r_2 ^n + C_3 r_3 ^n + C_4 r_4 ^n$, where $C_1, C_2, C_3, C_4$ are constants to be found by using the initial conditions, i.e.

$C_1 + C_2 + C_3 + C_4 = -\frac 1 9 \\ C_1 r_1 + C_2 r_2 + C_3 r_3 + C_4 r_4 = -\frac 2 9 \\ C_1 r_1 ^2 + C_2 r_2 ^2 + C_3 r_3 ^2 + C_4 r_4 ^2 = -\frac 4 9 \\ C_1 r_1 ^3 + C_2 r_2 ^3 + C_3 r_3 ^3 + C_4 r_4 ^3 = -\frac 8 9 .$

The determinant of the system will be a Vandermonde determinant, therefore it will have the value $(r_1 - r_2) (r_1 - r_3) (r_1 - r_4) (r_2 - r_3) (r_2 - r_4) (r_3 - r_4)$.

Since $x^4-x^3+1=0$ has degree $4$, its roots can, in principle, be computed explicitly; in practice, though, they look extremely ugly. It is true that sometimes one can perform smart tricks and compute certain polynomials in $r_1, r_2, r_3, r_4$ without explicitly knowing these, by using the fundamental theorem of symmetric polynomials and patiently computing long algebraic expressions, but I shall not attempt to do it here.

Second method

If you are unhappy about using computer software to solve mathematical problems, you could mimic the approach from differential equations.

First, find the general solution of the "homogeneous" equation $a_n = a_{n-1} + a_{n-4}$. This is done by considering the associated algebraic equation $x^4 = x^3 - 1$; it is known then that $a_n = C_1 r_1 ^n + C_2 r_2 ^n + C_3 r_3 ^n + C_4 r_4 ^n$.

Next, add a particular solution of the "inhomogeneous" equation to the previous expression, to obtain what you are looking for. Since your equation contains an exponential term, why not try it first? Therefore, let us look for a solution of the form $2^n C$. Replacing this in your equation will give you $C = \frac 1 9$.

Finally, impose the initial conditions to find out the 4 constants.

In principle it can be done, in practice the computations will prove intimidating. If you need the result in programming or engineering, you might be satisfied by doing them numerically. If you are doing pure mathematics (i.e. symbolic computations), maybe the above will suffice.

Third method

If you are unhappy about the guessing involved in the previous method, call $b_n = 2^n$. Then

$a_n = a_{n-1} -a_{n-4} + b_{n-4} \\ b_n = 2 b_{n-1}.$

Calling $v_n = \left( \begin{array} {c} a_n \\ b_n \end{array} \right)$ gives $v_n = \left( \begin{array} {cc} 1 & 0 \\ 0 & 2 \end{array} \right) v_{n-1} + \left( \begin{array} {cc} 1 & 1 \\ 0 & 0 \end{array} \right) v_{n-4}$, which is a homogeneous vector recursive formula. Again, you may try techniques inspired by those from differential equations, but you will reach the same end, namely the difficulty of working with the roots of the equation $x^4 - x^3 + 1 = 0$.

Fourth method

Use generating funtions, as described above in another answer. Again, you will reach the same difficulty related to the associated algebraic equation.