Let $(a_n)$ be defined by $a_1=a_2=1$ and $a_n=a_{n-1}+a_{n-2}$ for $n>2$. Compute the sum $\frac{a_1}2+\frac{a_2}{2^2}+\frac{a_3}{2^3}+\ldots$.
Problem
Source: Croatia 1999 4th Grade P3
Tags: Sum, Summation, Fibonacci, Fibonacci sequence, algebra
RagvaloD
18.05.2021 02:08
$S=\frac{a_1}{2}+\frac{a_2}{2^2}+\frac{a_3}{2^3}+...=\frac{a_1}{2}+\frac{a_2}{2^2}+\frac{a_1+a_2}{2^3}+\frac{a_2+a_3}{2^4}+...= \frac{a_1}{2}+\frac{a_2}{2^2}+\frac{1}{4} (\frac{a_1}{2}+\frac{a_2}{2^2}+...)+\frac{1}{2} (\frac{a_2}{2^2}+\frac{a_3}{2^3}+...)=\frac{a_1}{2}+\frac{a_2}{2^2}+\frac{S}{4}+\frac{S-\frac{a_1}{2}}{2} = \frac{3}{4}S+\frac{a_1+a_2}{4}\to S=a_1+a_2=2$
Kuttus
10.06.2021 18:33
can this be done without proving whether s is convergent or not?
pinkpig
10.06.2021 20:07
Let $S=\frac{a_1}2+\frac{a_2}{2^2}+\frac{a_3}{2^3}+\ldots.$ We can express $S$ as $\frac{1}{2}+\frac{1}{4}+\frac{2}{8}+\frac{3}{16}+\ldots.$ Also, we can find that $2S = 1+\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\ldots.$ Therefore, $2S-S=S=1+0+\frac{1}{4}+\frac{1}{8}+\frac{2}{16}+\frac{3}{32}+\ldots=1+\frac{S}{2}.$ Solving $\frac{S}{2}+1=S,$ we find that $S=2$ so $\frac{a_1}2+\frac{a_2}{2^2}+\frac{a_3}{2^3}+\ldots=2.$
Hope this helps! Please tell me if there are any errors in my solution.
jasperE3
10.06.2021 20:17
You can also just plug $\frac12$ into the generating function for the Fibonacci sequence.