5
$\begingroup$

In the Wikipedia page of the Fibonacci sequence, I found the following statement:

Like every sequence defined by a linear recurrence with linear coefficients, the Fibonacci numbers have a closed form solution.

The closed form expression of the Fibonacci sequence is:

enter image description here

Another example, from this question, is this recursive sequence:

enter image description here

which has the following closed form formula:

enter image description here

Yet another example from this question is this recursive sequence:

enter image description here

which has the following closed form formula:

enter image description here

So, my question is, how does one come up with these formulae?

Verifying whether a formula is correct or not is easy - that's not what I am asking. I want to know how to come up with a closed form formula for a given recursive sequence.

For example, say, I am interested in the following sequence:

$a_{n+1}$ = $a_n$ + (sum of the digits of $a_n$)

How do I come up with a closed form expression for the $n^{th}$ term of this sequence?

I guess the first step would be to confirm if this sequence is "defined by a linear recurrence with linear coefficients"; if yes, it must have a closed form formula.

$\endgroup$
10
  • $\begingroup$ You guess right. So, is your sequence defined by a linear recurrence with linear coefficients? $\endgroup$ – Ivan Neretin Feb 28 '20 at 9:16
  • $\begingroup$ @IvanNeretin I am not quite sure. It seems so; the first term on the right hand side is certainly linear. The second term, I am not sure if it can be expressed as a linear recurrence with linear coefficients. Besides, the statement is not commutative. So, I am not sure if a closed form can't be found for expressions that cannot be defined as a linear recurrence with linear coefficients. $\endgroup$ – Kristada673 Feb 28 '20 at 9:22
  • 1
    $\begingroup$ Your example $a_{n+1}=a_n+(\text{sum of the digits of }a_n)$ seems particularly difficult and requires very different techniques than the previous ones; it is not at all linear. Please confirm which case matters to you, to avoid wasted effort. $\endgroup$ – Yves Daoust Feb 28 '20 at 9:46
  • 1
    $\begingroup$ @YvesDaoust I am interested in that sequence only. While researching how to find closed forms, I came across the resources I mentioned in the question,. If they are not relevant, its ok, I am willing to take a different approach. $\endgroup$ – Kristada673 Feb 28 '20 at 9:51
  • 2
    $\begingroup$ @IvanNeretin: "there is no approach that will work" might be an overstatement. Chuck Norris must know. $\endgroup$ – Yves Daoust Feb 28 '20 at 9:55
5
$\begingroup$

Consider

$$a_{n+1}=a_n+(a_n\bmod 10)$$

which is a simplified version, where you only add the last digit.

By experimentation, except for the first term we have the expression

$$a_n=a_0+5n+\alpha_{a_0}+\beta_{n\bmod 4}$$ where $\alpha_{a_0}$ is a small integer and $\beta_{k}=(1,-3,-1,3)$.

For instance, $7$ yields the sequence of $\delta$'s

$$2,4,3,6,7,4,3,6,7,4,3,6,7,\cdots$$

There are two special cases: initial number ending in $0$ and in $5$.

The period $4$ is explained as follows: as you add to the number its last digit, this digit gets doubled. And the sequence of doublings modulo $10$ is either $0,0,0,\cdots$ or $2,4,8,6,2,4,8,6,\cdots$. Then the term $5n$ is simply explained by the fact that the average of a period is $5$.


Chances are high that handling the next digits will be pain in the neck, because of the carries.

$\endgroup$
2
  • 1
    $\begingroup$ This unexplained downvote is shocking. $\endgroup$ – Yves Daoust Feb 28 '20 at 10:21
  • 1
    $\begingroup$ Yes, somebody just downvoted my question as well as both the answers without any explanation. $\endgroup$ – Kristada673 Feb 28 '20 at 10:28
5
$\begingroup$

how does one come up with these formulae?

There is no generic rule that could cover all imaginable recurrences, however there are specific types of recurrences for which one can work out solutions.

One such case where a formula can be given is the linear case (like with Fibonacci numbers), that can be approached by linear algebra: Suppose the recurrence has the form

$$ x_n = a_1 x_{n-1} + a_2 x_{n-2} +\cdots +a_k x_{n-k} = \sum_{j=1}^k a_j x_{n-j} $$ for $n>k\geqslant 1$ where $x_1$, ..., $x_k$ are given numbers in some field $K$ and the $a_i$ are constants not depending on $n$. To get an explicit representation for $x_n$, write the recurrence as: $$ \underbrace{\left(\begin{array}{l} x_{n\;\;\;}\\ x_{n-1}\\ \;\;\vdots\\ x_{n-k+2}\\ x_{n-k+1}\\ \end{array}\right)}_{\displaystyle{=:y_n}} =\underbrace{\begin{pmatrix} a_1 & a_2 & \cdots & a_{k-1} & a_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots &&\ddots&&\vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{pmatrix}}_{\displaystyle{=:A\in K^{k\times k}}} \cdot \underbrace{\left(\begin{array}{l} x_{n-1}\\ x_{n-2}\\ \;\;\vdots\\ x_{n-k+1}\\ x_{n-k}\\ \end{array}\right)}_{\displaystyle{=:y_{n-1}}} $$ so that it takes the form $$ y_n = Ay_{n-1} = A^{n-k}y_k $$

