# General formula for the 1; 5; 19; 65; 211 sequence

I have got array $1; 5;19; 65; 211$. Can I find general formula for my array?

For example, general formula for array $1; 2; 6; 24; 120$ is $n!$.

I tried a lot for finding the general formula, but I only found recurrent formula: $a_{n+1} = 5a_{n}-6a_{n-1}$.

Any help will be much appreciated.

• – lab bhattacharjee May 18 '16 at 16:53
• Here is one (out of infinitely many). – barak manos May 18 '16 at 17:01
• OEIS has a few entries for this sequence. – Jules May 18 '16 at 18:38
• I would like to reopen the question since my answer below could be a reference for similar questions (what is the next number in$\ldots$), often appearing here on MSE. For instance, it just happened: math.stackexchange.com/questions/1848089/unknown-formula – Jack D'Aurizio Jul 3 '16 at 21:43
• What distinguishes this Question from many of this ilk is the OP's statement of a recurrence relation. It is certainly a well founded problem to solve that recurrence relation (with the given initial conditions) for an explicit formula. – hardmath Jul 3 '16 at 23:34

This kind of problems is always ill-posed, since given any sequence $a_0,a_1,\ldots,a_n$ we are free to assume that $a_k=p(k)$ for some polynomial $p$ with degree $n$, then extrapolate $a_{n+1}=p(n+1)$ through Lagrange's approach or the backward/forward difference operator. A taste of the second approach:

$$\begin{array}{ccccccccc} 1 & & 5 & & 19 & & 65 & & 211\\ & 4 && 14 && 46 && 146\\ & & 10 && 32 && 100 && \\ &&& 22 && 68 &&&\\ &&&& 46\end{array}$$ by applying four times the difference operator, we reach a constant polynomial, hence we may re-construct $p(n+1)$ this way:

$$\begin{array}{cccccccccc} \color{green}{1} & & 5 & & 19 & & 65 & & 211&&\color{purple}{571}\\ & \color{green}{4} && 14 && 46 && 146&&\color{red}{360}\\ & & \color{green}{10} && 32 && 100 && \color{red}{214}& \\ &&& \color{green}{22} && 68 &&\color{red}{114}&&\\ &&&& \color{green}{46}&&\color{red}{46}&&&\end{array}$$ and $\color{purple}{571}$ is a perfectly reasonable candidate $a_{n+1}$, like $$a_n = 1-\frac{31 n}{6}+\frac{181 n^2}{12}-\frac{47 n^3}{6}+\frac{23 n^4}{12}=\color{green}{46}\binom{n}{4}+\color{green}{22}\binom{n}{3}+\color{green}{10}\binom{n}{2}+\color{green}{4}\binom{n}{1}+\color{green}{1}$$ is a perfectly reasonable expression for $a_n$.

The Berlekamp-Massey algorithm is designed for solving the same problem under a different assumption, namely that $\{a_n\}_{n\geq 0}$ is a linear recurring sequence with a characteristic polynomial with a known degree. In your case you already know the characteristic polynomial $x^2-5x+6=(x-2)(x-3)$, hence you just have to find the coefficients $A,B$ fulfilling $$a_n= A\cdot 2^n+B\cdot 3^n$$ and by considering that $a_0=1,a_1=5$ we get $\color{red}{a_n = 3^{n+1}-2^{n+1}}$.

• That's true for a certain value of the word "reasonable". :) Your point about these questions being ill-posed is well-taken, and yet there is so often consensus agreement on what is meant. – G Tony Jacobs May 18 '16 at 17:19
• Nice approach!!! – SiXUlm May 18 '16 at 17:25
• What if I say that a solution is "nicer" iff it's "shorter" than others? We can do better. Let's say that our "elementary functions" are polinomials and exponentials. A solution could be the nicest if it's the shortest. This might give solution he was waiting for. – Ivan Di Liberti May 18 '16 at 21:22

Are you simply looking for an explicit formula, or a way to derive it yourself? $$a_n = 3^n-2^n$$

You have $a_{n+1}=5a_n-6a_{n-1}$. This kind of recurrence tends to happen with exponential-type series. Thus, assume $a_n=r^n$, and plug in:

$a_{n+1}-5a_n+6a_{n-1}=0 \\ r^{n+1} - 5r^n+6r^{n-1}=0$

Divide through by $r^{n-1}$, and you get a quadratic in $r$:

$r^2-5r+6=0$

This is solved by $r=2$ and $r=3$, so you look for a sequence of the form:

$a_n=P\cdot 2^n + Q\cdot 3^n$ for some real coefficients $P$ and $Q$. You can find them by plugging in the first couple of terms in your series, thus producing a linear system in $P$ and $Q$.

In the answer given by @SiXUlm, we note another recurrence for this sequence:

$a_n = 3a_{n-1}+2^n$ for $n\geq2$, with $a_1=1$

You can also get the formula by solving this recurrence. We write it as:

