12
$\begingroup$

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.

$\endgroup$
2

5 Answers 5

27
$\begingroup$

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

$\endgroup$
10
  • 3
    $\begingroup$ Awesome solution! $\endgroup$
    – Max
    Jan 6, 2018 at 17:58
  • $\begingroup$ That's very kind of you! $\endgroup$ Jan 6, 2018 at 18:01
  • $\begingroup$ I just followed the solution step by step and obtained that result... $\endgroup$ Jan 6, 2018 at 21:28
  • $\begingroup$ 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}}$. $\endgroup$ Jan 6, 2018 at 21:31
  • 2
    $\begingroup$ 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. $\endgroup$
    – chi
    Jan 6, 2018 at 21:31
11
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the reply. Interesting solution. $\endgroup$
    – Max
    Jan 6, 2018 at 23:57
5
$\begingroup$

\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*}

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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}.$ $\endgroup$ Jan 7, 2018 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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