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

Solution 1:

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

Solution 2:

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

Solution 3:

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.