45

The Fibonacci recurrence $F_n=F_{n-1}+F_{n-2}$ allows values for all indices $n\in\mathbb{Z}$. There is an almost endless list of properties of these numbers in all sorts of ways. The below question might even be known. Yet, if true, I like to ask for alternative proofs.

Question. Does the following identity hold? We have $$\frac{\sum_{k=0}^{\infty}\frac{F_{n+k}}{k!}}{\sum_{k=0}^{\infty}\frac{F_{n-k}}{k!}}=e,$$ independent of $n\in\mathbb{Z}$.

T. Amdeberhan
  • 41,802

5 Answers5

79

It follows from the identity

$$F_{n+k} = \sum_{j=0}^k {k \choose j} F_{n-j}$$

which is obtained by applying the standard recurrence $k$ times to the left side, each time splitting up each term into two terms.

Indeed, this gives

$$\sum_{k=0}^{\infty} \frac{F_{n+k}}{k!} = \sum_{k=0}^{\infty} \frac{ \sum_{j=0}^k {k \choose j} F_{n-j}}{k!}= \sum_{k=0}^{\infty} \sum_{j=0}^{k} \frac{1}{j! (k-j)!} F_{n-j} = \sum_{j=0}^{\infty} \sum_{k-j=0}^{\infty} \frac{1}{(k-j)!} \frac{F_{n-j}}{j!} = \sum_{j=0}^{\infty} e \frac{F_{n-j}}{j!}$$

Will Sawin
  • 135,926
30

Mathematica tells me it's a consequence of the two series (distinguished by $\pm$): $$\sum_{k=0}^\infty\frac{F_{n\pm k}}{k!}=\frac{e^{\sqrt{5}} \phi^n-(1-\phi)^n}{\sqrt{5}\, \exp(\phi^{\mp 1})},$$ with $\phi$ the golden ratio (the positive solution of $1+1/\phi=\phi$). So the ratio of the $\pm$ series equals $e^{\phi-1/\phi}=e$, and the entire $n$-dependence drops out of the ratio.

The identity also holds for $n\in\mathbb{R}$, with the usual generalisation $F_z=(\phi^z-\phi^{-z}\cos\pi z)/\sqrt{5}$ of the Fibonacci numbers to real argument $z$.

Carlo Beenakker
  • 177,695
  • 1
    This is cool, indeed. – T. Amdeberhan Apr 12 '17 at 22:37
  • 1
    As I suspected (and Greg Martin commented), this extends to general nontrivial Fibonacci recurrences with $G_0=a$ and $G_1=b$. Writing the RHS above as $f(n)$, the corresponding value using $G$ is $af(-1) + bf(0)$ for the positive version, and similarly for the negative. Again cancellation occurs leaving a power of $e$. Gerhard "Or Use General Linear Nonsense" Paseman, 2017.04.13. – Gerhard Paseman Apr 13 '17 at 18:04
22

More generally, $$\sum_{k=0}^\infty F_{n+k} \frac{x^k}{k!} = e^x\sum_{k=0}^\infty F_{n-k}\frac{x^k}{k!},\tag{1}$$ which is equivalent to Will Sawin's identity.

Similarly, $$e^x\sum_{k=0}^\infty F_{n+k}\frac{x^k}{k!}= \sum_{k=0}^\infty F_{n+2k}\frac{x^k}{k!},\tag{2}$$ and more generally, from the formula $$(-1)^q F_{p-q}+F_{\!q}\,\phi^p = F_{\!p}\,\phi^q,$$ where $\phi = (1+\sqrt5)/2$, and the analogous formula with $\phi$ replaced by $(1-\sqrt5)/2$, we get for any integers $p$, $q$, and $n$, $$ e^{(-1)^q F_{p-q}\ x}\sum_{k=0}^\infty F_{q}^k F_{n+pk}\frac{x^k}{k!} = \sum_{k=0}^\infty F_p^k F_{n+qk} \frac{x^k}{k!}. $$ The cases $p=1, q=-1$ and $p=1,q=2$ give $(1)$ and $(2)$.

Related identities (also involving Lucas numbers) can be found in L. Carlitz and H. H. Ferns, Some Fibonacci and Lucas Identities, Fibonacci Quarterly 8 (1970), 61–73.

Ira Gessel
  • 16,246
6

The identity given is simpler than it seems. Suppose that $z$ is any nonzero complex number. Then

