Difference between revisions of "2008 Mock ARML 2 Problems/Problem 8"

m (category)
(solution)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
<math>a_0^2=1\Rightarrow a_0=1</math>
+
The motivating factor for this solution is the form of the first summation, which might remind us of the expansion of the coefficients of the product of two [[multinomial]]s (or [[generating functions]]).
  
<math>a_0a_1+a_1a_0=1\Rightarrow a_1=\dfrac{1}{2}</math>
+
Let <math>x</math> be an arbitrary number; note that
 
+
<center><math>\begin{align*}\left[\sum_{j = 0}^{\infty} a_jx^j\right]^2 &= (a_0 + a_1 \cdot x + a_2 \cdot x^2 + \cdots)^2\\ &= a_0^2 + (a_0a_1 + a_1a_0)x + (a_0a_2 + a_1a_2 + a_2a_0)x^2 + \cdots\end{align*}</math></center>
<math>a_0a_2+a_1^2+a_2a_0=1\Rightarrow a_2=\dfrac{3}{8}</math>
+
By the given, the coefficients on the right-hand side are all equal to <math>1</math>, yielding the [[geometric series]]:
 
+
<center><math>\left[\sum_{j = 0}^{\infty} a_jx^j\right]^2 = 1 + x + x^2 + \cdots = \frac{1}{1-x}</math></center>
<math>a_0a_3+a_1a_2+a_2a_1+a_3a_0=2a_3+\dfrac{3}{8}=1\Rightarrow a_3=\dfrac{5}{16}</math>
+
For <math>x = \frac{1}{2}</math>, this becomes <math>\left[\sum_{j = 0}^{\infty}\frac {a_j}{2^j}\right]^2 = 2</math>, and the answer is <math>\boxed{\sqrt{2}}</math>.
 
 
We make a conjecture that <math>a_i=\dfrac{F_{i+3}}{2^{i+1}}</math>, where <math>F_n</math> is the <math>n</math>th [[Fibonacci number]] and we prove that it is so:
 
 
 
<math>a_ia_{n-i}=\dfrac{F_{i+3}\cdot F_{n-i+3}}{2^{n+2}}</math>
 
 
 
We must prove that <math>\sum_{i = 0}^{n}\dfrac{F_{i+3}\cdot F_{n-i+3}}{2^{n+2}} = 1</math>.
 
 
 
{{solution}}
 
  
 
==See also==
 
==See also==
 
{{Mock ARML box|year = 2008|n = 2|num-b=7|after=Final Question|source = 206880}}
 
{{Mock ARML box|year = 2008|n = 2|num-b=7|after=Final Question|source = 206880}}
  
[[Category:Intermediate Number Theory Problems]]
+
[[Category:Intermediate Algebra Problems]]

Revision as of 08:30, 1 June 2008

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

The motivating factor for this solution is the form of the first summation, which might remind us of the expansion of the coefficients of the product of two multinomials (or generating functions).

Let $x$ be an arbitrary number; note that

$\begin{align*}\left[\sum_{j = 0}^{\infty} a_jx^j\right]^2 &= (a_0 + a_1 \cdot x + a_2 \cdot x^2 + \cdots)^2\\ &= a_0^2 + (a_0a_1 + a_1a_0)x + (a_0a_2 + a_1a_2 + a_2a_0)x^2 + \cdots\end{align*}$ (Error compiling LaTeX. ! Package amsmath Error: \begin{align*} allowed only in paragraph mode.)

By the given, the coefficients on the right-hand side are all equal to $1$, yielding the geometric series:

$\left[\sum_{j = 0}^{\infty} a_jx^j\right]^2  = 1 + x + x^2 + \cdots = \frac{1}{1-x}$

For $x = \frac{1}{2}$, this becomes $\left[\sum_{j = 0}^{\infty}\frac {a_j}{2^j}\right]^2 = 2$, and the answer is $\boxed{\sqrt{2}}$.

See also

2008 Mock ARML 2 (Problems, Source)
Preceded by
Problem 7
Followed by
Final Question
1 2 3 4 5 6 7 8
Invalid username
Login to AoPS