Skip to page content Home     Posts     CV     Contact     People

Reciprocal-Fibonacci Series

2018 Jan 30

Evaluate the following infinite series, where $F_n$ is the nth fibonacci number with $F_1=F_2=1$: $$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_k F_{k+5}}=\space\space\space ?$$ $$\sum_{k=1}^\infty \frac{1}{F_k F_{k+6}}=\space\space\space ?$$ $$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_{5k-1}F_{5k+4}}=\space\space\space ?$$ $$\sum_{k=1}^\infty \frac{1}{F_{10k}F_{10k+10}}=\space\space\space ?$$

To evaluate these series, consider the functions $\Phi_n(x)$ defined as $$\Phi_n(x):=\sum_{k=1}^\infty \frac{x^{k+1}}{F_k F_{k+n}}$$ where $F_k$ are the Fibonacci numbers, with $F_1=F_2=1$. In this post, I shall endeavour to evaluate a few particular value of $\Phi_n(x)$, establish a few of its functional equations to make computation easier, and use the functional equations to evaluate related sums.

First, recall the following well-known identities: $$F_{k+n}=F_k F_{n-1}+F_{k+1}F_n$$ $$F_k^2-F_{k+1}F_{k-1}=(-1)^{k+1}$$ which I will use frequently throughout the post.

I shall begin by computing $\Phi_1(-1)$ and $\Phi_2(1)$, which are both straightforward telescoping sums: $$\begin{align} \Phi_1(-1) &= \sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_k F_{k+1}}\\ &= 1+\sum_{k=2}^\infty \frac{F_k^2-F_{k+1}F_{k-1}}{F_k F_{k+1}}\\ &= 1-\sum_{k=2}^\infty \frac{F_{k-1}}{F_{k}}-\frac{F_k}{F_{k+1}}\\ &= 1-1+\lim_{k\to\infty} \frac{F_k}{F_{k+1}}\\ &= \phi^{-1}\\ \end{align}$$ Where $\phi$ is the golden ratio $\frac{1+\sqrt 5}{2}$. Next, we have $$\begin{align} \Phi_2(1) &= \sum_{k=1}^\infty \frac{1}{F_k F_{k+2}}\\ &= \sum_{k=1}^\infty \frac{1}{F_k F_{k+1}}-\frac{1}{F_{k+1}F_{k+2}}\\ &= 1+\lim_{k\to\infty} \frac{1}{F_{k+1}F_{k+2}}\\ &= 1\\ \end{align}$$

Now I will establish a recurrence relation that allows one to compute additional values of $\Phi_n(x)$ using the two previously computed as initial conditions.

Theorem 1: $$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}-\frac{F_{n-1}}{F_n}\frac{\Phi_{n-1}(x)}{x}+\frac{F_{n-1}x}{F_n^2}$$

Proof:

$$\begin{align} \Phi_n(x) &=\sum_{k=1}^\infty \frac{x^{k+1}}{F_k F_{k+n}}\\ &=\sum_{k=1}^\infty \frac{x^{k+1}}{F_k (F_k F_{n-1}+F_{k+1}F_n)}\\ &=\sum_{k=1}^\infty \frac{x^{k+1}}{F_{k+1}F_n}\bigg(\frac{1}{F_k}-\frac{F_{n-1}}{F_{k+n}}\bigg)\\ &=\frac{\Phi_1(x)}{F_n}-\frac{F_{n-1}}{F_n}\sum_{k=1}^\infty \frac{x^{k+1}}{F_{k+1}F_{k+n}}\\ &=\frac{\Phi_1(x)}{F_n}+\frac{F_{n-1}}{F_n}\bigg(\frac{x}{F_n}-\sum_{k=1}^\infty \frac{x^{k}}{F_{k}F_{k+n-1}}\bigg)\\ &=\frac{\Phi_1(x)}{F_n}+\frac{F_{n-1}}{F_n}\bigg(\frac{x}{F_n}-\frac{\Phi_{n-1}(x)}{x}\bigg)\\ &= \frac{\Phi_1(x)}{F_n}-\frac{F_{n-1}}{F_n}\frac{\Phi_{n-1}(x)}{x}+\frac{F_{n-1}x}{F_n^2}\space\space\space\space\space\space\blacksquare\\ \end{align}$$

