Find a Closed Form Solution for the Difference Equation

• Research
• Open Access
• Published: 23 July 2014

Closed-form solution of a general three-term recurrence relation

Advances in Difference Equations volume 2014, Article number:196 (2014) Cite this article

• 5675 Accesses

• 2 Citations

• Metrics details

Abstract

We present a closed-form solution for n th term of a general three-term recurrence relation with arbitrary given n-dependent coefficients. The derivation and corresponding proof are based on two approaches, which we develop and describe in detail. First, the recursive-sum theory, which gives the exact solution in a compact finite form using a recursive indexing. Second, the discrete dimensional-convolution procedure, which transforms the solution to the non-recursive expression of n, including a finite number of elementary operations and functions.

1 Introduction

A general three-term recurrence relation is usually defined by the following expression:

W_{n+1} = A_n W_n + B_n W_{n-1} ,

(1)

where n \ge 1 (n \in \mathbb{N}), W_n is unknown function of n, A_n and B_n are arbitrary given functions of n, and W_0 = C_0, W_1 = C_1 are initial conditions (we assume not to have the trivial case when C_1 = C_0 = 0 and W_n \equiv 0).

This well-known relation has a large number of applications and plays an important role in many areas of mathematics and physics. We recall here a few of them to underline the importance of the proposed statement.

First, the recurrence relation Eq. (1) corresponds to the finite difference equation for the general second order differential equation with unknown function f ( x ) and arbitrary given U ( x ), namely: f^{″} - U ( x ) \cdot f = 0. Therefore, it is widely used for the analytical and numerical analysis (and approximations) in corresponding physical and mathematical applications; see for example [1].

Second, three-term recurrence relations appear naturally when one uses the Frobenius method for solving some linear differential equations and studying some special functions; see [2].

Third, Eq. (1) corresponds to a continued fraction with arbitrary given coefficients. Basically, the three-term recurrence relation corresponds to the expressions for the numerators and denominators of this continued fraction (see Chapter IV in [3]), which were derived by Euler.

In this manuscript we obtain a closed-form solution of a canonical three-term recurrence relation, which is equivalent to Eq. (1) in the case of (A_n \ne 0, ∀ n). Our goal is to obtain the solution consisting of a finite number of terms, rather than a variety of methods with infinite series [4]. In that way we develop two approaches for the expressions with a finite number of terms. We start with the recursive-sum theory, which is presented in Section 3. It allows one to obtain the exact solution of the three-term recurrence relation in a compact form using recursive indexing. Next, we develop the discrete dimensional-convolution procedure, which allows one to eliminate recursive indexing and to represent the solution as a closed-form expression. It means that the final closed-form expression depends on arbitrary given coefficients and includes a finite number of elementary operations, such as: '+', '−', '×', '÷'; and elementary functions, such as the Heaviside step function (or unit step function) and the floor function for integer division.

2 Preliminaries

Let us start from the simplification of Eq. (1). For this we assume that A_n \ne 0, ∀ n (in the opposite case, the recurrence relation near numbers of zero A-coefficients has other fundamental properties and it should be considered separately). Thus, we can use the following substitution:

W_{n+1} = a_{n+1} \cdot \prod _{i=1}^n A_i .

(2)

According to this substitution and Eq. (1), a_n fulfills the following three-term recurrence relation:

a_{n+1} = a_n + \frac{B_n}{A_n{A}_{n-1}} \cdot a_{n-1} .

(3)

Since Eq. (1), Eq. (3) are linear and n, A_n, B_n are arbitrary, we can assume without loss of generality the following initial conditions: a_0 = 1, a_1 = 1. Finally, we specify d_n = B_n \cdot {(A_n{A}_{n-1})}^{-1} as an arbitrary given function of n, and write below the expression, which we further call the canonical three-term recurrence relation:

\begin{array}{r}{a}_{n+1}=a_n+d_n\cdot a_{n-1},\\ a_0=1,a_1=1.\end{array}

(4)

We note that the solution of Eq. (4) consists of a sum of d_i-products (i \in \mathbb{N}) with different powers. Here the product power p is equal to the total number of d_i in the product. The maximum power of a_{n+1}, i.e. the largest power among all the products in a_{n+1}, is equal to 〚 ( n + 1 ) / 2 〛, since

〚(n+1)/2〛 = max (〚n/2〛,1+〚(n-1)/2〛) , \mathrm{\forall } n ,

(5)

where we use Gauss notation for the integer division: 〚 x 〛 = \lfloor x \rfloor = max ( m \in \mathbb{Z} \mid m \le x ). Because of this fundamental characteristic it is natural to express a_{n+1}, i.e. the solution of Eq. (4), in the following form:

a_{n+1} = 1 + \sum _{p=1}^{〚(n+1)/2〛} S ( n , p ) ,

