2
$\begingroup$
  • Let $F_n$ be A000045 (i.e., Fibonacci numbers). Here

$$ F_n = F_{n-1} + F_{n-2}, \\ F_0 = 0, F_1 = 1, \\ F_{-n} = (-1)^{n-1}F_n $$

I conjecture that

$$ F_{-n} = \left\lfloor\frac{n+1}{2}\right\rfloor - \sum\limits_{i=1}^{n-1} \left(\left\lfloor\frac{n-i+1}{2}\right\rfloor + 1\right)F_{-i}, \\ F_{-n} = \left\lfloor\frac{2(n+1)}{3}\right\rfloor - \sum\limits_{i=1}^{n-1} \left(2\left\lfloor\frac{n-i+2}{3}\right\rfloor + 1\right)F_{-i} $$

Here is the PARI/GP program to check it numerically:

test1(n) = fibonacci(-n) == ((n+1)\2 - sum(i=1, n-1, ((n - i + 1)\2 + 1)*fibonacci(-i)))
test2(n) = fibonacci(-n) == (2*(n+1)\3 - sum(i=1, n-1, (2*((n - i + 2)\3) + 1)*fibonacci(-i)))

Is there a way to prove it? Is there any other similar formulas?

$\endgroup$

2 Answers 2

4
$\begingroup$

We have $$F_{-n}=\frac{(-a_-)^n-(-a_+)^n}{\sqrt5} \tag{1}\label{1}$$ with $$a_\pm:=\frac{1\pm\sqrt5}2.$$

We also have the easy formula for $\sum_{j=j_1}^{j_2}(p+qj)x^j$, which yields
$$\sum_{i=1}^{n-1} \left(\left\lfloor\frac{n-i+1}{2}\right\rfloor + 1\right)u^i \\ =-\frac{(u-1) u^2 \left\lfloor \frac{n+1}{2}\right\rfloor +(u-1) u \left\lfloor \frac{n}{2}\right\rfloor -2 u^{n+2}+u^n+u^3+u^2-u}{(u-1)^2 (u+1)}. \tag{2}\label{2}$$

Your first identity easily follows from \eqref{1} and \eqref{2}.

Other such identities should be derivable quite similarly.

$\endgroup$
3
$\begingroup$

As a complement to Iosif's answer, I'll give the inductive proof. First, some preliminaries: note that by recursively applying the defining relations, $$ F_n=F_{n-1}+F_{n-3}+...+F_2+1=1-(F_{-(n-1)}+F_{-(n-3)}+...+F_{-2}),\text{ when }n\text{ is odd,} $$ and $$ F_n=F_{n-1}+F_{n-3}+...+F_1=F_{-(n-1)}+F_{-(n-3)}+...+F_{-1},\text{ when }n\text{ is even.} $$ Therefore, $$ F_{-1}+F_{-2}+...+F_{-(n-1)}=1+(-1)^{n-1}F_{n-1}+(-1)^{n}F_{n} \\ =1-F_{-(n-1)}-F_{-n}. \tag{1}\label{eq:1} $$

Now, we start the inductive proof of your first statement. Clearly it holds for $n=1,2$.

Suppose that $n>2$ is odd. By equation \eqref{eq:1} and the inductive hypothesis, we obtain \begin{eqnarray*} F_{-n} &=& F_{-(n-2)} + \left(1-2F_{-(n-1)}-2F_{-(n-2)}-\sum_{i=1}^{n-3}F_{-i}\right)\\ &=&\left(\left\lfloor \frac{n-1}{2} \right\rfloor - \sum_{i=1}^{n-3}\left( \left\lfloor \frac{n-i-1}{2}\right\rfloor +1 \right)F_{-i}\right) + ... \\ &&\text{ ...} +\left(1-2F_{-(n-1)}-2F_{-(n-2)}-\sum_{i=1}^{n-3}F_{-i}\right) \\ &=&\left\lfloor \frac{n+1}{2} \right\rfloor - \sum_{i=1}^{n-1}\left( \left\lfloor \frac{n-i+1}{2}\right\rfloor +1 \right)F_{-i} \end{eqnarray*} as required. The cases of $n$ even, and the second of your formulae, are similar.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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