Closed form expressions for $T_n$ and $S_n$ of a Fibonacci-like sequence

Question

I am a student curious about recurrence relations who has just bumped into the Intermediate 1st year (grade 11).

I derived the closed form expressions for the $n^{th}$ term and the sum of $n$ terms of a Fibonacci-like sequence of the form $(a,b,a+b,a+2b,2a+3b,...)$ by substituting $a_n=x^n$ into the characteristic recurrence relation: $a_{n+2}=a_{n+1}+a_n$.

I want to know what this method ($a_n=x^n$) is called, and if the below mentioned expressions are already documented somewhere. I would also like to know if there are simpler versions of these expressions.
$$T_n=\sum_{r \in \{{\phi,\psi\}}}{r^n \left(\frac{T_1}{3r+1}+\frac{T_2}{r+2}\right)}$$ $$S_n=\left(\sum_{r\in\{\phi,\psi\}}{r^n\left(\frac{T_1+T_2}{3r+1}+\frac{T_1+2T_2}{r+2}\right)}\right)-T_2$$ where,
$T_n = n^{th}$ term of the Fibonacci-like sequence.
$S_n =$ sum of $n$ terms of the Fibonacci-like sequence.
$\phi,\psi$ are the roots of the equation: $x^2-x-1=0$

Also, I saw other answers mentioning the closed form expressions for $T_n$ using Binet's formula and other methods, but I could not find a closed form expression for $S_n$ in any of those.

These work over every Fibonacci-like sequence. I would love suggestions on the improvement of these expressions.

Thank You.

EDIT: There seems to be some confusion around the summation in the comments. Here is an example that completely explains it.

Let's consider the Fibonacci sequence:$$1,1,2,3,5,8,...$$

Let's verify the formulas for the 6th term and the sum of the first 6 terms of the Fibonacci sequence using the expressions provided above.

First, let's calculate the 6th term ($T_6$) of the Fibonacci sequence:

$$T_6 = \sum_{r \in \{\phi,\psi\}}{r^6\left(\frac{T_1}{3r+1}+\frac{T_2}{r+2}\right)}$$

We know the first two terms of the Fibonacci sequence are $T_1 = 1$ and $T_2 = 1$, and we'll use the roots of the characteristic equation, $\phi$ and $\psi$, which are approximately $\phi \approx 1.61803$ and $\psi \approx -0.61803$.

Substituting these values into the formula:

$$T_6 = \left(\phi^6\left(\frac{1}{3\phi+1}+\frac{1}{\phi+2}\right)\right) + \left(\psi^6\left(\frac{1}{3\psi+1}+\frac{1}{\psi+2}\right)\right)$$

After evaluating this expression, we get $T_6 \approx 8$.

Next, let's calculate the sum of the first 6 terms of the Fibonacci sequence ($S_6$):

$$S_6 = \left(\sum_{r \in \{\phi,\psi\}}{r^6\left(\frac{T_1+T_2}{3r+1}+\frac{T_1+2T_2}{r+2}\right)}\right)-T_2$$

Substituting the known values:

$$S_6 = \left(\phi^6\left(\frac{1+1}{3\phi+1}+\frac{1+2}{\phi+2}\right)\right) + \left(\psi^6\left(\frac{1+1}{3\psi+1}+\frac{1+2}{\psi+2}\right)\right) - 1$$

After evaluating this expression, we get $S_6 \approx 20$.

The values obtained from the formulas match the actual values of the 6th term and the sum of the first 6 terms of the Fibonacci sequence, confirming the correctness of the expressions provided above.

Answer 1

I don't know if there's an official name for the $a_n = x^n$ method - maybe the "ansatz method", since one name for a substitution like $a_n = x^n$ is an "ansatz".