(6)

where S ( n , p ) includes all terms of the power p. In the next sections we demonstrate that each S ( n , p ) is equal to the corresponding recursive-sum, and we rigorously prove all the propositions.

3 Recursive-sum theory

In this section we start from the definition of a general recursive-sum (R-sum). Next, we present and prove some of its properties, which determine the R-sum algebra. It could be useful for solving different recurrence relations, but, particularly for the solution of the canonical three-term recurrence relation it is sufficient to use a particular case of the R-sum, namely the reduced R-sum, which is described in the next section.

Definition 1 A general R-sum (R) is defined for the ordered sequence ( d_i , i \in \mathbb{Z} ) by the following expression:

\mathbf{R} = \mathbf{R} ( N , k , \mathrm{\Delta } , {\mathrm{\Delta }}_0 ) = \prod _{m=1}^k \left[\sum _{i_m=i_{m-1}+\mathrm{\Delta }}^{N+m\cdot \mathrm{\Delta }}{d}_{i_m}\right] ,

(7)

where (N , k , \mathrm{\Delta } , {\mathrm{\Delta }}_0 \in \mathbb{Z}), i_0 \equiv {\mathrm{\Delta }}_0, N is the order of the R-sum, k \ge 1 is the power of the R-sum, Δ is the recursive shift of the R-sum, {\mathrm{\Delta }}_0 is the initial shift of the R-sum. For the correct definition it is also assumed that N \ge {\mathrm{\Delta }}_0 and d_i is defined for all indices used in Eq. (7). The product in Eq. (7) corresponds to the standard left-to-right order of multiplication, so the definition can be written also in the following way:

\begin{array}{c}\mathbf{R}(N,1,\mathrm{\Delta },{\mathrm{\Delta }}_0)=\sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{N+\mathrm{\Delta }}{d}_{i_1},\hfill \\ \mathbf{R}(N,2,\mathrm{\Delta },{\mathrm{\Delta }}_0)=\sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{N+\mathrm{\Delta }}{d}_{i_1}\cdot \sum _{i_2=i_1+\mathrm{\Delta }}^{N+2\mathrm{\Delta }}{d}_{i_2},\hfill \\ \mathbf{R}(N,3,\mathrm{\Delta },{\mathrm{\Delta }}_0)=\sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{N+\mathrm{\Delta }}{d}_{i_1}\cdot \sum _{i_2=i_1+\mathrm{\Delta }}^{N+2\mathrm{\Delta }}{d}_{i_2}\cdot \sum _{i_3=i_2+\mathrm{\Delta }}^{N+3\mathrm{\Delta }}{d}_{i_3},\hfill \\ ⋮\hfill \\ \mathbf{R}(N,k,\mathrm{\Delta },{\mathrm{\Delta }}_0)=\sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{N+\mathrm{\Delta }}{d}_{i_1}\cdot \sum _{i_2=i_1+\mathrm{\Delta }}^{N+2\mathrm{\Delta }}{d}_{i_2}\cdot \cdots \cdot \sum _{i_{k-1}=i_{k-2}+\mathrm{\Delta }}^{N+(k-1)\mathrm{\Delta }}{d}_{i_{k-1}}\cdot \sum _{i_k=i_{k-1}+\mathrm{\Delta }}^{N+k\mathrm{\Delta }}{d}_{i_k}.\hfill \end{array}

(8)

Next, we present some of the elementary properties of the R-sum, P.(1)-P.(3), which follow directly from the definition.

P.(1):

\mathbf{R} ( N , k , \mathrm{\Delta } , N ) = \prod _{j=1}^k d_{N+j\cdot \mathrm{\Delta }} .

(9)

P.(2):

