Some identities for generalized Fibonacci and Lucas numbers

Abstract

In this paper we study one parameter generalization of the Fibonacci numbers, Lucas numbers which generalizes the Jacobsthal numbers, Jacobsthal–Lucas numbers simultaneously. We present some their properties and interpretations also in graphs. Presented results generalize well-known results for Fibonacci numbers, Lucas numbers, Jacobsthal numbers and Jacobsthal–Lucas numbers.

Keywords:

• Fibonacci numbers
• Jacobsthal numbers
• Recurrence relations

1 Introduction and preliminary results

The Fibonacci numbers $F_n$ are defined by the recurrence relation $F_n=F_{n-1}+F_{n-2}$, for $n\ge 2$ with $F_0=0$, $F_1=1$.

The $n$th Lucas number $L_n$ is defined recursively by $L_n=L_{n-1}+L_{n-2}$ for $n\ge 2$ with initial terms $L_0=2$, $L_1=1$.

Apart from the Fibonacci numbers and the Lucas numbers the well-known are the Jacobsthal numbers and the Jacobsthal–Lucas numbers.

For an integer $n\ge 0$ the $n$th Jacobsthal number $J_n$ is defined recursively by $J_n=J_{n-1}+2J_{n-2}$, for $n\ge 2$ with $J_0=0,J_1=1$. The $n$th Jacobsthal–Lucas number $j_n$ is defined by $j_n=j_{n-1}+2j_{n-2}$, for $n\ge 2$ with $j_0=2,j_1=1$.

Let us consider one parameter generalization of the Fibonacci numbers.

Let $n\ge 0$, $t\ge 1$ be integers. The $n$th generalized Fibonacci number $J_{t,n}$ is defined recursively as follows (1) $$J_{t,n}=J_{t,n-1}+t\cdot J_{t,n-2},$$(1) for $n\ge 2$ with initial conditions $J_{t,0}=0$ and $J_{t,1}=1$.

It is interesting to note that $J_{t,n}$ generalizes the Fibonacci numbers and the Jacobsthal numbers. If $t=1$ then $J_{1,n}=F_n$ and for $t=2$ holds $J_{2,n}=J_n$. For these reasons numbers $J_{t,n}$ also are named as generalized Jacobsthal numbers.

In the same way we can define the generalized Lucas numbers, which are a generalization of Lucas numbers and Jacobsthal–Lucas numbers.

Let $n\ge 0$, $t\ge 1$ be integers. The $n$th generalized Lucas number $j_{t,n}$ is defined recursively as follows (2) $$j_{t,n}=j_{t,n-1}+t\cdot j_{t,n-2},$$(2) for $n\ge 2$ with initial conditions $j_{t,0}=2$ and $j_{t,1}=1$.

If $t=1$ then $j_{1,n}=L_n$ and for $t=2$ holds $j_{2,n}=j_n$.

Since the characteristic equation of relations (1) and (2) is $r^2-r-t=0$, so roots of it are $\alpha =\frac{1+\sqrt{1+4t}}{2}$, $\beta =\frac{1-\sqrt{1+4t}}{2}$. Consequently for $n\ge 0$ the direct formulas (named also as Binet formulas) for $J_{t,n}$ and $j_{t,n}$ have the forms (3) $$J_{t,n}=\frac{1}{\sqrt{1+4t}}\left[{\left(\frac{1+\sqrt{1+4t}}{2}\right)}^n-{\left(\frac{1-\sqrt{1+4t}}{2}\right)}^n\right],$$(3) (4) $$j_{t,n}={\left(\frac{1+\sqrt{1+4t}}{2}\right)}^n+{\left(\frac{1-\sqrt{1+4t}}{2}\right)}^n.$$(4)

The Fibonacci numbers have many interpretations also in graph theory, see [1–6]. It was shown that the generalized Fibonacci numbers $J_{t,n}$ are related to the Merrifield–Simmons index of a special graph product, see for details [7]. In this paper we show another graph interpretation of $J_{t,n}$.