Through this formula, one may recursively calculate many values of $\Phi_n(1)$ and $\Phi_{n}(-1)$. For example, using $\Phi_1(-1)=\phi^{-1}$ as previously calculated, $$\begin{align} \Phi_2(-1) &=\frac{\Phi_1(-1)}{F_2}-\frac{F_1}{F_2}\frac{\Phi_1(-1)}{-1}+\frac{F_1 (-1)}{F_2^2}\\ &=2\Phi_1(-1)-1\\ &=2\phi^{-1}-1\\ \end{align}$$

and

$$\begin{align} \Phi_3(-1) &=\frac{\Phi_1(-1)}{F_3}-\frac{F_2}{F_3}\frac{\Phi_2(-1)}{-1}+\frac{F_2 (-1)}{F_3^2}\\ &=\frac{\phi^{-1}}{2}+\frac{2\phi^{-1}-1}{2}-\frac{1}{4}\\ &=\frac{3\phi^{-1}}{2}-\frac{3}{4}\\ \end{align}$$

In fact, one may solve the recurrence relation to obtain the following:

Theorem 2: $$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}\sum_{k=0}^{n-1} (-x)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-x)^{1-k}F_{n-k-1}}{F_{n-k}},\space\space\space n\ge 1$$

Proof: The base case of this formula - with $n=1$ - holds trivially, so I will now begin the induction step.

Suppose that $$\Phi_m(x)=\frac{\Phi_1(x)}{F_m}\sum_{k=0}^{m-1} (-x)^{-k}-\frac{1}{F_m}\sum_{k=0}^{m-1}\frac{(-x)^{1-k}F_{m-k-1}}{F_{m-k}}$$ is true for some $m$. Then it follows that $$-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)=-\frac{\Phi_1(x)}{F_{m+1}x}\sum_{k=0}^{m-1} (-x)^{-k}+\frac{1}{F_{m+1} x}\sum_{k=0}^{m-1}\frac{(-x)^{1-k}F_{m-k-1}}{F_{m-k}}$$ $$-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=1}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m-1}\frac{(-x)^{-k}F_{m-k-1}}{F_{m-k}}$$ $$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m-1}\frac{(-x)^{-k}F_{m-k-1}}{F_{m-k}}$$ $$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)+\frac{F_m x}{F_{m+1}^2}=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m-1}\frac{(-x)^{-k}F_{m-k-1}}{F_{m-k}}+\frac{F_m x}{F_{m+1}^2}$$ $$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)+\frac{F_m x}{F_{m+1}^2}=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=1}^{m}\frac{(-x)^{1-k}F_{m-k}}{F_{m-k+1}}+\frac{F_m x}{F_{m+1}^2}$$ $$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)+\frac{F_m x}{F_{m+1}^2}=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m}\frac{(-x)^{1-k}F_{m-k}}{F_{m-k+1}}$$ By Theorem 1, the LHS is equal to $\Phi_{m+1}(x)$, and so $$\Phi_{m+1}(x)=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m}\frac{(-x)^{1-k}F_{m-k}}{F_{m-k+1}}$$ Which shows that the formula holds for $m+1$ as well. Thus, by induction, it holds for all $n\ge 1$. $\blacksquare$

Corollary 1: $$\Phi_n(-1)=\frac{n\phi^{-1}}{F_n}-\frac{1}{F_n}\sum_{k=0}^{n-1} \frac{F_k}{F_{k+1}},\space\space\space n\ge 1$$