$a_n - 3a_{n-1} = 2^n$

and then solve the related recurrence:

$a_n - 3a_{n-1} = 0$

Using the technique from above, we get $r=3$ and $a_n=P\cdot3^n$. Then, because of the $2^n$ that we were just ignoring, we throw in a $Q\cdot 2^n$ term to account for its effect. Thus, we get the same answer as above.

$5 = 1*3 + 2, 19 = 5*3 + 2^2, 65 = 19*3 +2^3, 211=65*3+2^4$, etc

If $a_0 = 1$, then $a_n = 3 \times a_{n-1} + 2^n$.

• How to derive this in general? – lab bhattacharjee May 18 '16 at 16:55
• I don't know. It depends very much on the problem. – SiXUlm May 18 '16 at 17:01
• That's an interesting recurrence @SiXUlm. How did you notice it? – G Tony Jacobs May 18 '16 at 17:07
• I noticed when I divide the one term by its successive, I obtain the result is bigger than $3$, but never $4$ (except the first term), so I checked the difference $a_{n+1} - 3a_n$ and saw the pattern $2,4,8,16$. – SiXUlm May 18 '16 at 17:13

This refers to @Jack d'Aurizio's second ansatz, just to make it explicite. It is a method which I use if I suspect that my sequence has a recursive structure.

Example in Pari/GP

v=[1,5,19,65,211]  \\ initialize a row-vector with values of the sequence

Now recursion means, that we have some transfer [1,5,19] -> [5,19,65] or [1,5,19] -> [19,65,211] by some transfermatrix T by [...] * T = [...]. To be able to find T by a matrix-inversion the brackets in [...] -> [...] should be (quadratic) matrices and not only vectors. So I construct a source-matrix Q and use the maximal possible dimension first:

Q=matrix(3,3,r,c,v[r-1+c])  \\ "source"-matrix with maximal dimension
\\ all entries of v are used
%291 =
[1 5 19]
[5 19 65]
[19 65 211]

First test, whether we really need dimension 3. If the matrix is singular, we only need a smaller dimension for the recursion:

matrank(Q)
%292 = 2

Well, the rank of the matrix is only 2, so we need to do everything with 2x2-matrices only:

Q=matrix(2,2,r,c,v[r-1+c])
%293 =
[1 5]
[5 19]

Now we define the target-matrix Z which should be a "rightshift" of Q by one column:

Z=matrix(2,2,r,c,v[1+r-1+c])
%294 =
[5 19]
[19 65]

From this we can compute the needed transfermatrix T to allow Q*T=Z

T = Q^-1 * Z
%295 =
[0 -6]
[1 5]

The transfermatrix contain the solution which is also known by the earlier answers: $a_{k+1} = -6 a_{k-1} + 5 a_k$ . Powers of $T$ should transfer more positions in $v$:

Q * T
%296 =
[5 19]
[19 65]

Q * T^2
%297 =
[19 65]
[65 211]

Q * T^3
%298 =
[65 211]
[211 665]

and so on ...
Of course this can simply be generalized to higher dimensions. And if in the problem the rank of the initial matrix had been 3 and no more entries in v had been given, we had been lost in the well known arbitrariness...

Remark: we could do even more. When we diagonalize the transfermatrix T then we can even find the "Binet-type" solutions with some exponential-formula, where the elements of the generalized sequence in v can be directly computed putting the index into the exponent of a monomial, and can thus often be generalized to fractional and even complex sequence-indexes . (As might be known from the Fibonacci-numbers and their Binet-formula - see wikipedia)

The sequence you have found is a generalization of the Fibonacci sequence.

There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas, and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)

We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n)$$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

The result is written in this form to underscore that it is the sum of a Fibonacci-type and Lucas-type Binet-like terms. It will also reduce to the standard Fibonacci and Lucas sequences for $a=b=1 \ \text{and} \ f_0=0, f_1=1$.

The analysis follows Maynard almost exactly and I can expand upon this or provide a brief manuscript. This analysis is valid for any $a,b,f_0,f_1\in\mathbb{R}$. Notice that only when $a=b=1$ does the ratio of successive terms approach the golden ratio $\Phi$ for large $n$. I haven't fully explored the limiting ratio for the general case, but I find for positive $a,b$ that the limiting ratio is given by $\alpha$.

After all is said and done, your sequence with $f_0=1, f_1=5, \alpha=3, \text{ and } \beta=2$, comes down to

$$f_n=\frac{5}{2}(3^n-2^n)+\frac{1}{2}(3^n+2^n)=3^{n+1}-2^{n+1},\ \ \ n=0,1,2,3...\\ \lim_{n\to \infty}\frac{f_{n+1}}{f_n}=3$$

which is essentially the same the result $(3^n-2^n)$ noted earlier on this page. However, now you have the tools to tackle many additional problems of this type.

Disclosure: This post is was derived largely from a previous answer of mine in Decimal Fibonacci Number?