$$ \sum_{k=0}^\infty \frac{z^{n+k}}{k!} = z^n \sum_{k=0}^\infty \frac{z^k}{k!} = e^z z^n, \quad \sum_{k=0}^\infty \frac{z^{n-k}}{k!} = z^n \sum_{k=0}^\infty \frac{z^{-k}}{k!} = e^{1/z} z^n. \tag1 $$

Now, if $\,a_n := u\,\alpha^n + v\,\beta ^n\,$ for any nonzero $\,\alpha,\beta\,$ then

$$ \sum_{k=0}^\infty \frac{a_{n+k}}{k!} = u\, e^\alpha \alpha^n + v\, e^\beta \beta^n, \quad \sum_{k=0}^\infty \frac{a_{n-k}}{k!} = u\, e^{1/\alpha} \alpha^n + v\, e^{1/\beta} \beta^n. \tag2 $$

Divide the two summations to get

$$ \frac{ \sum_{k=0}^\infty \frac{a_{n+k}}{k!} } { \sum_{k=0}^\infty \frac{a_{n-k}}{k!} } = \frac{ u\, e^\alpha \alpha^n + v\, e^\beta \beta^n } { u\, e^{1/\alpha} \alpha^n + v\, e^{1/\beta} \beta^n}. \tag3 $$

For the Fibonacci sequence, $\,\alpha-\frac1\alpha = \beta -\frac1\beta = 1.$ The right side thus simplifies to $\,e^1 = e.$

In general, if $\,\alpha\beta=-1,\,$ then $\, \gamma := \alpha-\frac1\alpha = \beta -\frac1\beta,\,$ and the right side simplifies to $\,e^\gamma.$


There is an equivalent approach to a proof. Let $\,z\,$ be either $\,\alpha\,$ or $\,\beta.\,$ Then $\, z = \gamma + 1/z\,$ and

$$ z^{n+k} = z^n(\gamma+1/z)^k = \sum_{j=0}^k {k\choose j} \gamma^{k-j}z^{n-j}. \tag4 $$

Appy this to the sequence $\,a_n\,$ to get

$$ a_{n+k} = \sum_{j=0}^k {k\choose j} \gamma^{k-j} a_{n-j}. \tag5 $$

Now sum to get

$$ \sum_{k=0}^{\infty} \frac{a_{n+k}}{k!} = \sum_{k=0}^{\infty} \frac{ \sum_{j=0}^k {k \choose j} \gamma^{k-j} a_{n-j}}{k!} = \sum_{k=0}^{\infty}\sum_{j=0}^{k}\frac{\gamma^{k-j}}{j!(k-j)!} a_{n-j}\\ = \sum_{j=0}^{\infty} \sum_{k-j=0}^{\infty} \frac{\gamma^{k-j}}{(k-j)!} \frac{a_{n-j}}{j!} = \sum_{j=0}^{\infty} e^\gamma \frac{a_{n-j}}{j!} = e^\gamma \sum_{j=0}^{\infty} \frac{a_{n-j}}{j!}. \tag6 $$

This is another proof of the general result of equation $(3)$.

Somos
  • 2,464
5

I set out intending to post this as a comment, but perhaps it sits better here. The method that follows suggests a general formula to produce such relationships from second order linear recurrences. Modulo issues of convergence, it's more or less elementary. Some text is required to set up the machinery, but the substance of the argument is really just a few lines.


Context

