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

(Solution)
m (Solution)
 
(One intermediate revision by one other user not shown)
Line 3: Line 3:
  
 
==Solution==
 
==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 [[multinomial]]s (or [[generating functions]]).  
+
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 polynomials (or [[generating functions]]).  
  
 
Let <math>x</math> be an arbitrary number; note that  
 
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_1 + a_2a_0)x^2 + \cdots\end{align*}</math></center>
+
<center><math>\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_1 + a_2a_0)x^2 + \cdots</math></center>
 
By the given, the coefficients on the right-hand side are all equal to <math>1</math>, yielding the [[geometric series]]:
 
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>
 
<center><math>\left[\sum_{j = 0}^{\infty} a_jx^j\right]^2  = 1 + x + x^2 + \cdots = \frac{1}{1-x}</math></center>

Latest revision as of 00:57, 31 May 2016

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 polynomials (or generating functions).

Let $x$ be an arbitrary number; note that

$\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_1 + a_2a_0)x^2 + \cdots$

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