Closed form formula involving complex numbers Consider the recurrence relation $x_0=1$, $x_1=3$, and $x_n = 6 x_{n-1} -10 x_{n-2}$, for $n\geq2$, how to find a closed form formula when the answer is allowed to have complex numbers?
(Got this question while learning Complex numbers. Quite puzzled about how to start, since the problem was stated using all real numbers (integers to be exact). Couldn't think of how to expand it into complex field. Any advise?)
 A: We can start with the generating function, suppose that
$$f(t) = \sum_{k\geq0}x_kt^k = 1+3t+\sum_{k\geq2}x_kt^k = 1+3t+\sum_{k\geq2}(6x_{k-1}-10x_{k-2})t^k = 1+3t+6t\sum_{k\geq2}x_{k-1}t^{k-1}-10t^2\sum_{k\geq2}x_{k-2}t^{k-2} = $$
Now lets work on the following:
$\sum_{k\geq2}(x_{k-1})t^{k-1} = \sum_{k\geq1}(x_{k})t^{k} = \sum_{k\geq0}(x_{k})t^{k} - 1 = f(t) -1$
$\sum_{k\geq2}x_{k-2}t^{k-2} = \sum_{k\geq0}x_{k}t^{k} = f(t)$
As such, we have:
$$
f(t) = 1+3t+6t(f(t)-1)-10t^2f(t)\Rightarrow f(t)(10t^2-6t+1) = -3t+1 \Rightarrow f(t) = \frac{-3t+1}{10t^2-6t+1}
$$
The function $f(t)$ has the following series representation:
$$
f(t) = \sum_{k\geq0} \frac{1}{2}t^k\left((3-i)^k+(3+i)^k\right)
$$
Comparing coefficients, we get that $\boxed{x_n = \frac{1}{2}((3-i)^n+(3+i)^n)}$
A: In my opinion these answers are getting way out of hand. The recurrence relation you give above is a standard Fibonacci-type. I have presented a general solution for those here. That equation is valid for all real and complex numbers ($x_0,\ x_1$). Many people believe that the such sequences are valid only for integer initial conditions. That is not so, as I have verified for myself many times over.
