0
$\begingroup$

While I was reading a book, I found the identity \begin{align*} \sum_{k = 0}^{m} (-1)^{[(m - k)/2]}\mathscr{F}_{m}^{k} F_{n + k}^{m - 1} = 0 , \end{align*} where the $ [x] $ denotes the integer that is smaller than $x$, and the symbol $ \mathscr{F} $ is Fibonacci combination define as \begin{align*} \mathscr{F}_{n}^{k} = \frac{F_{n} F_{n - 1} \cdots F_{n - k + 1}}{F_{k} F_{k - 1} \cdots F_{1}} = \prod_{j = 1}^{k} \frac{F_{n - k + j}}{F_{j}} \end{align*} and $ \mathscr{F}_{n}^{0} = 1 $.

Of course it is wrong, we can let $ m = 1 $ to find it is wrong. Then I ask AI, it tells me the right identity is \begin{align*} \sum_{k = 0}^{m} (-1)^{k(k + 1)/2}\mathscr{F}_{m}^{k} F_{n + k}^{m - 1} = 0 \end{align*} and $ m $ is odd. Let us try to let $ m = 3 $, we have \begin{align*} F_{n}^{2} - 2F_{n + 1}^{2} - 2F_{n + 2}^{2} + F_{n + 3}^{2} = 0 \end{align*} It is right. And let $ m = 5 $, we have \begin{align*} F_{n}^{4} - 5F_{n + 1}^{4} - 15F_{n + 2}^{4} + 15F_{n + 3}^{4} + 5F_{n + 4}^{4} - F_{n + 5}^{4} = 0 \end{align*} I don't know does this is right, but if we let $ n = 0 $, it is right.

So, for any odd $ m $, does we have \begin{align*} \sum_{k = 0}^{m} (-1)^{k(k + 1)/2}\mathscr{F}_{m}^{k} F_{n + k}^{m - 1} = 0 \end{align*} I try to use mathematical induction to prove it, but it looks like difficult because the index of $ \mathscr{F} F $ is changed \begin{align*} \mathscr{F}_{2l - 1}^{k} F_{n + k}^{2l - 2} \to \mathscr{F}_{2l + 1}^{k} F_{n + k}^{2l} \end{align*} Can you help me? Thank you.

$\endgroup$
2
  • $\begingroup$ You get a correct identity, for all $m\ge 1$ and $n\in \mathbb Z$, by using the ceiling function instead of the floor function: $$\sum_{k = 0}^{m} (-1)^{\color{blue}{\lceil}(m - k)/2\color{blue}{\rceil}}\mathscr{F}_{m}^{k} F_{n + k}^{m - 1} = 0,$$where $\lceil x\rceil$ is the smallest integer which is at least $x$. This was problem $1.2.8$ - $30$ in The Art of Computer Programming vol. 1. There's a proof in the back of the book (and also in this answer of mine). $\endgroup$ Commented Jul 19 at 16:30
  • $\begingroup$ @MikeEarnest Thanks you. It looks like a insteresting book. $\endgroup$ Commented Jul 19 at 18:09

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.