A sequence like fibonacci sequance that has got the shortest formula. [closed]

Question

I want a squance like this:

$X_1=a$,$X_2=b$,$X_n=X_{n-2}+X_{n-1}$

But I want one that has the shortest formula for example I found the lucas numbers formula.it was shorter than the fibonacci numbers formula but I want one with a shorter one.

Answer 1

Well, the general formula for the recurrence relation $x_n=x_{n-1}+x_{n-2}$ is $$ x_n= \frac{\phi ^n (x_0+ x_1 \phi )+\phi (-\phi )^{-n} (x_0 \phi -x_1)}{\phi ^2+1}, $$ where $\phi$ is either of the roots of $x^2-x-1$. You can make this formula really short by taking $x_0= 1$ and $x_1=\phi$. You get $$ x_n=\phi^n. $$ You can prove this directly without considering the giant unwieldy general formula. To do this keep in mind that $\phi^2=\phi+1$ such that $$\phi^n=\phi^2\phi^{n-2}=(\phi+1)(\phi^{n-2})=\phi^{n-1}+\phi^{n-2}.$$

---

Shorter still of course is taking $x_0=x_1=0$ such that $x_n=0$.

---

Edit: Now that I see that you want $x_0,x_1\in \mathbb{Z}_{> 0}$, I think that the best answer has got to be $x_0=2$ and $x_1=1$ yielding $$x_n= \phi^n + (-\phi)^{-n}.$$ The formula will always look like $$x_n =a \cdot \phi^n + b \cdot (-\phi)^{-n}.$$ Since you don't want $x_n=0$ we must have at least one of $a,b$ to be non-zero. If say $b=0$ we get $x_0=a$ and $x_1= a\cdot\phi$. Then $x_0$ and $x_1$ can't both be integers. So $b\neq 0$, by the same argument $a \neq 0$. I guess you could call $a=b=1$ the simplest form.