How to find a closed formula for this Fibonacci-like recursive definition?

Question

I have a recursive definition which is similar to the Fibonacci-numbers:

$n_1 = 1$ (I)

$n_2 = 2$ (II)

$n_k = n_{k-2} + n_{k-1} + 1$ (III)

I am looking for a closed formula for it.

If that $+1$ weren't on the end of (III), everything would be very easily linearizable, because I could apply matrices and solve the problem in its own system of eigenvectors. This is how the closed formula of the Fibonacci-numbers is derived.

But now, with this $+1$, this solution doesn't work any more.

What to do?

Answer 1

You could try to use recurrence annihilators, or equivalently, the shift operator, as follows:

$$F(n)=F(n-2)+F(n-1)+1$$ $$F(n+2)−F(n+1)−F(n)=1$$

Let $\partial$ denote $\frac{d}{dn}$. Than $$e^{h\partial}F(n)=F(n+h)$$ which can be used to express the above as

$$(e^{2\partial}-e^\partial -1)F(n)=1$$ which can be factored $$(e^\partial-\frac{1-\sqrt{5}}{2})(e^\partial-\frac{1+\sqrt{5}}{2})F(n)=1$$ what is left to do, is to notice that $(e^\partial-1)$ annihilates a constant. This is why the first differences of the sequence you computed are the Fibonacci numbers($(e^\partial-1)$ is the first difference). As such $$(e^\partial-1)(e^\partial-\frac{1-\sqrt{5}}{2})(e^\partial-\frac{1+\sqrt{5}}{2})F(n)=0$$ which leads to a general solution

$$F(n)=c_0(\frac{1-\sqrt{5}}{2})^n+c_1(\frac{1+\sqrt{5}}{2})^n+c_2$$

The constants $c_i$ can be computed from initial conditions.

If you want to learn more about such computations, and proofs of the used theorems, you can read this post on Recurrence annihilators and Algebraic encodings. The post also contains a recurrence solver, that will show you these calculations, step by step.

Answer 2

For @LordSharkTheUnknown 's pretty comment, I computed the first few values of the sequence: $1, 2, 4, 7, 12, 20...$

Its difference sequence are the Fibonacci-numbers. The hypothesis can be easily proven by induction.

Since we have closed formula for the Fibonacci-numbers, which is

$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n- \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n $$

it is already easy to convert to a series with elemental identities.

Answer 3

Let $f_k = n_k + 1$, we have $$n_k = n_{k-1} + n_{k-2} + 1 \quad\implies\quad f_k = f_{k-1} + f_{k-2}$$ Compare this to the recurrence relation of Fibonacci numbers $$F_k = F_{k-1} + F_{k-2}$$ and notice $f_1 = 2 = F_3, f_2 = 3 = F_4$, we find $$f_k = F_{k+2} \quad\implies\quad n_k = F_{k+2} - 1$$

In general, if you have a homogeneous linear recurrence relation with constant coefficients

$$x_{n} + \sum_{k=1}^m a_k x_{n-k} = 0$$

whose characteristic polynomial $\chi(\lambda) = \lambda^m + \sum_{k=1}^m a_k \lambda^{m-k}$ doesn't vanish at $1$, the inhomogeneous recurrence relation with a polynomial $P(x)$ as source term: $$x_{n} + \sum_{k=1}^m a_k x_{n-k} = P(n)$$ will have a particular solution of polynomial in $n$ with same degree as $P(x)$.

In your case, $P(x) = 1$, so your recurrence relation will have a constant sequence as particular solution. You just need to figure out that constant and reduce your problem to that of Fibonacci sequences.