Only undirected, connected simple graphs are considered. A subset $S\subseteq V\left(G\right)$ is independent if for each $x,y\in S$, there is no edge between them. Moreover the empty set and every subset containing exactly one vertex are independent. Let $n\ge 1$ be an integer. Let us consider $n$ copies of edgeless graph $N_t$ of order $t$, $t\ge 1$, denoted by $N_t^i$, with $V\left(N_t^i\right)=\{x_1^i,\dots ,x_t^i\}$ for $i=1,\dots ,n$. Then $G_n$ is a graph such that $V\left(G_n\right)={\bigcup }_{i=1}^{n}V\left(N_t^i\right)$ and $E\left(G_n\right)={\bigcup }_{i=1}^n\{x_j^i{x}_k^{i+1};1\le i\le n,1\le j,k\le t\}$. Let $\sigma \left(G_n\right)$ be the number of all independent sets $S$ of $G_n$ such that $|S\cap V\left(N_t^i\right)|\le 1$ for $i=1,\dots ,n$.

Theorem 1

Let $n\ge 1$ , $t\ge 1$ be integers. Then (5) $$\sigma \left(G_n\right)=J_{t,n+2}.$$(5)

Proof

By Induction on $n$ Let $n,t$ be as in the statement of the theorem. If $n=1,2$ then the result is obvious. Suppose that $n\ge 3$ and let $\sigma \left(G_k\right)=J_{t,k+2}$ for $k<n$. We shall show that $\sigma \left(G_n\right)=J_{t,n+2}$. Let $S\subseteq V\left(G_n\right)$ be an arbitrary independent set such that $|S\cap V\left(N_t^i\right)|\le 1$ for $i=1,\dots ,n$. We consider the following cases.

1.	$S\cap V\left(N_t^n\right)=0̸$. Then $S$ is an arbitrary independent set of a graph $G_{n-1}$ with the condition $|S\cap V\left(N_t^j\right)|\le 1$ for $j=1,\dots ,n-1$. By the induction hypothesis there are $\sigma \left(G_{n-1}\right)=J_{t,n+1}$ subsets $S$ in this case.
2.	$S\cap V\left(N_t^n\right)\ne 0̸$. Clearly $|S\cap V\left(N_t^n\right)|=1$ and by the definition of the graph $G_n$ holds $S\cap V\left(N_t^{n-1}\right)=0̸$. Since the unique vertex belonging to $S\cap V\left(N_t^n\right)$ can be chosen in $t$ ways and by induction hypothesis there are $t\cdot \sigma \left(G_{n-2}\right)=t\cdot J_{t,n}$ subsets $S$ in this case.

Finally $\sigma \left(G_n\right)=\sigma \left(G_{n-1}\right)+t\cdot \sigma \left(G_{n-2}\right)=J_{t,n+1}+t\cdot J_{t,n}=J_{t,n+2}$ which ends the proof. □

2 Identities for generalized Fibonacci and Lucas numbers

In this section we give some properties of generalized Fibonacci numbers and generalized Lucas numbers.

Theorem 2

Let $n\ge 0$ , $t\ge 1$ be integers. Then (6) $$J_{t,n+2}+t\cdot J_{t,n}=j_{t,n+1}.$$(6)

Proof

By Induction on $n$ For $n=0$ we have $J_{t,2}+t\cdot J_{t,0}=1+t\cdot 0=1=j_{t,1}$.

Let $k\ge 0$ be given and suppose that (6) is true for all $n=0,1,2,\dots ,k$. We shall show that (6) holds for $n=k+1$. Using induction’s assumption for $n=k$ and $n=k-1$ and (1), (2) we have $$J_{t,(k+1)+2}+t\cdot J_{t,k+1}==J_{t,k+3}+t\cdot J_{t,k+1}==(J_{t,k+2}+t\cdot J_{t,k+1})+t\cdot \left(J_{t,k}+t\cdot J_{t,k-1}\right)==(J_{t,k+2}+t\cdot J_{t,k})+t\cdot \left(J_{t,k+1}+t\cdot J_{t,k-1}\right)==j_{t,k+1}+t\cdot j_{t,k}=j_{t,k+2}=j_{t,(k+1)+1}.$$

Thus, (6) holds for $n=k+1$, and the proof of the induction step is complete. □

Theorem 3

Let $n\ge 0$ , $t\ge 1$ be integers. Then (7) $$J_{t,n}+j_{t,n}=2\cdot J_{t,n+1}.$$(7)

Proof

By Induction on $n$ For $n=0$ we have $J_{t,0}+j_{t,0}=0+2=2\cdot 1=2\cdot J_{t,1}$.

