While experimenting with Fibonacci numbers and Pascal's triangle, I found this: take any row of Pascal's triangle (say, $n = 7$): $$1, 7, 21, 35, 35, 21, 7, 1$$ and write under it the Fibonacci numbers, with $F_0=0$ going under the second number (of course, we assume $F_{-1} = F_1 - F_0 = 1$). Then, write a third row of $\pm1$'s: $$\begin{array}{ccc}1&7&21&35&35&21&7&1\\1&0&1&1&2&3&5&8\\1&-1&1&-1&1&-1&1&-1\\\end{array}$$ Multiply down the columns: $$\begin{array}{ccc}1&0&21&-35&70&-63&35&-8\\\end{array}$$ and now add the row to get $21$, which is the ($n+1$)th Fibonacci number! This seems to work for all $n$.

To prove this would be to prove the following Fibonacci recursion with binomial coefficients: $$F_{n+1} = \sum_{k=0}^n {\left(\left(-1\right)^k {n\choose k} F_{k-1}\right)}$$ I'm not sure how to continue from here; any hints? Thanks!

  • $\begingroup$ Induction would probably be the tool of choice here! $\endgroup$ – flawr Feb 13 '17 at 23:41
  • $\begingroup$ The easiest way to prove this is probably generating functions; you can take advantage of the fact that ${n\choose k}={n\choose n-k}$ to write this as $F_{n+1}=\sum_k a_kb_{n-k}$ for suitable terms $a_i$ and $b_i$; the sum on the right hand side is then just the product of the generating functions for the two sequences $a_n$ and $b_n$, so it's easy to compare and confirm the identity. There's also probably a super-slick combinatorial proof, but I'm not seeing it offhand... $\endgroup$ – Steven Stadnicki Feb 13 '17 at 23:41
  • $\begingroup$ The really cool thing about this is that you can use this representation to end up showing that any positive integer $n$ can be written of the form $\sum_{k=1}^{n}c_{n}F_{n}$ for some sequnce $c_n$ of binomial coefficients. $\endgroup$ – Plopperzz Feb 14 '17 at 0:02

Remember that $F_n = \frac{1}{\sqrt5}\left(\varphi^n - (-\varphi)^{-n}\right)$ and $\varphi - 1 = \frac{1}{\varphi}$. Now we can substitue it into your sum: $$\sum_{k = 0}^n \left((-1)^k \binom{n}{k}F_{k - 1}\right)\\ = \frac{1}{\sqrt5}\sum_{k = 0}^n \left((-1)^k \binom{n}{k} (\varphi^{k - 1} - (-\varphi)^{1 - k})\right)\\ = \frac{1}{\sqrt5}\left(\frac{1}{\varphi}(1 - \varphi)^n + \varphi\left(1 + \frac{1}{\varphi}\right)^n\right)\\ = \frac{1}{\sqrt5}\left(-(-\varphi)^{-n - 1} + \varphi^{n + 1}\right) \\ = F_{n + 1}.$$

  • $\begingroup$ There is something funny in this proof. Fibonacci number is a sum of "big" and "small" parts and the sum of "big" parts is "small" while the sum of "small" parts is "big". $\endgroup$ – Smylic Feb 14 '17 at 0:25
  • $\begingroup$ Minor nitpickery: you have a typo in the penultimate line; the $(-\varphi)^{n+1}$ term should have a negative exponent, not a positive one. $\endgroup$ – Steven Stadnicki Feb 14 '17 at 1:24
  • $\begingroup$ Yes, thank you! $\endgroup$ – Smylic Feb 14 '17 at 7:23

A dynamical systems approach: Let $\sigma$ denote the "right-shift" on the space of sequences $(x_n)_{n\in {\Bbb Z}}$, i.e.: $$ (\sigma x)_n = x_{n+1}, \ \ {n\in {\Bbb Z}} $$ Then the Fibonacci sequence, $(F_n)_{n\in {\Bbb Z}}$, verifies: $$ \sigma^2 F = \sigma F + F = (\sigma +1) F $$ or, equivalently, $$ \sigma^{-1}F = \sigma F - F = (\sigma -1) F $$ The first identity implies: $$ \sigma^{2n} F = (\sigma +1)^n F = \sum_{k=0}^n \binom{n}{k}\sigma^k F $$ and the second: $$ \sigma^{-n} F = (\sigma -1)^n F = \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}\sigma^k F = (-1)^{n+1} \sum_{k=0}^{n-1} (-1)^{k-1}\binom{n}{k}\sigma^k F $$ Evaluating the latter at the index $-1$, i.e.: $$ F_{-n-1}=(\sigma^{-n} F)_{-1} = (-1)^{n} \sum_{k=0}^n (-1)^{k}\binom{n}{k}\sigma^k F_{k-1} $$ we see that your identity really corresponds to evaluating $(-1)^{n} F_{-n-1}$ and not $F_{n+1}$. They just happen to be identical, due to the symmetry in the initial conditions that define $(F_n)_{n\in {\Bbb Z}}$ [The sequence $F_n + (-1)^n F_{-n}, \ {n\in {\Bbb Z}}$ is identically zero]


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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