6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Recurrence_relation#Solving $\endgroup$ – lab bhattacharjee May 18 '16 at 16:53
  • 1
    $\begingroup$ Here is one (out of infinitely many). $\endgroup$ – barak manos May 18 '16 at 17:01
  • 6
    $\begingroup$ OEIS has a few entries for this sequence. $\endgroup$ – Jules May 18 '16 at 18:38
  • 1
    $\begingroup$ 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 $\endgroup$ – Jack D'Aurizio Jul 3 '16 at 21:43
  • 2
    $\begingroup$ 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. $\endgroup$ – hardmath Jul 3 '16 at 23:34
34
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – G Tony Jacobs May 18 '16 at 17:19
  • 2
    $\begingroup$ Nice approach!!! $\endgroup$ – SiXUlm May 18 '16 at 17:25
  • $\begingroup$ 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. $\endgroup$ – Ivan Di Liberti May 18 '16 at 21:22
13
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How to derive this in general? $\endgroup$ – lab bhattacharjee May 18 '16 at 16:55
  • $\begingroup$ I don't know. It depends very much on the problem. $\endgroup$ – SiXUlm May 18 '16 at 17:01
  • $\begingroup$ That's an interesting recurrence @SiXUlm. How did you notice it? $\endgroup$ – G Tony Jacobs May 18 '16 at 17:07
  • 1
    $\begingroup$ 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$. $\endgroup$ – SiXUlm May 18 '16 at 17:13
1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.