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.
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}}$.
Are you simply looking for an explicit formula, or a way to derive it yourself? $$a_n = 3^n-2^n$$
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?
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$.
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...
indexes . (As might be known from the Fibonacci-numbers and their Binet-formula - see wikipedia)