\mathbf{R} ( N , k + 1 , \mathrm{\Delta } , {\mathrm{\Delta }}_0 ) = \sum _{j={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{N+\mathrm{\Delta }} d_j \cdot \mathbf{R} ( N + \mathrm{\Delta } , k , \mathrm{\Delta } , j ) .

(10)

P.(3):

\begin{array}{c}\mathbf{R}(N,k,\mathrm{\Delta },{\mathrm{\Delta }}_0+1)\hfill \\ =\mathbf{R}(N,k,\mathrm{\Delta },{\mathrm{\Delta }}_0)-d_{{\mathrm{\Delta }}_0+\mathrm{\Delta }}\cdot \mathbf{R}(N+\mathrm{\Delta },k-1,\mathrm{\Delta },{\mathrm{\Delta }}_0+\mathrm{\Delta }).\hfill \end{array}

(11)

Finally, we consider the R-sum key lemma: If N \ge {\mathrm{\Delta }}_0 + 1, then

\mathbf{R} ( N , k + 1 , \mathrm{\Delta } , {\mathrm{\Delta }}_0 ) = \mathbf{R} ( N - 1 , k + 1 , \mathrm{\Delta } , {\mathrm{\Delta }}_0 ) + d_{N+(k+1)\mathrm{\Delta }} \cdot \mathbf{R} ( N , k , \mathrm{\Delta } , {\mathrm{\Delta }}_0 ) .

(12)

Proof of the key lemma First, we consider the difference \mathbf{D} = [ \mathbf{R} ( N , k + 1 , \mathrm{\Delta } , {\mathrm{\Delta }}_0 ) - d_{N+(k+1)\mathrm{\Delta }} \cdot \mathbf{R} ( N , k , \mathrm{\Delta } , {\mathrm{\Delta }}_0 ) ] and try to eliminate the index numbers which correspond to zero terms in the original expression. For the correct procedure (when an upper bound in each sum is never less than the lower one) we will eliminate the zero terms and delete the corresponding index numbers step by step from i_1 to i_{k+1}. We have

\mathbf{D} = \sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{N+\mathrm{\Delta }} d_{i_1} \cdot \sum _{i_2=i_1+\mathrm{\Delta }}^{N+2\mathrm{\Delta }} d_{i_2} \cdot \cdots \cdot \sum _{i_k=i_{k-1}+\mathrm{\Delta }}^{N+k\mathrm{\Delta }} d_{i_k} \cdot [\sum _{i_{k+1}=i_k+\mathrm{\Delta }}^{N+(k+1)\mathrm{\Delta }}{d}_{i_{k+1}}-d_{N+(k+1)\mathrm{\Delta }}] .

(13)

At the next step we note that for i_1 = N + \mathrm{\Delta } according to the definition we have only one value, i_2 = N + 2 \mathrm{\Delta }, and one term, d_{N+2\mathrm{\Delta }}, in the second sum in Eq. (13). According to the definition and P.(1) the same is true for the other indices: i_3 = N + 3 \mathrm{\Delta } , \dots , i_k = N + k \mathrm{\Delta }. The last term in Eq. (13) gives [ {\sum }_{i_{k+1}=N+k\mathrm{\Delta }+\mathrm{\Delta }}^{N+(k+1)\mathrm{\Delta }} d_{i_{k+1}} - d_{N+(k+1)\mathrm{\Delta }} ] \equiv 0. This means that all the terms in Eq. (13) which correspond to i_1 = N + \mathrm{\Delta } are equal to zero. Since the condition (N \ge {\mathrm{\Delta }}_0 + 1), we can then write

\mathbf{D} = \sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{(N-1)+\mathrm{\Delta }} d_{i_1} \cdot \sum _{i_2=i_1+\mathrm{\Delta }}^{N+2\mathrm{\Delta }} d_{i_2} \cdot \cdots \cdot \sum _{i_k=i_{k-1}+\mathrm{\Delta }}^{N+k\mathrm{\Delta }} d_{i_k} \cdot [\sum _{i_{k+1}=i_k+\mathrm{\Delta }}^{N+(k+1)\mathrm{\Delta }}{d}_{i_{k+1}}-d_{N+(k+1)\mathrm{\Delta }}] .

(14)

The same procedure can be repeated for any successive indices. Consider the m th sum (m \le k) in Eq. (13). For each i_m = N + m \mathrm{\Delta } we have only one term in the next sum, corresponding to i_{m+1} = N + ( m + 1 ) \mathrm{\Delta }, and so on until the last term: [ {\sum }_{i_{k+1}=N+k\mathrm{\Delta }+\mathrm{\Delta }}^{N+(k+1)\mathrm{\Delta }} d_{i_{k+1}} - d_{N+(k+1)\mathrm{\Delta }} ] \equiv 0. So we can delete all the corresponding index numbers and write

\mathbf{D} = \sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{(N-1)+\mathrm{\Delta }} d_{i_1} \cdot \sum _{i_2=i_1+\mathrm{\Delta }}^{(N-1)+2\mathrm{\Delta }} d_{i_2} \cdot \cdots \cdot \sum _{i_k=i_{k-1}+\mathrm{\Delta }}^{(N-1)+k\mathrm{\Delta }} d_{i_k} \cdot [\sum _{i_{k+1}=i_k+\mathrm{\Delta }}^{N+(k+1)\mathrm{\Delta }}{d}_{i_{k+1}}-d_{N+(k+1)\mathrm{\Delta }}] .

(15)

Finally, we note that [ {\sum }_{i_{k+1}=i_k+\mathrm{\Delta }}^{N+(k+1)\mathrm{\Delta }} d_{i_{k+1}} - d_{N+(k+1)\mathrm{\Delta }} ] = {\sum }_{i_{k+1}=i_k+\mathrm{\Delta }}^{(N-1)+(k+1)\mathrm{\Delta }} d_{i_{k+1}}. Thus we obtain

\begin{array}{rl}\mathbf{D}& =\sum _{i_1={\mathrm{\Delta }}_0+\mathrm{\Delta }}^{(N-1)+\mathrm{\Delta }}{d}_{i_1}\cdot \sum _{i_2=i_1+\mathrm{\Delta }}^{(N-1)+2\mathrm{\Delta }}{d}_{i_2}\cdot \cdots \cdot \sum _{i_k=i_{k-1}+\mathrm{\Delta }}^{(N-1)+k\mathrm{\Delta }}{d}_{i_k}\cdot \sum _{i_{k+1}=i_k+\mathrm{\Delta }}^{(N-1)+(k+1)\mathrm{\Delta }}{d}_{i_{k+1}}\\ =\mathbf{R}(N-1,k+1,\mathrm{\Delta },{\mathrm{\Delta }}_0),\end{array}

(16)

which proves the key lemma. □

4 Exact solution of a canonical three-term recurrence relation via finite R-sum expansion

In this section we start with a definition of a reduced R-sum, a particular case of the general R-sum. Then we construct the exact solution of the canonical three-term recurrence relation, by using the R-sum key lemma.

Definition 2 A reduced R-sum (\tilde{\mathbf{R}}) is a particular case of the general R-sum (see Eqs. (7)-(8)), defined by the following expression:

\tilde{\mathbf{R}} = \tilde{\mathbf{R}} ( N , k ) = \mathbf{R} ( N , k , 2 , - 1 ) = \sum _{i_1=1}^{N+2} d_{i_1} \cdot \sum _{i_2=i_1+2}^{N+4} d_{i_2} \cdot \cdots \cdot \sum _{i_{k-1}=i_{k-2}+2}^{N+2(k-1)} d_{i_{k-1}} \cdot \sum _{i_k=i_{k-1}+2}^{N+2k} d_{i_k} .

(17)

The key lemma Eq. (12) gives the following for the reduced R-sum:

\tilde{\mathbf{R}} ( N , k + 1 ) = \tilde{\mathbf{R}} ( N - 1 , k + 1 ) + d_{N+2(k+1)} \cdot \tilde{\mathbf{R}} ( N , k ) .

(18)

Since N and k are independent and arbitrary, let us consider them as functions of new numbers n and p: N = N ( n , p ) = n - 2 p; k = k ( n , p ) = p. In that way we consider a new subsidiary function:

S ( n , p ) = \tilde{\mathbf{R}} ( n - 2 p , p ) .

(19)

According to the previous notations we have N ( n , p ) = n - 2 p = n - 2 k = N ( n + 2 , p + 1 ) = N ( n + 1 , p + 1 ) + 1. Thus we can write the analog of the key lemma for the S function, by using Eqs. (18) and (19):

S ( n + 2 , p + 1 ) = S ( n + 1 , p + 1 ) + d_{n+2} \cdot S ( n , p ) .

(20)

Now, we will rigorously prove a theorem about the exact solution of a canonical three-term recurrence relation Eq. (4).

Theorem 1 An exact solution of Eq. (4) is the following:

a_{n+1} = 1 + \sum _{p=1}^{〚(n+1)/2〛} S ( n , p ) .

(21)

Proof Our proof is based on mathematical induction. Base cases:

\begin{array}{r}n=1\text{:}{a}_2=1+d_1=1+\sum _{p=1}^{1}S(1,p),\\ n=2\text{:}{a}_3=1+d_1+d_2=1+\sum _{p=1}^{1}S(2,p),\\ n=3\text{:}{a}_4=1+d_1+d_2+d_3+d_1{d}_3=1+\sum _{p=1}^{2}S(3,p),\\ n=4\text{:}{a}_5=1+d_1+d_2+d_3+d_4+d_1{d}_3+d_1{d}_4+d_2{d}_4=1+\sum _{p=1}^{2}S(4,p).\end{array}

(22)

Inductive step: we will prove that the statement Eq. (21) for a_n and a_{n-1}, ∀ n, gives the following:

a_n + d_n \cdot a_{n-1} = a_{n+1} .

(23)

To prove it for all n, we consider below two cases. First case: n is an arbitrary even number, n = 2 m, m \in \mathbb{N}. Second case: n is an arbitrary odd number, n = 2 m + 1, m \in \mathbb{N}.

First case, n = 2 m.

a_n + d_n \cdot a_{n-1} = a_{2m} + d_{2m} \cdot a_{2m-1} = 1 + d_{2m} + \sum _{l=1}^m S ( 2 m - 1 , l ) + d_{2m} \cdot \sum _{p=1}^{m-1} S ( 2 m - 2 , p ) .

(24)

Note that {\sum }_{l=1}^m S ( 2 m - 1 , l ) = S ( 2 m - 1 , 1 ) + {\sum }_{l=2}^m S ( 2 m - 1 , l ) = S ( 2 m - 1 , 1 ) + {\sum }_{p=1}^{m-1} S ( 2 m - 1 , p + 1 ). After the substitution we have

\begin{array}{rl}{a}_n+d_n\cdot a_{n-1}& =1+d_{2m}+S(2m-1,1)+\sum _{p=1}^{m-1}S(2m-1,p+1)+d_{2m}\cdot \sum _{p=1}^{m-1}S(2m-2,p)\\ =1+d_{2m}+S(2m-1,1)+\sum _{p=1}^{m-1}[S(2m-1,p+1)+d_{2m}\cdot S(2m-2,p)].\end{array}

(25)

According to Eq. (20) we can write S ( 2 m - 1 , p + 1 ) + d_{2m} \cdot S ( 2 m - 2 , p ) = S ( 2 m , p + 1 ). Also, according to the definitions Eq. (17) and Eq. (19) we can write d_{2m} + S ( 2 m - 1 , 1 ) = d_{2m} + {\sum }_{j=1}^{2m-1} d_j = {\sum }_{j=1}^{2m} d_j = S ( 2 m , 1 ). Thus, we can obtain

\begin{array}{rl}{a}_n+d_n\cdot a_{n-1}& =1+S(2m,1)+\sum _{p=1}^{m-1}S(2m,p+1)\\ =1+S(2m,1)+\sum _{p=2}^{m}S(2m,p)=1+\sum _{p=1}^{m}S(2m,p)=a_{n+1},\end{array}

(26)

which proves the first case of the theorem.

Second case, n = 2 m + 1.

We have

\begin{array}{rl}{a}_n+d_n\cdot a_{n-1}& =a_{2m+1}+d_{2m+1}\cdot a_{2m}\\ =1+d_{2m+1}+\sum _{l=1}^{m}S(2m,l)+d_{2m+1}\cdot \sum _{p=1}^{m}S(2m-1,p).\end{array}

(27)

Similar to the previous case, we write {\sum }_{l=1}^m S ( 2 m , l ) = S ( 2 m , 1 ) + {\sum }_{p=1}^{m-1} S ( 2 m , p + 1 ). Also we note that {\sum }_{p=1}^m S ( 2 m - 1 , p ) = {\sum }_{p=1}^{m-1} S ( 2 m - 1 , p ) + S ( 2 m - 1 , m ). Thus, we can write

\begin{array}{rcl}{a}_n+d_n\cdot a_{n-1}& =& 1+d_{2m+1}+S(2m,1)+d_{2m+1}S(2m-1,m)\\ +\sum _{p=1}^{m-1}[S(2m,p+1)+d_{2m+1}\cdot S(2m-1,p)].\end{array}

(28)

According to Eq. (20) we again can rewrite S ( 2 m , p + 1 ) + d_{2m+1} \cdot S ( 2 m - 1 , p ) = S ( 2 m + 1 , p + 1 ). In addition we note that {\sum }_{p=1}^{m-1} S ( 2 m + 1 , p + 1 ) = {\sum }_{p=2}^m S ( 2 m + 1 , p ). Summarizing, we obtain

a_n + d_n \cdot a_{n-1} = 1 + d_{2m+1} + S ( 2 m , 1 ) + d_{2m+1} S ( 2 m - 1 , m ) + \sum _{p=2}^m S ( 2 m + 1 , p ) .

(29)

Finally, we note that d_{2m+1} S ( 2 m - 1 , m ) = d_{2m+1} \tilde{\mathbf{R}} ( - 1 , m ) = d_{2m+1} {\prod }_{j=1}^m d_{2j-1} = \tilde{\mathbf{R}} ( - 1 , m + 1 ) = S ( 2 m + 1 , m + 1 ). In addition, we can write d_{2m+1} + S ( 2 m , 1 ) = d_{2m+1} + {\sum }_{j=1}^{2m} d_j = {\sum }_{j=1}^{2m+1} d_j = S ( 2 m + 1 , 1 ). This gives us the final result:

\begin{array}{rl}{a}_n+d_n\cdot a_{n-1}& =1+S(2m+1,1)+S(2m+1,m+1)+\sum _{p=2}^{m}S(2m+1,p)\\ =1+\sum _{p=1}^{m+1}S(2m+1,p)=a_{n+1},\end{array}

(30)

which proves the second case and Theorem 1. □

5 Discrete dimensional-convolution procedure

In this section we develop a procedure which could be used for the transformation of the exact solution Eq. (21) to the expression without recursive indexing.

Let us start from a simple case to demonstrate the idea of the discrete dimensional-convolution procedure. We consider a simple expression, which can be associated with a particular case of R-sum:

E_2 = \sum _{i_1=1}^{N_1} \sum _{i_2=i_1+\delta }^{N_2} f ( i_1 , i_2 ) ,

(31)

where N_1 , N_2 \in \mathbb{N} (N_1 \le N_2) are arbitrary given natural numbers; \delta \in \mathbb{N} (0 \le \delta \le [ N_2 - N_1 ]) is an arbitrary given natural number (shift); and f ( i_1 , i_2 ) is an arbitrary given function of natural index numbers i_1 and i_2. The previous expression E_2 can be rewritten as follows:

E_2 = \sum _{i_1=1}^{N_1} \sum _{i_2=1}^{N_2} F ( i_1 , i_2 ) ,

(32)

where F ( i_1 , i_2 ) = f ( i_1 , i_2 ) \cdot H ( i_2 - i_1 - \delta ), and H ( x ) is Heaviside step function (or unit step function):

(33)

Let us consider now Eq. (32). The indices i_1 and i_2 can be associated with two dimensions by the following way. Let us consider a two dimensional plot (array with elements F ( i_1 , i_2 )) with horizontal numbering related to the i_2 index and vertical numbering related to the i_1 index;

\left[ \begin{array}{cccc}F(1,1)& F(1,2)& \cdots & F(1,N_2)\\ F(2,1)& F(2,2)& \cdots & F(2,N_2)\\ ⋮& \ddots & ⋮\\ F(N_1,1)& F(N_1,2)& \cdots & F(N_1,N_2)\end{array} \right] .

For numbering of this array of elements it is possible to use a traversal rule with one global index q \in [ 1 , \dots , N_1 \cdot N_2 ] instead of i_1 \in [ 1 , \dots , N_1 ] and i_2 \in [ 1 , \dots , N_2 ]. Consider, for example, the following rule: q = i_1 + N_1 \cdot ( i_2 - 1 ), with the corresponding relations:^a i_1 = i_1 ( q ) = 1 + N_1 \{ ( q - 1 ) / N_1 \} = q - N_1 〚 ( q - 1 ) / N_1 〛, i_2 = i_2 ( q ) = 1 + 〚 ( q - 1 ) / N_1 〛. Since, for the presented rule, a unique combination of ( i_1 , i_2 ) corresponds to a certain unique number q and vice versa (i.e. we have one-to-one mapping), we can rewrite Eq. (32) in the following form:

E_2 = \sum _{q=1}^{N_1\cdot N_2} F (1+N_1\{(q-1)/N_1\},1+〚(q-1)/N_1〛) .

(34)

The presented procedure, i.e. the reduction from two dimensions to one dimension, is a particular case of discrete dimensional-convolution procedure. Let us now generalize it to a multidimensional case. In that way we consider a multidimensional analog of Eq. (32):

E_k = \sum _{i_1=1}^{N_1} \sum _{i_2=1}^{N_2} \cdots \sum _{i_k=1}^{N_k} F ( i_1 , i_2 , \dots , i_k ) ,

(35)

where (k \in \mathbb{N}), k \ge 3, is an arbitrary given natural number, ( N_1 , N_2 , \dots , N_k \in \mathbb{N} ) is an array of arbitrary given natural numbers, and F ( i_1 , i_2 , \dots , i_k ) is an arbitrary given function of i_1 , i_2 , \dots , i_k.

Let us now define a global index q as follows:

q = i_1 + N_1 ( i_2 - 1 ) + N_1 N_2 ( i_3 - 1 ) + \cdots + \left[\prod _{j=1}^{k-1}{N}_j\right] ( i_k - 1 ) .

(36)

Note that the minimum value q_{\min } = 1 corresponds to the case that every index number is equal to unity. The maximum value q_{\max } = N_1 \cdot N_2 \cdot \cdots \cdot N_k corresponds to the case that every index number reaches its maximum, since we have the relation

N_1 + N_1 ( N_2 - 1 ) + N_1 N_2 ( N_3 - 1 ) + \cdots + \left[\prod _{j=1}^{k-1}{N}_j\right] ( N_k - 1 ) = \left[\prod _{j=1}^k{N}_j\right] .

(37)

Now we construct one-to-one mapping between the global index q and the index numbers ( i_1 , \dots , i_k ). For that we need to solve Eq. (36), i.e. to express any certain index number as a function of q (not depending on any other index numbers). We do that separately for i_1, i_k, and all others, i_r (2 \le r \le [ k - 1 ], r \in \mathbb{N}).

Obtaining of i_1: Since , the expression \{ ( q - 1 ) / N_1 \} does not depend on any index numbers except i_1. Thus, we obtain

i_1 = i_1 ( q ) = 1 + N_1 \{(q-1)/N_1\} .

(38)

Obtaining of i_k: Since (see Eq. (36)), the expression 〚 ( q - 1 ) / {\prod }_{j=1}^{k-1} N_j 〛 does not depend on any index numbers except i_k. Thus we obtain

i_k = i_k ( q ) = 1 + 〚(q-1)/\prod _{j=1}^{k-1}{N}_j〛 .

(39)

Obtaining of i_r (2 \le r \le [ k - 1 ]): Here we make two steps, similar to the previous cases, in order to eliminate the dependence of higher and lower index numbers separately. Consider the following expression:

h_r = h_r ( i_1 , \dots , i_r ) = i_1 + \cdots + \left[\prod _{j=1}^{r-1}{N}_j\right] ( i_r - 1 ) .

(40)

According to Eq. (37) we have . In addition, we have the simple relations \{ u / v \} \cdot v \equiv u for , and \{ u / v \} \cdot v \equiv 0 for ( u / v ) \in \mathbb{N}. Thus we obtain

h_r = 1 + \{(q-1)/\prod _{j=1}^r{N}_j\} \cdot \prod _{j=1}^r N_j .

(41)

Next, we perform a step similar to the one we performed when obtaining i_k (see also Eq. (39)):

i_r = 1 + 〚(h_r-1)/\prod _{j=1}^{r-1}{N}_j〛 .

(42)

Finally, we can write

i_r = i_r ( q ) = 1 + 〚 N_r \{(q-1)/\prod _{j=1}^r{N}_j\} 〛 .

(43)

As can be seen, Eq. (38) corresponds to Eq. (43) if we put formally r = 1. In addition, we can write ( q - 1 ) \equiv \{ ( q - 1 ) / {\prod }_{j=1}^k N_j \} \cdot {\prod }_{j=1}^k N_j. This means that Eq. (39) also corresponds to Eq. (43) if we put formally r = k. Thus we can write the described substitution for the discrete dimensional-convolution procedure in the following form:

\begin{array}{r}q=i_1+N_1(i_2-1)+N_1{N}_2(i_3-1)+\cdots +\left[\prod _{j=1}^{k-1}{N}_j\right](i_k-1),q\in [1,\dots ,\prod _{j=1}^k{N}_j];\\ i_r=1+〚N_r\{(q-1)/\prod _{j=1}^r{N}_j\}〛,r\in [1,\dots ,k].\end{array}

(44)

According to the previous equations every certain unique index number combination corresponds to the unique value of q. In addition, the total number of different index number combinations is equal to the total number of different values of q. Thus, we can conclude that Eq. (44) describes the one-to-one mapping for Eq. (35), and we can write

E_k = \sum _{q=1}^{N_1\cdot N_2\cdot \cdots \cdot N_k} F (i_1(q),\dots ,i_k(q)) .

(45)

Summarizing, the proposed procedure allows one to calculate a reduced R-sum without recursive indexing.

6 Closed-form solution of the canonical three-term recurrence relation

In this section we apply the previous results, in order to obtain the closed-form solution of Eq. (4) without recursive indexing. By using the exact solution via R-sum expansion Eq. (21), the definition of the reduced R-sum Eq. (17), and the procedure described in the previous section, we can write

\begin{array}{c}{a}_{n+1}=1+\sum _{p=1}^{〚(n+1)/2〛}\tilde{\mathbf{R}}(n-2p,p),\hfill \\ \tilde{\mathbf{R}}(n-2p,p)=\sum _{i_1=1}^{N_1}\sum _{i_2=1}^{N_2}\cdots \sum _{i_p=1}^{N_p}\left(\prod _{m=1}^p[d_{i_m}H(i_m-i_{m-1}-2)]\right)\hfill \\ \phantom{\tilde{\mathbf{R}}(n-2p,p)}=\sum _{i_1=1}^{N_1}\sum _{i_2=1}^{N_2}\cdots \sum _{i_p=1}^{N_p}\tilde{F}(i_1,i_2,\dots ,i_p),\hfill \end{array}

(46)

where i_0 \equiv - 1, N_j = n - 2 p + 2 j (1 \le j \le p, j \in \mathbb{N}), and H ( x ) is the unit step function (see Eq. (33)).

Now, we apply the results from the previous section Eqs. (44)-(45) in order to replace the recursive indexing by one global index q. For that we introduce new integer-valued function g = g ( m , n , p , q ) which is associated with a recursive index i_m (1 \le m \le p, m \in \mathbb{N}):

g ( m , n , p , q ) = 1 + 〚(n-2p+2m)\{(q-1)/\prod _{j=1}^m(n-2p+2j)\}〛 .

(47)

By using this function and Eqs. (45)-(46) we can obtain finally the closed-form solution^b

\begin{array}{c}{a}_{n+1}=1+\sum _{p=1}^{〚(n+1)/2〛}\sum _{q=1}^{M(n,p)}\prod _{m=1}^p[d_{g(m,n,p,q)}\cdot H[g(m,n,p,q)-g(m-1,n,p,q)-2]],\hfill \\ \text{where}M(n,p)=\prod _{j=1}^p{N}_j=\prod _{j=1}^p(n-2p+2j)=\frac{n!!(n-2p+2)}{(n-2p+2)!!}.\hfill \end{array}

(48)

Remark The integer-valued function g ( m , n , p , q ) \in [ 1 , \dots , n ] determines the index number of arbitrary given d_{\text{(index number)}} in the canonical three-term recurrence relation; see Eq. (4). The first term in the d-products in Eq. (48) is d_{g(1,n,p,q)} according to Eq. (46) and the corresponding condition i_0 \equiv - 1, so for the brevity in our notation we imply: g ( 0 , n , p , q ) \equiv - 1.

7 Fibonacci numbers

An important particular case of the canonical three-term recurrence relation is the well-known Fibonacci sequence, which corresponds to the case d_n \equiv 1 in Eq. (4). Thus, the Fibonacci numbers (F_n) satisfy the following relation:

\begin{array}{r}{F}_{n+1}=F_n+F_{n-1},\\ F_0=1,F_1=1.\end{array}

(49)

The Fibonacci number (F_{n+1}) corresponds to the total number of terms (d-products) in the solution a_{n+1} of the canonical three-term recurrence relation since the exact solution consists of a sum of unique combinations of d_i products; see Eqs. (4)-(5) and Eqs. (46)-(48).

The closed-form solution of Fibonacci sequence has well been known at least since the discovery of Abraham de Moivre, however, we can obtain it also by using our results, namely, Eq. (21) or Eq. (48):

\begin{array}{rl}{F}_{n+1}& =1+\sum _{p=1}^{〚(n+1)/2〛}(\sum _{i_1=1}^{n-2p+2}\sum _{i_2=i_1+2}^{n-2p+4}\cdots \sum _{i_{p-1}=i_{p-2}+2}^{n-2}\sum _{i_p=i_{p-1}+2}^{n}1)\\ =1+\sum _{p=1}^{〚(n+1)/2〛}\sum _{q=1}^{M(n,p)}\prod _{m=1}^{p}H[g(m,n,p,q)-g(m-1,n,p,q)-2],\end{array}

(50)

where g ( m , n , p , q ) and M ( n , p ) are introduced in Eqs. (47)-(48), and H ( x ) is the unit step function; see Eq. (33).

This expression gives the exact solution of the Fibonacci sequence without involving irrational numbers; the solution includes only certain combinations of natural numbers.

8 Conclusions

In summary, we obtain the closed-form solution of a canonical three-term recurrence relation Eq. (4) with an arbitrary given n-dependent coefficient d_n. The final non-recursive expression Eq. (48) includes a finite number of elementary operations and functions.

Possible applications of the developed approaches, namely the R-sum theory and the discrete dimensional-convolution procedure, are not limited by the considered statement. Due to its universality, they could be used for solving other recursive problems, in particular many-term recurrence relations.

An interesting and open question for the author is how the solution Eq. (48) could be efficiently used for approximations and solving differential equations.

Endnotes

We use the following notations: \{ x \} = x - 〚 x 〛, 〚 x 〛 = \lfloor x \rfloor = max ( m \in \mathbb{Z} \mid m \le x ).

We define double factorial for an arbitrary number m \in \mathbb{N} as follows: m ! ! = m \cdot ( m - 2 ) \cdot ( m - 4 ) \cdot \cdots \cdot 1.

References

Acknowledgements

IG would like to thank his wife Alla for her help and understanding during the preparation of the manuscript.

Author information

Affiliations

1. Department of Physics, Umeå University, Umeå, 90187, Sweden

   Ivan Gonoskov

Corresponding author

Correspondence to Ivan Gonoskov.

Additional information

Competing interests

The author declares that he has no competing interests.

Authors' contributions

IG has made all substantive intellectual contributions to the published study.

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits use, duplication, adaptation, distribution, and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reprints and Permissions

About this article

Cite this article

Gonoskov, I. Closed-form solution of a general three-term recurrence relation. Adv Differ Equ 2014, 196 (2014). https://doi.org/10.1186/1687-1847-2014-196

Download citation

• Received: 21 March 2014

• Accepted: 25 June 2014

• Published: 23 July 2014

• DOI : https://doi.org/10.1186/1687-1847-2014-196

Keywords

• Exact Solution
• Recurrence Relation
• Index Number
• Global Index
• Elementary Operation

Find a Closed Form Solution for the Difference Equation

Source: https://advancesindifferenceequations.springeropen.com/articles/10.1186/1687-1847-2014-196

Share :