Relation between series and equations

Question

There is following quotes from wiki on Plastic number:

The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$.

And 2nd is that

Plastic number is the unique real solution of equation $x^3=x+1$

This last cubic equation and recurrence relation looks very similar if you assume that n represent 3rd power of x, correspondingly n-2 would represent x itself and n-3 would represent 1.

But what is mathematical justification to associate the sequence and equation?

I remember we did this trick in college to find formula for Nth Fibbonachi numbers (which is $A(n) = A(n − 1) + A(n − 2)$ and correspondingly $x^2=x+1$) but it was too long ago..

Answer 1

The formula $$\rho^n=A(n-2)+A(n-3)$$ is wrong, as a little computation shows.

But the correct expression to get the sequence in A000931 is by taking the three roots of $x^3-x-1=0$.

If $r,s,t$ are those (with $r$ the real one) then the correction is $$A(n)=\frac{r^n}{2 r+3}+\frac{s^n}{2 s+3}+\frac{t^n}{2 t+3}.\qquad (1)$$ Obviously the entry in wikipedia gotta be corrected.

I still don't know how to deduce $(1)$ which is present in the aforementioned OEIS' entry, credited to Keith Schneider.

Answer 2

The mathematical justification is the standard association of a linear recurrence with its associated polynomial.

If the recurrence is $\sum\limits_{k=0}^m c_k a_{n-k} = 0 $ (with $c_0 \ne 0$), if we assume that $a_n = r^n$ with $r \ne 0$, we get $0 =\sum\limits_{k=0}^m c_k r^{n-k} =r^n\sum\limits_{k=0}^m c_k r^{-k} $, so that $1/r$ is a root of $C(x) =\sum\limits_{k=0}^m c_k x^{k} $.

The initial conditions for the $a_i$ then determine which linear combination of the roots of $C(x)$ give the formula for the $a_n$.

There are more complications if $C(x)$ has repeated roots, but this is why the recurrence leads to a polynomial.

Another nice result of using the polynomial is that the largest (or maybe smallest) root determines the asymptotic growth of the recurrence.

Look for generatingfunctionology and download the book. It's free and extremely useful.

Answer 3

This is uneccessarily complex and arcane. THE defining property of the plastic number is that it is a morphic number and satisfies the relations $p-1=p^{-4}$ and $p+1=p^3$. It the follows that $p^n=p^{n-1}+p^{n-5}$ and $p^n=p^{n+2}-p^{n-1}$. That's all there is to it.