# 2008 Mock ARML 2 Problems/Problem 8

## Problem

Given that $\sum_{i = 0}^{n}a_ia_{n - i} = 1$ and $a_n > 0$ for all non-negative integers $n$, evaluate $\sum_{j = 0}^{\infty}\frac {a_j}{2^j}$.

## Solution

$a_0^2=1\Rightarrow a_0=1$

$a_0a_1+a_1a_0=1\Rightarrow a_1=\dfrac{1}{2}$

$a_0a_2+a_1^2+a_2a_0=1\Rightarrow a_2=\dfrac{3}{8}$

$a_0a_3+a_1a_2+a_2a_1+a_3a_0=2a_3+\dfrac{3}{8}=1\Rightarrow a_3=\dfrac{5}{16}$

We make a conjecture that $a_i=\dfrac{F_{i+3}}{2^{i+1}}$, where $F_n$ is the $n$th Fibonacci number and we prove that it is so:

$a_ia_{n-i}=\dfrac{F_{i+3}\cdot F_{n-i+3}}{2^{n+2}}$

We must prove that $\sum_{i = 0}^{n}\dfrac{F_{i+3}\cdot F_{n-i+3}}{2^{n+2}} = 1$.