Let $\Lambda$ be the complex vector space of functions $f\colon \mathbb{Z}\to \mathbb{C}$ for which there exists a constant $K_{f}\in\mathbb{R}_{\geq 1}$ such that $$\lim_{n^{-1}\to 0}\left(\frac{f\left(n\right)}{K_{f}^{\left|n\right|}}\right)\ =\ 0.$$ (The addition of $\Lambda$ and $\mathbb{C}$-action on $\Lambda$ are computed pointwise.) Now let $$S\ \colon\ \Lambda \to \Lambda,\ \ Sf\left(n\right)\ :=\ f\left(n+1\right)$$ be the ($\mathbb{C}$-linear) shift operator. Define $S^{-1}$ analogously, it being the (unique) inverse of $S$. For any polynomial $P\in\mathbb{C}\left[S,S^{-1}\right]$, we have a well-defined $\mathbb{C}$-linear map $$P\ \colon\ \Lambda\to\Lambda$$ (perhaps implicitly using that $S$ and $S^{-1}$ commute; the multiplicative structure of the ring corresponds to the composition of operators so that in particular $1\in \mathbb{C}\left[S,S^{-1}\right]$ is identified with the identity). For such $P$, we consider in turn the $\mathbb{C}$-linear map $$e^{P}\ :=\ \sum_{d\in\mathbb{N}} \frac{P^{d}}{d!}\ \colon\ \Lambda \to \Lambda.$$ The well-definition of $e^{P}$ consists of its pointwise absolute convergence and its taking functions in $\Lambda$ to functions in $\Lambda$; both follow from standard arguments$^{\text{1}}$. Also by a standard argument$^{\text{2}}$, $P_{0}$ commutes not only with $P_{1}$ but moreover with $e^{P_{1}}$ for any $P_{0},P_{1}\in \mathbb{C}\left[S,S^{-1}\right]$. By yet another standard argument$^{\text{3}}$, $$e^{P_{0}}e^{P_{1}}\ =\ e^{P_{0}+P_{1}}\ =\ e^{P_{1}}e^{P_{0}}.$$ Finally, it's clear that $e^{1}$ is the operator that scales inputs by $e$ and that if for some $f\in\Lambda$ and $P\in \mathbb{C}\left[S,S^{-1}\right]$ we have that $Pf = 0$, then $\left(e^{P}-1\right)f\ =\ 0$.


The argument

Now fix $f$ the Fibonacci sequence; this is in $Λ$ as by an elementary induction we have that $\left|f\left(n\right)\right|\leq 2^{\left|n\right|}$. The defining linear recurrence of $f$ is that $$\left(S-S^{-1}-1\right)f\ =\ 0.$$ From this it follows that for each $n\in\mathbb{Z}$, \begin{align*}\sum_{d\in\mathbb{N}}\frac{f\left(n+d\right)}{d!}\ :&=\ e^{S}f\left(n\right)\\ &=\ e^{S^{-1}+1}e^{S-S^{-1}-1}f\left(n\right)\\ &=\ e^{S^{-1}+1}f\left(n\right)\\ &=\ e^{1} e^{S^{-1}}f\left(n\right)\\ :&=\ e\sum_{d\in\mathbb{N}}\frac{f\left(n-d\right)}{d!},\end{align*} and modulo the question of the vanishing of the denominator in the expression in the OP (which is contingent on not only the recurrence, but also the specific initial conditions of the sequence), this is precisely what was to be demonstrated. $\blacksquare$


Notes

All instances of "convergence" in reference sums in what follows refer specifically to absolute convergence pointwise in $n$.

  1. For any $f\in \Lambda$ with $K_{f}\in\mathbb{R}_{\geq 1}$ such that $\lim_{n^{-1}\to 0}\left(f\left(n\right)K_{f}^{-\left|n\right|}\right)\ =\ 0$ and any $P\in \mathbb{C}\left[S,S^{-1}\right]$ whose terms have sum of norms of coefficients $L\in\mathbb{R}_{\geq 0}$ and maximum absolute degree $h\in\mathbb{N}$, there must (by the limit hypothesis) for every $\varepsilon > 0$ exist an $M_{\varepsilon}\in\mathbb{R}_{\geq 0}$ such that $\left|f\left(n\right)\right|\leq \max\left(M_{\varepsilon},\varepsilon K_{f}^{\left|n\right|}\right)$. It's then not hard to see (by expanding $P^{d}$) that $$\left|\frac{P^{d}}{d!}f\left(n\right)\right|\ \leq\ M_{\varepsilon}\frac{L^{d}}{d!}+\varepsilon\frac{\left(LK_{f}^{h}\right)^{d}}{d!}K_{f}^{\left|n\right|}$$ and thus that $$\left|e^{P}f\left(n\right)\right|\ \leq\ M_{\varepsilon}e^{L}+\varepsilon e^{LK_{f}^{h}}K_{f}^{\left|n\right|}$$ (so that the sum on the left necessarily converges). As the choice of $\varepsilon$ was arbitrary, it follows that $$\lim_{n^{-1}\to 0}\left(\frac{e^{P}f\left(n\right)}{K_{f}^{\left|n\right|}}\right)\ =\ 0,$$ completing the argument for both claims.

  2. As $P_{0}$ plainly commutes with the partial sums that converge to $e^{P_{1}}$, it must commute with $e^{P_{1}}$ itself.

  3. Expand the sums on the left and right as is justified by convergence and then use commutativity to collect and rearrange the terms to obtain the sum of binomial expansions implied by the middle.

Rafi
  • 233