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.

Solution 1:

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

Solution 2:

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

Solution 3:

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