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.
 A: 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}
$$
A: \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*}
A: $$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.$
A: 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}
$$
A: 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}$.
