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

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.

• $X_n=0$. That formula is so short I have to pad this to make it a legal comment... – David C. Ullrich Jul 8 '16 at 16:33
• No one of the first numbers should be positive – Taha Akbari Jul 8 '16 at 16:34
• What do you mean by "shorter"? Total number of characters for the closed-form? This sounds very fuzzy to me. – Clement C. Jul 8 '16 at 16:43
• @Clement C. Yes shortest number of charters – Taha Akbari Jul 8 '16 at 16:50

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.

• But $\phi$ is not a natural number.I mean that all of them be a natural number but thanks for your formula it may be helpful – Taha Akbari Jul 8 '16 at 17:00
• @Pjotr5.I commented upper that one of $X_0$ or $X_1$ should be positive. – Taha Akbari Jul 8 '16 at 17:04
• Ah okay, then I don't think you can go much shorter than $x_0=2$ and $x_1=1$ yielding $$x_n= \phi^n + (-\phi)^{-n}.$$ – Pjotr5 Jul 8 '16 at 17:25
• Ok then you say the shortest is the Lucas numbers? – Taha Akbari Jul 8 '16 at 17:29
• Yes, in some sense! See edit. – Pjotr5 Jul 8 '16 at 17:35