45
$\begingroup$

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}$.

$\endgroup$
4
  • 2
    $\begingroup$ Perhaps this is also true with F replaced by G, where G is a Fibonacci recurrence but G_0 and G_1 are two arbitrary numbers, excluding 0,0. Gerhard "Can't Build E From Nothing" Paseman, 2017.04.12. $\endgroup$ Commented Apr 12, 2017 at 21:04
  • 11
    $\begingroup$ Can't you just do the sums using the Binet formula? $\endgroup$ Commented Apr 12, 2017 at 21:05
  • $\begingroup$ As I mentioned above, it would be nice to see alternative or novel proofs. $\endgroup$ Commented Apr 12, 2017 at 21:19
  • $\begingroup$ @GerhardPaseman I suspect your comment is true, and can be proved from the special cases $n=0,1$ of the OP's assertion by taking linear combinations. $\endgroup$ Commented Apr 13, 2017 at 17:07

5 Answers 5

79
$\begingroup$

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!}$$

$\endgroup$
3
  • 4
    $\begingroup$ OoOooO that is slick! $\endgroup$
    – user78249
    Commented Apr 12, 2017 at 22:21
  • 2
    $\begingroup$ This is cool, too. $\endgroup$ Commented Apr 12, 2017 at 22:38
  • 1
    $\begingroup$ It is not an answer, It's a Golden answer! $\endgroup$
    – Amin235
    Commented Apr 18, 2017 at 21:44
30
$\begingroup$

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$.

$\endgroup$
2
  • 1
    $\begingroup$ This is cool, indeed. $\endgroup$ Commented Apr 12, 2017 at 22:37
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 13, 2017 at 18:04
22
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, indeed. $\endgroup$ Commented May 25, 2022 at 14:17
6
$\begingroup$

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)$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Your method using $P$ seems to be essentially the Umbral Calculus. $\endgroup$
    – Somos
    Commented May 14, 2023 at 10:59

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