The simplest closed form I can think of for a sequence that satisfies $T_n = T_{n-1} + T_{n-2}$ in terms of $\phi$ and $\psi$ is $$T_n = \frac{(T_1 - T_0\psi)\cdot \phi^n - (T_1 - T_0\phi)\cdot \psi^n}{\phi - \psi}.$$ This can be obtained by writing $T_n = A \phi^n + B \psi^n$, then setting $n=0$ and $n=1$ to solve for $A$ and $B$. (When $T_0 = 0$ and $T_1 = 1$, this reduces to Binet's formula.)

In some cases, our base case for the recurrence is $T_1$ and $T_2$, rather than $T_0$ and $T_1$. In that case, $T_0$ "should have been" $T_2 - T_1$ to satisfy the Fibonacci recurrence, and we can replace $T_0$ by $T_2 - T_1$ in the formula above. It's a tiny bit messier, that way.

Compared to the formula in the question, we are trading off a constant factor like $\frac{T_1}{3\phi + 1} + \frac{T_2}{\phi+2}$ for $\frac{T_1 - T_0\psi}{\phi-\psi}$ or $\frac{T_1 \psi^2 - T_2\psi}{\phi - \psi}$. These are equal when $\phi$ and $\psi$ are the two roots of $x^2-x-1=0$.

---

For $S_n$, we can observe that $S_{n-1} + S_{n-2} = S_n - T_2$. Proof: $$S_{n-1} + S_{n-2} = \sum_{k=2}^n T_{k-1} + \sum_{k=3}^n T_{k-2} = T_1 + \sum_{k=3}^n (T_{k-1} + T_{k-2}) = T_1 + \sum_{k=3}^n T_k,$$ which includes every term of $S_n$ except for $T_2$. It follows that $(S_{n-1} + T_2) + (S_{n-2} + T_2) = (S_n + T_2)$, so the sequence $\hat S_n := S_n + T_2$ also satisfies the Fibonacci recurrence. We can therefore use the same formula as above for it, with the initial condition $\hat S_0 = T_2$ and $\hat S_1 = T_3$. After subtracting $T_2$ from the result, we conclude $$S_n = \hat S_n - T_2 = \frac{(T_3 - T_2\psi)\cdot \phi^n - (T_3 - T_2\phi)\cdot \psi^n}{\phi - \psi} - T_2.$$ We can also spot that if $\hat S_0 = T_2$ and $\hat S_1 = T_3$, then in general we'll have $\hat S_n = T_{n+2}$, and therefore $S_n = T_{n+2} - T_2$.

Answer 2

I had tried to find the sum until nth term for fibonacci once, and I would suggest a much simpler way. Here was my approach:

$F_{k} = F_{k+1} - F_{k-1}$

$F_{k-1} = F_{k} - F_{k-2}$

$F_{k-2} = F_{k-1} - F_{k-3}$

$F_{k-3} = F_{k-2} - F_{k-4}$

$F_{k-4} = F_{k-3} - F_{k-5}$

...

$F_{3} = F_{4} - F_{2}$

$F_{2} = F_{3} - F_{1}$

$F_{1} = F_{2} - F_{0}$

Therefore, the sum telescopes: cancelling every term except $F_{k+1} + F_{k} - F_{1} - F_{0} $

Which simplifies to $F_{k+2}-F_{2} = F_{k+2} - 1$

Now, for a closed form expression you can simply plug this into the Binets formula and get the closed form:

$$S_{k}= \frac{\left(\frac{1+\sqrt5}{2}\right)^{k+2} - \left(\frac{1-\sqrt5}{2}\right)^{k+2}}{\sqrt5} -1 $$

Answer 3

Let $<T_n>$ be a Fibonacci-like sequence with first and second terms with $a$ and $b$.

Then a closed formula expression for $T_n$ is given by the formula in Misha Lavrov's response, plugging in $T_0=a$ and $T_1=b$.

By the telescoping method desribed in Initial_Velocity's response, we obtain the closed formula expression $$S_n=T_{n+1}+T_n-T_1-T_0=T_{n+1}-T_n-b-a.$$