0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Mathematics Meta, or in Mathematics Chat. Comments continuing discussion may be removed. $\endgroup$ Commented Apr 28, 2024 at 13:15

3 Answers 3

Reset to default
2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ That's a really neat expression! Thank you for the answer. $\endgroup$ Commented Mar 29, 2024 at 18:47
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ The $S_n$ must be in the terms of first and second term. You just put the values of $\phi$ and $\psi$. What is $k$ in your formula? You did not define it. $\endgroup$ Commented Mar 28, 2024 at 15:42
  • $\begingroup$ Sorry I meant n instead of k, a typo $\endgroup$ Commented Mar 28, 2024 at 17:04
  • $\begingroup$ I am really confused about how to use it for other fibonacci sequences like $0,1,1,2,...$, or $4,5,9,14,...$, etc. that have other first and second terms. $\endgroup$ Commented Mar 29, 2024 at 17:23
0
$\begingroup$

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.$$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.