Proof: This follows directly from Theorem 2, since $$\sum_{k=0}^{n-1} 1^{-k}=n$$ and since $\Phi_1(-1)=\phi^{-1}$. $\blacksquare$

Corollary 2: $$\Phi_{2n}(1)=\frac{1}{F_{2n}}\sum_{k=0}^{2n-1}\frac{(-1)^{k}F_{2n-k-1}}{F_{2n-k}},\space\space\space n\ge 1$$

Proof: This follows directly from Theorem 2, since $$\sum_{k=0}^{n-1} (-1)^{-k}=\begin{cases} 0 & \text{if n is even}\\ 1 & \text{if n is odd} \end{cases}$$

$\blacksquare$

Corollary 3: $$\Phi_{2n+1}(1)=\frac{\Phi_1(1)}{F_{2n+1}}+\frac{1}{F_{2n+1}}\sum_{k=1}^{n}\frac{1}{F_{2k}F_{2k+1}}, \space\space\space n\in\mathbb N, \space n\ge 1$$

Proof: This follows directly from Theorem 2, since $$\sum_{k=0}^{n-1} (-1)^{-k}=\begin{cases} 0 & \text{if n is even}\\ 1 & \text{if n is odd} \end{cases}$$

$\blacksquare$

Having derived these formulas, the answers to the first two proposed problems come easily: $$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_k F_{k+5}}=\phi^{-1}-\frac{83}{150}$$ $$\sum_{k=1}^\infty \frac{1}{F_k F_{k+6}}=\frac{143}{960}$$

I will now demonstrate how to use $\Phi_n(x)$ to evaluate a class of rather intimidating sums - sums in the form $$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}},\space\space\text{with}\space\space\space 0\le m\le n-1$$ To evaluate these sums, I will make use of the properties of the complex roots of unity: $$\omega_n := \cos \frac{2\pi}{n}+i\sin \frac{2\pi}{n}$$ I will now state two elementary properties (without proof) of the complex roots of unity that I will make use of later: $$\sum_{p=0}^{n-1} (\omega_n^p)^k= \begin{cases} n & \text{if} \space\space\space n|k\\ 0 & \text{else} \end{cases}\tag 1$$ $$\sum_{k=0}^{n-1} (\omega_n^p)^k= \begin{cases} n & \text{if} \space\space\space \omega_n^p=1\\ 0 & \text{else}\\ \end{cases}\tag 2$$

As a result,

Theorem 3: If $$G(x):=\sum_{k=1}^\infty x^k a_k$$ Then $$\sum_{p=0}^{n-1}(\omega_n^p)^m G(\omega_n^p)=n\sum_{k=1}^\infty a_{nk-m}$$

Proof: This theorem follows directly from properties (1) and (2) of the complex roots of unity. $\blacksquare$

Using the solution to the generalized recurrence and these identities, one may prove the following:

Theorem 4: $$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_n F_{n-m}}\bigg],\space\space\space n\ge 2, \space\space 0\le m\le n-1$$

Proof: I shall divide this proof into two cases - one for even $n$, and one for odd $n$. We shall consider even $n$ first.

