If x_n=a_1*x_{n-1} +...+a_k*x_{n-k}, then the degree of the denominator of the rational generating function is at most k.
故序列a_n是二次的, b_n是四次的,要求证明c_n是八次的.
利用alpha_2=alpha_0, it is easy to see that
alpha_0*(b_{n+1}^2 - b_n^2)=a_{n+1}*(alpha_0 c_{n-1} +alpha_1 c_{n} + alpha_0 c_{n+1}).
I seriously doubt that c_n is a linear recursive sequence. See the following example.
Let d_n be a new sequence defined by
d_n = c_{n-1} + alpha_1 / alpha_0 * c_n + c_{n+1}.
If c_n is linear recursive, as you questioned, then d_n is also a linear recursive sequence with the same linear relation SUM_{k=0}^8 gamma_k d_{n+k} = 0. http://en.wikipedia.org/wiki/Lin ... nstant_coefficients
Now we let a_n = 1/4 * 4^n + 4 * 4^{-n},
b_n = 2^n + 2^{-n}. Consequently, the expression of d_n in the form of a_n and b_n is
d_n= (b_{n+1}^2 - b_n^2) / a_{n+1}
= (3*4^n - 3/4 * 4^{-n}) / (4^n + 4^{-n} )
=3 - (15/4) * ( 1/(16^n+1) ).
Take look at the generating function of d_n, which is sum_{n=0}^infty d_n*x^n. Ignore the constant (3) and the scalar (15/4), the main term is of the form \sum_n (x^n/ (a^n+1) ) with a= 16.
I do not believe (with probability >80%) that this summation function will ends up with a rational function, although I cannot prove it.
You may construct your own example to give hints before you try to prove the assertion.