0
$\begingroup$

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.

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

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ – Taha Akbari Jul 8 '16 at 17:00
  • $\begingroup$ @Pjotr5.I commented upper that one of $X_0$ or $X_1$ should be positive. $\endgroup$ – Taha Akbari Jul 8 '16 at 17:04
  • $\begingroup$ 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}.$$ $\endgroup$ – Pjotr5 Jul 8 '16 at 17:25
  • $\begingroup$ Ok then you say the shortest is the Lucas numbers? $\endgroup$ – Taha Akbari Jul 8 '16 at 17:29
  • $\begingroup$ Yes, in some sense! See edit. $\endgroup$ – Pjotr5 Jul 8 '16 at 17:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.