1

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?)

Amy
  • 21
  • 1
    Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc. – MH.Lee Nov 12 '21 at 16:15
  • 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? – Amy Nov 12 '21 at 16:25
  • Welcome to MSE. Use $$ around the whole mathematical expression. – jjagmath Nov 12 '21 at 16:26
  • @Amy Nightflight asked for context, but the idea is that you edit your question to improve it, don't add that in comments. – jjagmath Nov 12 '21 at 16:28
  • @jjagmath, thank you for letting me know. I will try to use $$ around the whole mathematical expression the next time. (Actually, I tried this time in the beginning. However, it doesn't quite work out. I un-voluntarily reduced to the form that worked. ) I will also include more context and background when asking the question or edit it to improve it. (New to this system. Thanks for pointing me to the better way of using the system.) – Amy Nov 12 '21 at 17:56
  • 1
    All the terms of the sequence are obviously real. However in the expression for the general term, you can use complex numbers, if needed. On simplification the expression should still evaluate to a real number. Now unless you show your attempts at solving, it won't be clear to anyone what tools you are comfortable using to solve such problems. – Macavity Nov 12 '21 at 18:43

2 Answers2

2

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

aliberro
  • 408
  • This is brilliant! Thank you. I am still pondering on the part of the series representation of $f(t)$. Is this Maclaurin Series of $f(t)$? – Amy Nov 12 '21 at 17:51
  • Yeah, just do partial fractions, then find the Maclaurin series for $f(t)$. If you have any other question feel free – aliberro Nov 12 '21 at 17:58
  • Thank you so much for the hint on partial fractions. After thinking about it for a while and reconfirming it by looking at the book, I suddenly realize I only did partial fractions in the real number field before. The rational functional representation of $f(t)$ is already one of the simplest rational fraction form of $\frac{Ax+B}{ax^2+bx+c}$. How to proceed ? Or is there any material you could refer me to ? – Amy Nov 12 '21 at 18:42
  • @Amy note that $10t^2-6t+1 = \frac{(10t-(-3-i))(10t-(3-i))}{2}$, then $\frac{-3t+1}{10t^2-6t+1} = \frac{1}{10} \frac{-3t+1}{(10t-(-3-i))(10t-(3-i))}$ – aliberro Nov 12 '21 at 18:47
  • @Amy can you continue from here? – aliberro Nov 12 '21 at 18:47
  • thanks again for the prompt! I got $10t^2-6t+1=\frac{(10t-(3+i))(10t-(3-i))}{10}$. Thus $$\frac{-3t+1}{10t^2-6t+1}=10 \times \frac{-3t+1}{(10t-(3+i))(10t-(3-i))}$$ I tried to work on the partial fraction for $\frac{-3t+1}{(10t-(3+i))(10t-(3-i))}$ by assuming: $$\frac{-3t+1}{(10t-(3+i))(10t-(3-i))}= \frac{A}{10t-(3+i)} + \frac{B}{10t-(3-i)} = \frac{10At-(3-i)A+10Bt-(3+i)B}{(10t-(3+i))(10t-(3-i))}$$ Thus, it means $10(A+B)=-3$ (equation 1), and $-(3-i)A-(3+i)B=1$ (equation 2). From (equation 2), I got $A=B=-\frac{1}{6}$, but this solution couldn't make (equation 1) true. Any help? – Amy Nov 12 '21 at 21:26
  • @Amy it would be better if you move to the chat, since the comments are so big now. Let us continue this discussion in chat. – aliberro Nov 12 '21 at 21:33
  • I noticed a small mistake in my previous comment, $10t^2-6t+1=\frac{(10t-(3+i))(10t-(3-i))}{10}$, then $\frac{-3t+1}{10t^2-6t+1} = 10\frac{-3t+1}{(10t-(3+i))(10t-(3-i))}$ – aliberro Nov 12 '21 at 22:32
1

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.

Cye Waldman
  • 7,524