Suppose $n$ is even. I will begin with the following formula from Theorem 2: $$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}\sum_{k=0}^{n-1} (-x)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-x)^{1-k}F_{n-k-1}}{F_{n-k}}$$ Letting $x=\omega_n^p$, we have $$\Phi_n(\omega_n^p)=\frac{\Phi_1(\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (-\omega_n^p)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{1-k}F_{n-k-1}}{F_{n-k}}$$ $$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{(-1)^{m-1}\Phi_1(\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (-\omega_n^p)^{m-k-1}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ By property (2) of the roots of unity, when $\omega_n^p\ne -1$, this is equal to $$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ and when $\omega_n^p=-1$, it is equal to $$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\Phi_1(-1)}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ $$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ This tells us that, since exactly one of the $\omega_n^p$ with $p$ between $0$ and $n-1$ is equal to $-1$, $$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\sum_{p=0}^{n-1}\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ $$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\sum_{p=0}^{n-1}(-\omega_n^p)^{m-k}\bigg)$$ Now note that since the sum $\sum_{p=0}^{n-1}(-\omega_n^p)^{m-k}$ cycles through the nth roots of unity, and since when $n$ is even, $\omega_n^p$ being a root of unity implies that $-\omega_n^p$ is also a root of unity, it is equal to the sum $\sum_{p=0}^{n-1}(\omega_n^p)^{m-k}$. Thus, $$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\sum_{p=0}^{n-1}(\omega_n^p)^{m-k}\bigg)$$ and, by identity (1), this is $$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\cdot\begin{cases} n & \text{if} \space\space\space n|m-k\\ 0 & \text{else} \end{cases}\bigg)$$ Now, if one assumes that $0\le m\le n-1$, the only value of $k$ between $0$ and $n-1$ satisfying $n|m-k$ would be $k=m$. Thus, all terms of the sum are multiplied by zero except for the $k=m$ term, and all that remains is $$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{n(-1)^{m-1}F_{n-m-1}}{F_nF_{n-m}}$$ Using Theorem 3, one may replace the LHS: $$\sum_{k=1}^\infty \frac{n}{F_{nk-m}F_{nk+n-m}}=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{n(-1)^{m-1}F_{n-m-1}}{F_nF_{n-m}}$$ $$\sum_{k=1}^\infty \frac{1}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg]$$ and, because $n$ is even, this is equivalent to $$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg]$$ Which completes the proof for the case of even $n$.

Now suppose that $n$ is odd. Again, I will begin with the following formula from Theorem 2: $$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}\sum_{k=0}^{n-1} (-x)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-x)^{1-k}F_{n-k-1}}{F_{n-k}}$$ but this time, I will let $x=-\omega_n^p$, so that $$\Phi_n(-\omega_n^p)=\frac{\Phi_1(-\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (\omega_n^p)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{1-k}F_{n-k-1}}{F_{n-k}}$$ $$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{(-1)^{m-1}\Phi_1(-\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (\omega_n^p)^{m-k-1}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ By property (2) of the roots of unity, when $\omega_n^p\ne 1$, this is equal to $$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ and when $\omega_n^p=1$, it is equal to $$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\Phi_1(-1)}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ $$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ Because of this, one may say that $$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\sum_{p=0}^{n-1}\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$$ $$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\sum_{p=0}^{n-1}(\omega_n^p)^{m-k} \bigg)$$ By property (1), this is $$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\cdot \begin{cases} n & \text{if} \space\space\space n|m-k\\ 0 & \text{else} \end{cases} \bigg)$$ If one assumes that $0\le m\le n-1$, the only term of the sum that does not vanish is the term for which $k=m$. Thus, $$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\frac{nF_{n-m-1}}{F_{n-m}}$$ $$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=(-1)^{m-1}\bigg[\frac{n\phi^{-1}}{F_n}-\frac{nF_{n-m-1}}{F_nF_{n-m}}\bigg]$$ By Theorem 3, the LHS can be replaced with an infinite series: $$n\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{n\phi^{-1}}{F_n}-\frac{nF_{n-m-1}}{F_nF_{n-m}}\bigg]$$ and so, at last, $$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg]$$ Which completes the proof for the case of odd $n$. Thus I have established that $$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg],\space\space\space n\ge 2, \space\space 0\le m\le n-1 \space\space\space\blacksquare$$

With this formula, the third and fourth proposed problems may be solved readily: $$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_{5k-1}F_{5k+4}}= \frac{2}{15}-\frac{\phi^{-1}}{5}$$ $$\sum_{k=1}^\infty \frac{1}{F_{10k}F_{10k+10}}=\frac{\phi^{-1}}{55}-\frac{34}{3025}$$