Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(New page: ==Problem== Given that <math>\sum_{i = 0}^{n}a_ia_{n - i} = 1</math> and <math>a_n > 0</math> for all non-negative integers <math>n</math>, evaluate <math>\sum_{j = 0}^{\infty}\frac {a_j}{...)
 
m (→‎Solution)
 
(5 intermediate revisions by 4 users not shown)
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 polynomials (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>\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]]:
 +
<center><math>\left[\sum_{j = 0}^{\infty} a_jx^j\right]^2  = 1 + x + x^2 + \cdots = \frac{1}{1-x}</math></center>
 +
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>.
  
−
<math>a_0a_2+a_1^2+a_2a_0=1\Rightarrow a_2=\dfrac{3}{8}</math>
+
==See also==
−
 
+
{{Mock ARML box|year = 2008|n = 2|num-b=7|after=Final Question|source = 206880}}
−
<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>
 
−
 
 
−
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>
+
[[Category:Intermediate Algebra Problems]]
−
 
 
−
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==
 

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_Mock_ARML_2_Problems/Problem_8&oldid=78756"