# Infinite geometric sum (asking for insight on an easier solution)

Let the sequence $F$ be defined as: $F_1=F_2=1$ and $F_n=2F_{n-1}+F_{n-2}$, for $n>2$. Evaluate $\sum_{n=1}^{\infty}\frac{F_n}{10^n}$.

The obvious solution involves solving for the explicit formula for $F$ (using the standard linear recurrence technique): $F_n=(\frac{\sqrt{2}-1}{2})(1+\sqrt{2})^n-(\frac{\sqrt{2}+1}{2})(1-\sqrt{2})^n$. Then we can just split the sum into two infinite geometric series. The computation is annoying, but nonetheless straightforward.

I was wondering if there is any easier solution than solving for an explicit formula for $F$. Maybe there is one that only needs the recursive definition? Any comments are appreciated.

Define $$S=\sum_{n=1}^{\infty}{{F_n}\over{10^n}}$$.

For proving that $$S$$ exists, note that $$F_n$$ is strictly increasing since $$F_1,F_2>0$$. Therefore we can obtain that $$F_n=2F_{n-1}+F_{n-2}\le 3F_{n-1}$$. Now define $$b_n={{F_n}\over{10^n}}$$ thus we get here: $${{b_{n+1}}\over{b_n}}={{F_{n+1}}\over{10F_n}}\le0.3<1$$ which implies on convergence according to d'Alembert's ratio test

After proving convergence we have: $$\begin{split} S &= {1\over 10} + {1\over 100} + \sum_{n=3}^{\infty}{F_n\over{10^n}}\\ &= {1\over 10} + {1\over 100} + \sum_{n=3}^{\infty}{{F_{n-2}+2F_{n-1}}\over{10^n}}\\ &= {11\over 100} + \sum_{n=1}^{\infty}{{F_n}\over{10^{n+2}}} + \sum_{n=2}^{\infty}{{F_n}\over{10^{n+1}}}\\ &= {11\over 100}+{S\over 100}+{2S\over 10}-{2\over 100}\\ &={{21S+9}\over 100} \implies S={9\over 79} \end{split}$$

• Awesome solution!
– Max
Jan 6, 2018 at 17:58
• That's very kind of you! Jan 6, 2018 at 18:01
• I just followed the solution step by step and obtained that result... Jan 6, 2018 at 21:28
• If still you are curious why S exists define $b_n={{F_n}\over{10^n}}$ and calculate $lim_{n\to\infty}{{b_{n+1}}\over{b_n}}$. Jan 6, 2018 at 21:31
• The point is, you proved one implication: if the sum converges, it has to converge to $9/79$. In principle, it is still possible that the sum fails to converge. A convergence criterion, as you just pointed out, suffices.
– chi
Jan 6, 2018 at 21:31

Of course, someone needs to prove that $A=\sum_{n=1}^{\infty}\frac{F_n}{10^n}$ exists. (E.g. by induction you prove $F_n\le 3^n$.)

However, once you prove that, the calculation is straightforward:

$$0=\sum_{n=1}^{\infty}\frac{F_{n+2}-2F_{n+1}-F_n}{10^n}=100\sum_{n=3}^{\infty}\frac{F_n}{10^n}-20\sum_{n=2}^{\infty}\frac{F_n}{10^n}-\sum_{n=1}^{\infty}\frac{F_n}{10^n}=100\left(A-\frac{1}{10}-\frac{1}{100}\right)-20\left(A-\frac{1}{10}\right)-A$$

So, $79A=9$, or $A=\frac{9}{79}$.

Use the method of generating functions. let $F_n=0$ for $n<0$. First make the recurrence valid for all $n\geq 0$. Substituting $2$ into the recurrence yields that $F_0=-1$. The recurrence $$F_n=2F_{n-1}+F_{n-2}+3\delta_{n,1}-\delta_{n,0}\quad (n\geq 0)\tag{1}$$ where $\delta$ is the Kronecker delta is valid for $n\geq 0$. Multiply both sides by $x^n$ and sum on $n$ to get that $$F(x)(1-2x-x^2)=3x-1\implies F(x)=\frac{3x-1}{1-2x-x^2}\tag{2}$$ where $F$ is the generating function associated with $F_n$ i.e. $\sum_{n=1}^{\infty}F_n x^n.$ Up to this point we can regard $F$ as a formal power series or as an analytic function. In fact $F$ has a nonzero radius of convergence (in fact from the roots of the denominator it converges for $|x|<(1+\sqrt{2})^{-1}$ and $0<1/10<(1+\sqrt{2})^{-1}$). Hence $$\sum_{n=1}^{\infty}\frac{F_n}{10^n}=F(1/10)+1=1-\frac{70}{79}=\frac{9}{79}.\tag{3}$$

• Thanks for the reply. Interesting solution.
– Max
Jan 6, 2018 at 23:57

\begin{align*} \sum_{n=1}^\infty\frac{F_n}{10^n}&=\frac{1}{10}+\frac{1}{100}+\sum_{n=3}^\infty\frac{F_n}{10^n}\\ &=0.11+\sum_{n=3}^\infty\frac{2F_{n-1}+F_{n-2}}{10^n}\\ &=0.11+\frac{2}{10}\left(\sum_{n=1}^\infty\frac{F_n}{10^n}-\frac{1}{10}\right)+\frac{1}{100}\sum_{n=1}^\infty\frac{F_n}{10^n}\\ 0.79\sum_{n=1}^\infty\frac{F_n}{10^n}&=0.09\\ \sum_{n=1}^\infty\frac{F_n}{10^n}&=\frac{9}{79} \end{align*}

$$S(x)=\sum_{n=1}^{\infty} x^n F_n=xF_1+x^2 F_2+ \sum_{n=3}^{\infty} x^n F_n=$$ $$=x+x^2+\sum_{n=3}^{\infty} x^n (2F_{n-1}+F_{n-2})=$$ $$=x+x^2 +2x\sum_{m=2}^{\infty}x^m F_m+x^2\sum_{m=1}^{\infty}xF_m=$$ $$=x+x^2 + 2x(S(x)-xF_1)+x^2S(x)=x+x^2+2x(S(x)-x)+x^2S(x).$$ $$\text {Therefore } \quad S(x)(1-2x-x^2)=x+x^2-2x^2=x-x^2.$$ When $$x=0.1$$ this implies $$S(0.1)\cdot (0.79)=0.09.$$

• Since $\lim_{m\to \infty} \sup_{n\geq m} |F_n (1+\sqrt 2\;)^{-n}|<\infty,$ the series $\sum_{n=1}^{\infty} x^n F_n$ converges for $|x|<(1+\sqrt 2)^{-1}.$ Jan 7, 2018 at 10:15