Hence we'll are left with determining $n$-th powers of a square matrix $A$. Now suppose $A$ has $k$ different eigenvectors $v_j$ and we know all of them, including the corresponding eigenvalues $\lambda_j$. Then we can write: $$ y_k = \sum_{j=1}^k \beta_j v_j = V\begin{pmatrix} \beta_k\\ \vdots\\ \beta_1\end{pmatrix} = \begin{pmatrix}v_k&\cdots&v_1\end{pmatrix}\cdot\begin{pmatrix} \beta_k\\ \vdots\\ \beta_1\end{pmatrix} $$ where the $\beta_j$ are scalars in the algebraic closure of $K$ and $V$ is a matrix with the eigenvectors of $A$ as columns. Hence: $$ y_n = A^{n-k}y_k = A^{n-k}\Big(\sum_{j=1}^k \beta_j v_j\Big) = \sum_{j=1}^k \beta_j A^{n-k}v_j = \sum_{j=1}^k \beta_j \lambda_j^{n-k}v_j \qquad (1) $$ which leaves is with the computation of the $\beta_j$, the $v_j$ and the $\lambda_j$. Once we determined the eigenvectors, we get the $\beta_j$ by means of: $$ \begin{pmatrix} \beta_k\\ \vdots\\ \beta_1\end{pmatrix} = V^{-1}y_k $$ Expanding the determinant of $A-\lambda E$ by expanding after it's top row, we find that all eigenvalues satisfy the characteristic equation $$\lambda^k = \sum_{j=1}^k a_j\lambda^{k-j} = a_1\lambda^{k-1}+a_2\lambda^{k-2}+\cdots+a_{k-1}\lambda+a_k$$ From this we easily see that the eigenvectors of $A$ are: $$v_j = \left(\begin{array}{l} \lambda_j^{k-1} \\ \;\;\vdots\\ \lambda_j^2 \\ \lambda_j \\ 1 \\ \end{array}\right) $$ Due to (1), in order to get $x_n$ we take the top component of $y_n$ to get: $$ x_n = \sum_{j=1}^k \beta_j \lambda_j^{n-k}\lambda_j^{k-1} = \sum_{j=1}^k \beta_j \lambda_j^{n-1} \qquad (2) $$

Thus we are finished: Depending on the $a_j$, the eigenvalues can be computed explicitly or by numerical methods. From the eigenvalues we get the Vandermonde-like matrix $V$ which we use to compute the coefficients $\beta_j$ from the starting values $x_1$ ... $x_k$ so that we have determined all unknowns in (2).

2nd Order

This is the case $x_n = a_1x_{n-1}+a_2x_{n-2}$. The matrix $V$ composed of the eigenvectors is: $V=\begin{pmatrix} \lambda_2 & \lambda_1\\ 1&1\\ \end{pmatrix}$ with inverse $$ V^{-1} =\dfrac{1}{\lambda_2-\lambda_1}\begin{pmatrix} 1 & -\lambda_1\\ -1&\lambda_2\\ \end{pmatrix} $$ so that $$ \binom{\beta_2}{\beta_1}=\dfrac{1}{\lambda_2-\lambda_1}\binom{x_2-\lambda_1 x_1}{\lambda_2 x_1-x_2} $$ and we arrive at $$ x_{n+1}=\dfrac{(\lambda_2 x_1-x_2)\lambda_1^n + (x_2-\lambda_1 x_1)\lambda_2^n}{\lambda_2-\lambda_1} $$

In the case of Fibonacci numbers, we have $a_1 = a_2 = x_1 = x_2 = 1$. The characteristic equation is $\lambda^2 = \lambda + 1$ which has the Golden Ratio $\lambda_1=\varphi$ as solution as well as $\lambda_2=\psi=1-\varphi=-1/\varphi$. Plugging in:

$$\begin{align} x_{n+1} &=\dfrac{(\psi-1)\varphi^n + (1-\varphi)\psi^n}{\psi-\varphi} \\ &=\dfrac{-\varphi^{n+1} + \psi^{n+1}}{\psi-\varphi} \\ &=\dfrac{\varphi^{n+1} - \psi^{n+1}}{\varphi-\psi} \\ \end{align}$$

Coinciding Eigenvalues