Let $k\ge 0$ be given and suppose that (7) is true for all $n=0,1,2,\dots ,k$. We shall show that (7) holds for $n=k+1$. Using induction’s assumption for $n=k$ and $n=k-1$ and (1), (2) we have $$J_{t,k+1}+j_{t,k+1}==(J_{t,k}+t\cdot J_{t,k-1})+(j_{t,k}+t\cdot j_{t,k-1})==(J_{t,k}+j_{t,k})+t\cdot (J_{t,k-1}+j_{t,k-1})==2\cdot J_{t,k+1}+t\cdot 2\cdot J_{t,k}==2\cdot \left(J_{t,k+1}+t\cdot J_{t,k}\right)=2\cdot J_{t,k+2}=2\cdot J_{t,(k+1)+1}.$$

Thus, (7) holds for $n=k+1$, and the proof of the induction step is complete. □

Theorem 4

Let $n\ge 0$ , $t\ge 1$ be integers. Then (8) $$\sum _{i=0}^n{J}_{t,i}=\frac{J_{t,n+2}-J_{t,1}}{t}.$$(8)

Proof

Using (1) we have $J_{t,n}=\frac{1}{t}(J_{t,n+2}-J_{t,n+1})$.

For integers $0,1,\dots ,n$ we obtain $$J_{t,0}=\frac{1}{t}(J_{t,2}-J_{t,1})$$$$J_{t,1}=\frac{1}{t}(J_{t,3}-J_{t,2})$$$$J_{t,2}=\frac{1}{t}(J_{t,4}-J_{t,3})⋮$$$$J_{t,n-1}=\frac{1}{t}(J_{t,n+1}-J_{t,n})$$$$J_{t,n}=\frac{1}{t}(J_{t,n+2}-J_{t,n+1}).$$

Adding these equalities we obtain (8). □

In the same way one can easily prove the next theorem.

Theorem 5

Let $n\ge 0$ , $t\ge 1$ be integers. Then (9) $$\sum _{i=0}^n{j}_{t,i}=\frac{j_{t,n+2}-j_{t,1}}{t}.$$(9)

From the above theorems we obtain the well-known identities for Fibonacci numbers, Lucas numbers, Jacobsthal numbers and Jacobsthal–Lucas numbers.

Corollary 6

Let $n\ge 0$ be an integer. Then $$\sum _{i=0}^n{F}_i=F_{n+2}-F_1=F_{n+2}-1,\sum _{i=0}^n{L}_i=L_{n+2}-L_1=L_{n+2}-1,\sum _{i=0}^n{J}_i=\frac{J_{n+2}-J_1}{2}=\frac{J_{n+2}-1}{2},\sum _{i=0}^n{j}_i=\frac{j_{n+2}-j_1}{2}=\frac{j_{n+2}-1}{2}.$$

Some identities for numbers $J_{t,n}$ and $j_{t,n}$ can be found using their matrix generators.

For integers $n\ge 1$ and $t\ge 1$ let $J(t,n)=\left[\begin{array}{cc}{J}_{t,n}\hfill & J_{t,n-1}\hfill \\ J_{t,n+1}\hfill & J_{t,n}\hfill \end{array}\right]$be a matrix with entries being generalized Fibonacci numbers.

Theorem 7

Let $n\ge 1$ , $t\ge 1$ be integers. Then $$\left[\begin{array}{cc}{J}_{t,n}\hfill & J_{t,n-1}\hfill \\ J_{t,n+1}\hfill & J_{t,n}\hfill \end{array}\right]=\left[\begin{array}{cc}{J}_{t,1}\hfill & J_{t,0}\hfill \\ J_{t,2}\hfill & J_{t,1}\hfill \end{array}\right]\cdot {\left[\begin{array}{cc}1\hfill & 1\hfill \\ t\hfill & 0\hfill \end{array}\right]}^{n-1}.$$

Proof

