Closed form for $T_n$ if $T_{n+3}=2 T_{n+2}+2 T_{n+1}-T_{n}$

Question

Consider the recurrence relation $$T_{n+3}=2 T_{n+2}+2 T_{n+1}-T_{n}$$ with first three terms as: $T_{1}=20, T_{2}=12, T_{3}=70$

Find the closed form expression for $T_n$.

My try: Since it is a constant coefficient difference equation, the auxiliary equation is: $$\lambda^3-2\lambda^2-2\lambda+1=0$$ whose roots are: $-1,\frac{3\pm\sqrt{5}}{2}$ Thus we have: $$T_{n}=A(-1)^{n}+B\left(\frac{3+\sqrt{5}}{2}\right)^{n}+C\left(\frac{3-\sqrt{5}}{2}\right)^{n}$$

where the constants $A,B,C$ to be determined by values of $T_1,T_2,T_3$ but its becoming too tedious to solve. Any alternate approach?

Answer 1

There is one alternate approach mentioned in the comments: generating functions.

Let $$f(x) = \sum_{n \geq 1} T_n x^n.$$ If we can write $f(x)$ as a well-known power series, then we can equate coefficients to determine $T_n$ exactly.

Start by multiplying both sides of your recurrence by $x^n$ and sum over all values of $n$ where the recurrence holds: \begin{align*} T_{n + 3} x^n &= 2 T_{n + 2} x^n + 2T_{n + 1} x^n - T_n x^n \\ \sum_{n \geq 1} T_{n + 3} x^n &= 2 \sum_{n \geq 1} T_{n + 2} x^n + 2 \sum_{n \geq 1} T_{n + 1} x^n - \sum_{n \geq 1} T_n x^n \\ \frac{f(x) - T_1 x - T_2 x^2 - T_3 x^3}{x^3} &= 2 \frac{f(x) - T_1 x - T_2 x^2}{x^2} + 2 \frac{f(x) - T_1 x}{x} - f(x). \end{align*} We can solve this for $f(x)$: $$f(x) = -{\frac {x \left( 2\,{\it T_1}\,{x}^{2}+2\,{\it T_2}\,{x}^{2}-{\it T_3}\,{x}^{2}+2\,{\it T_1}\,x-{ \it T_2}\,x-{\it T_1} \right) }{{x}^{3}-2\,{x}^{2}-2\,x+1}}. $$ Once you substitute your values for $T_1$, $T_2$, and $T_3$, you do partial fraction decomposition on the resulting explicit rational function. Each term of the decomposition can be written as an explicit geometric series, and $T_n$ is the sum of the $n$th terms of each. If you do this, you get \begin{equation*} A = -\frac{54}{5} \quad B = \frac{2}{5} (6 + \sqrt{5}) \quad C = \frac{2}{6}(6 - \sqrt{5}). \end{equation*}

It is, as you say, very tedious to do this by hand! I recommend using a computer algebra system such as Maple, Mathematica, or Sage to do the manipulations. In that case, each has very capable recurrence solvers.

For more details and some friendlier examples with respect to generating functions, see generatingfunctionology.

Answer 2

$$T_{n}=A(-1)^{n}+B\left(\frac{3+\sqrt{5}}{2}\right)^{n}+C\left(\frac{3-\sqrt{5}}{2}\right)^{n}$$ Where the constants $A,B,C$ to be determined by values of $T_1,T_2,T_3$ but its becoming too tedious to solve. Any alternate approach?

The approach is correct, and can be made less tedious by noting that:

• It is easier to shift the powers $\,T_n=A'(-1)^{n-1}+B'\left(\frac{3+\sqrt{5}}{2}\right)^{n-1}+C'\left(\frac{3-\sqrt{5}}{2}\right)^{n-1}\,$ since the sequence starts with index $\,1\,$.

• All terms in the sequence are integers, so $\,B',C'\,$ must be rational conjugates, therefore $\,A'=a\,$ and $\,B',C'=b \pm c\sqrt{5}\,$ where $\,a,b,c \in \mathbb Q\,$.

Then:

• $\require{cancel} \color{red}{20} = T_1 = a+b+\cancel{c\sqrt{5}}+b-\cancel{c\sqrt{5}} \color{red}{= a + 2 b}$

• $\color{red}{24} = 2 \cdot T_2 = -2a + (b+c\sqrt{5})(3+\sqrt{5}) + (b-c\sqrt{5})(3-\sqrt{5})$ $= -2a+3b+5c+\cancel{(b+3c)\sqrt{5}}+3b+5c-\cancel{(b+3c)\sqrt{5}}$ $\color{red}{= -2a + 6b + 10c}$

• $\color{red}{280} = 4 \cdot T_3 = 4a + (b+c\sqrt{5})(3+\sqrt{5})^2 + (b-c\sqrt{5})(3-\sqrt{5})^2$ $= 4a + (b+c\sqrt{5})(14 + 6 \sqrt{5}) + (b-c\sqrt{5})(14-6\sqrt{5})$ $= 4a+14b+30c+\cancel{(6b+14c)\sqrt{5}}+14b+30c-\cancel{(6b+14c)\sqrt{5}}$ $\color{red}{= 4a + 28 b + 60 c}$

Solving the system for $\,a,b,c\,$ gives $\,a = \dfrac{54}{5}, b = \dfrac{23}{5}, c = \dfrac{9}{5}\,$.