An interesting / annoying case is when two or more eigenvalues are the same so that $V$ is not invertible, so that there is no straight forward way to determine the $\beta_i$. In that case we can still arrive at a solution if $K$ supports concepts like continuity. Take for example the 2-dimensional case from above over $\mathbb R$ or $\mathbb C$ with $\lambda=\lambda_1=\lambda_2$. We then write $\lambda_2=\lambda+\varepsilon$ and take $\lim_{\varepsilon\to0}$: $$\begin{align} x_{n+1} &=\lim_{\varepsilon\to0} \dfrac{(\lambda_2 x_1-x_2)\lambda_1^n + (x_2-\lambda_1 x_1)\lambda_2^n}{\lambda_2-\lambda_1}\\ &=\lim_{\varepsilon\to0} \dfrac{x_1 \lambda (\lambda+\varepsilon) (\lambda^{n-1}-(\lambda+\varepsilon)^{n-1}) + x_2 ((\lambda+\varepsilon)^n - \lambda^n)}{\varepsilon}\\ &= -(n-1)\lambda^n x_1 + n\lambda^{n-1} x_2\\ \end{align}$$

Example: Take $x_{n+2} = 2x_{n+1} - x_n$ with characteristic polynomial $\lambda^2=2\lambda-1$. This has a double root at $\lambda=1$. The explicit formula is hence $x_{n+1}=n x_2 - (n-1)x_1$.

$\endgroup$
4
  • $\begingroup$ Nice effort, but this is unrelated to the exact question (see comments). I am not the downvoter. $\endgroup$ – Yves Daoust Feb 28 '20 at 10:22
  • 1
    $\begingroup$ @YvesDaoust : The question is how one comes up with explicit formulae, insn't it? $\endgroup$ – emacs drives me nuts Feb 28 '20 at 12:03
  • $\begingroup$ Not really. You didn't read the comments. $\endgroup$ – Yves Daoust Feb 28 '20 at 12:23
  • 2
    $\begingroup$ I think it's a fair interpretation of the question as currently written that the question boils down to "how one comes up with explicit formulae". The more specific question Yves answers feels like afterthought, like yet another example. $\endgroup$ – PatrickT Feb 28 '20 at 17:57
1
$\begingroup$

For example, say, I am interested in the following sequence: $$a_{n+1} = a_n + (\text{sum of the digits of } a_n)$$ How do I come up with a closed form expression for the $n$th term of this sequence?

One could try to look at it modulo some integer number(s). This won't give an explicit formula, but can give hints, and it can be used to check a potential explicit candidate.

Let$\def\mod{\operatorname{mod}}$ $Q_b(m)$ denote the digit-sum of $m\in\mathbb N_0$ when $m$ is represented to basis $b$. Then $$Q_b(m) \equiv m \pmod{b-1}$$ This is simply because $b\equiv1\pmod{b-1}$ and the powers $b^k$ in the representation of $m$ will all be $1^k=1$. In the decimal case $b=10$ we have: $$\begin{align} a_{n+1} &= a_n + (\text{sum of the digits of } a_n) \\ &= a_n + Q_{10}(a_n) \\ &\equiv 2a_n \equiv 2^n a_0\pmod 9 \end{align}$$ For example, with $a_0=5$ we get the sequence 5, 10, 11, 13, 17, 25, 32, 37, ... which is mod 9: 5, 1, 2, 4, 8=17, 16=25, 32, 64=37=1, ...

The pattern will be periodic with period 6 because $2^{n\mod6}\equiv2^n\pmod 9$. To see the repetition in the example above, notice that 32=5 mod 9.

For example, $a_{100} \equiv 2^{100} a_0 \equiv 2^4a_0 \equiv 7a_0$, and indeed with $a_0=3$ we have: $a_{100}=1164 \equiv 3 \equiv 7\cdot 3 \pmod 9$.

And we get the following nice properties:

  • 3 divides $a_n$ $\quad\Leftrightarrow\quad$ 3 divides $a_0$.

  • 9 divides $a_n$ $\quad\Leftrightarrow\quad$ 9 divides $a_0$.

As there is nothing interesting to say about $a_0=0$, let $a_0 \geqslant1$. Then $Q\geqslant1$ and thus the sequence is strictly increasing. Together with the divisibility property from above we get at least linear growth:

  • $d$ divides $a_0$ $\quad\Rightarrow\quad$ $a_{n+1} -a_n \geqslant d$ for $d\in\{1, 3,9\} $.

Investigating growth will not lead to an explicit formula, but it can help to get a better understanding. So let's get an upper bound: Let $m$ be a $k$-digit number. We then have:

$$ Q_b(m) \leqslant k(b-1) <kb = (1+\lfloor\log_b m\rfloor)b \leqslant (1+\log_b m)b $$ so that the growth is at least linear, but not much more:

  • $a_n \in \mathcal{O} (n\log n)$
$\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.