By Induction on $n$ If $n=1$ then the result is obvious. Assume that $$\left[\begin{array}{cc}{J}_{t,n}\hfill & J_{t,n-1}\hfill \\ J_{t,n+1}\hfill & J_{t,n}\hfill \end{array}\right]=\left[\begin{array}{cc}{J}_{t,1}\hfill & J_{t,0}\hfill \\ J_{t,2}\hfill & J_{t,1}\hfill \end{array}\right]\cdot {\left[\begin{array}{cc}1\hfill & 1\hfill \\ t\hfill & 0\hfill \end{array}\right]}^{n-1}.$$We shall show that $$\left[\begin{array}{cc}{J}_{t,n+1}\hfill & J_{t,n}\hfill \\ J_{t,n+2}\hfill & J_{t,n+1}\hfill \end{array}\right]=\left[\begin{array}{cc}{J}_{t,1}\hfill & J_{t,0}\hfill \\ J_{t,2}\hfill & J_{t,1}\hfill \end{array}\right]\cdot {\left[\begin{array}{cc}1\hfill & 1\hfill \\ t\hfill & 0\hfill \end{array}\right]}^n.$$By simple calculation using induction’s hypothesis we have $$\left[\begin{array}{cc}{J}_{t,1}\hfill & J_{t,0}\hfill \\ J_{t,2}\hfill & J_{t,1}\hfill \end{array}\right]\cdot {\left[\begin{array}{cc}1\hfill & 1\hfill \\ t\hfill & 0\hfill \end{array}\right]}^{n-1}\cdot \left[\begin{array}{cc}1\hfill & 1\hfill \\ t\hfill & 0\hfill \end{array}\right]=\left[\begin{array}{cc}{J}_{t,n}\hfill & J_{t,n-1}\hfill \\ J_{t,n+1}\hfill & J_{t,n}\hfill \end{array}\right]\cdot \left[\begin{array}{cc}1\hfill & 1\hfill \\ t\hfill & 0\hfill \end{array}\right]=$$ $$=\left[\begin{array}{cc}{J}_{t,n}+t\cdot J_{t,n-1}\hfill & J_{t,n}\hfill \\ J_{t,n+1}+t\cdot J_{t,n}\hfill & J_{t,n+1}\hfill \end{array}\right]=\left[\begin{array}{cc}{J}_{t,n+1}\hfill & J_{t,n}\hfill \\ J_{t,n+2}\hfill & J_{t,n+1}\hfill \end{array}\right],$$which ends the proof. □

This generator immediately gives the Cassini formula for the generalized Fibonacci numbers.

Corollary 8

Let $n\ge 1$ , $t\ge 1$ be integers. Then $$J_{t,n}^2-J_{t,n-1}\cdot J_{t,n+1}=\left(J_{t,1}^2-J_{t,0}\cdot J_{t,2}\right)\cdot {(-t)}^{n-1}={(-t)}^{n-1}.$$

If $t=1$ and $t=2$ then we obtain the well-known Cassini formulas for the Fibonacci numbers and the Jacobsthal numbers, respectively.

Corollary 9

Let $n\ge 1$ be an integer. Then $$\begin{array}{c}\hfill F_n^2-F_{n-1}\cdot F_{n+1}={(-1)}^{n-1}\hfill \\ \hfill J_n^2-J_{n-1}\cdot J_{n+1}={(-2)}^{n-1}.\hfill \end{array}$$

Analogously we can define the matrix generator and the Cassini formula for the generalized Lucas numbers.

For integers $n\ge 1$ and $t\ge 1$ let $j(t,n)=\left[\begin{array}{cc}{j}_{t,n}\hfill & j_{t,n-1}\hfill \\ j_{t,n+1}\hfill & j_{t,n}\hfill \end{array}\right]$be a matrix with entries being generalized Lucas numbers.

Theorem 10

Let $n\ge 1$ , $t\ge 1$ be integers. Then $$\left[\begin{array}{cc}{j}_{t,n}\hfill & j_{t,n-1}\hfill \\ j_{t,n+1}\hfill & j_{t,n}\hfill \end{array}\right]=\left[\begin{array}{cc}{j}_{t,1}\hfill & j_{t,0}\hfill \\ j_{t,2}\hfill & j_{t,1}\hfill \end{array}\right]\cdot {\left[\begin{array}{cc}1\hfill & 1\hfill \\ t\hfill & 0\hfill \end{array}\right]}^{n-1}.$$

Corollary 11

Let $n\ge 1$ , $t\ge 1$ be integers. Then $$j_{t,n}^2-j_{t,n-1}\cdot j_{t,n+1}=(-1-4t)\cdot {(-t)}^{n-1}.$$

If $t=1$ and $t=2$ then we have the well-known Cassini formulas for the Lucas numbers and the Jacobsthal–Lucas numbers, respectively.

Corollary 12

Let $n\ge 1$ be an integer. Then $$\begin{array}{c}\hfill L_n^2-L_{n-1}\cdot L_{n+1}=-5\cdot {(-1)}^{n-1},\hfill \\ \hfill j_n^2-j_{n-1}\cdot j_{n+1}=-9\cdot {(-2)}^{n-1}.\hfill \end{array}$$