Putnam 2011 A2

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

5 users

TOPICS

No tags match your search

M

No tags match your search

M

Putnam 2011 A2

G H J

Reveal topic tags

geometric series

college contests

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#1 h Dec 5, 2011, 12:47 AM • 5 Y

Y by Binomial-theorem, Rounak_iitr, Adventure10, Mango247, NicoN9

Let $a_1,a_2,\dots$ and $b_1,b_2,\dots$ be sequences of positive real numbers such that $a_1=b_1=1$ and $b_n=b_{n-1}a_n-2$ for $n=2,3,\dots.$ Assume that the sequence $(b_j)$ is bounded. Prove that $S=\sum_{n=1}^{\infty}\frac1{a_1\cdots a_n}$ converges, and evaluate $S.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Dec 5, 2011, 12:47 AM • 5 Y

Y by A_Math_Lover, kamatadu, Adventure10, NicoN9, MS_asdfgzxcvb

Note that $a_n=\frac{b_n+2}{b_{n-1}}=\left(1+\frac2{b_n}\right)\frac{b_n}{b_{n-1}}.$ The last part telescopes in the product, giving us
$a_1a_2\cdots a_n=\left(1+\frac2{b_2}\right)\left(1+\frac2{b_3}\right)\cdots\left(1+\frac2{b_n}\right)b_n.$
With $0<b_n\le M,$ the series for $S$ converges by comparison to a constant time a geometric series with ratio $\left(1+\frac2M\right)^{-1}.$

The sum is $\frac32.$

We claim, inductively, that for $n\ge 2,$ $S_n=\sum_{k=1}^n\frac{1}{a_1a_2\cdots a_k}=\frac32-\frac{1}{2\left(1+\frac2{b_2}\right)\cdots\left(1+\frac2{b_n}\right)}.$

For $n=2,$ $\frac32-S_2=\frac32-1-\frac{\frac1{b_2}}{1+\frac2{b_2}}=\frac1{2\left(1+\frac2{b_2}\right)},$ which starts the induction.
$\begin{align*}\frac32-S_{n+1}&=\frac32-S_n-\frac{\frac1{b_{n+1}}}{\left(1+\frac2{b_2}\right)\cdots\left(1+\frac2{b_{n+1}}\right)}\\ &=\frac{1}{2\left(1+\frac2{b_2}\right)\cdots\left(1+\frac2{b_n}\right)}-\frac{\frac1{b_{n+1}}}{\left(1+\frac2{b_2}\right)\cdots\left(1+\frac2{b_{n+1}}\right)}\\ &=\frac{1+\frac2{b_{n+1}}-\frac2{b_{n+1}}}{2\left(1+\frac2{b_2}\right)\cdots\left(1+\frac2{b_{n+1}}\right)}\\ &=\frac{1}{2\left(1+\frac2{b_2}\right)\cdots\left(1+\frac2{b_{n+1}}\right)} \end{align*}$
Since $\frac32-S_n$ tends to zero, we have $S=\lim S_n=\frac32.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

479 posts

#3 h Dec 5, 2011, 1:35 AM • 1 Y

Y by Adventure10

Alternatively, if $c_n = b_n/a_1a_2...a_n$ ,
$c_n = c_{n-1} - 2/a_1a_2...a_n$ .
Hence $c_n<c_{n-1}$ and $0<c_n$ so $c_n\to c_\infty$ by the monotone sequence theorem. This implies that $\sum 1/a_1...a_n$ converges, so $1/a_1...a_n\to 0$ . Since $b$ is bounded, $c_n\to 0$ and so $c\infty = 0$ .
The rest follows from expanding $c_n$ in terms of $c_1 = a_1/b_1$ and $a_2,a_3,...,a_n$ and taking the limit as $n\to\infty$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

228 posts

#4 h Dec 5, 2011, 6:30 AM • 1 Y

Y by Adventure10

Start writing out the $b_i$ in terms of $a_i$ , and find that it looks somewhat nice:
$b_2=a_1a_2-2$
$b_3=a_1a_2a_3-2a_3-2=a_1a_2a_3\left(1-\frac2{a_1a_2}-\frac2{a_1a_2a_3}\right)$
So, let $p_n=a_1a_2\ldots a_n$ , and let
$K_n=\sum_{i=2}^n\frac1{p_i}$
Prove by induction that $b_n=p_n(1-2K_n)$
Since $b_n>0$ , you get $K_n$ is bounded above by 1/2, and is increasing, so converges. If you let $M$ be an upper bound on the $b_i$ , and if $K_n$ converges to some $L<1/2$ , you get
$\frac M{1-2L}>p_n$
contrary to the fact that $1/p_n\to 0$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6920 posts

fedja

#5 h Dec 5, 2011, 10:13 PM • 14 Y

Y by A_Math_Lover, cttg8217, CANBANKAN, natmath, Ru83n05, Adventure10, Mango247, spiritshine1234, MS_asdfgzxcvb, and 5 other users

This is also one of the problems that you can figure out almost mechanically starting with the assumption that it is solvable (which you can safely use when you have a competition problem).

First of all, $a$ 's are useless because if you know $b$ 's, you know $a$ 's (Put $b_0=3$ to get $a_1$ correct)
Let $F(b_0,b_1,\dots)$ be the sum of the series. Then we have
$F(b_0,b_1,\dots)=\frac {b_0}{b_1+2}(1+F(b_1,b_2,\dots))$
Now, you are just given $b_0=3$ and $b_1=1$ and are asked to find the limit. Thus, if the problem is solvable, $F$ must depend just on the first 2 variables. Now, since the left hand side does not depend on $b_2$ , the right hand side should not depend on $b_2$ too, so $F$ must depend just on the first argument, giving
$F(x)=\frac x{y+2}(1+F(y))$
Hence, $\frac{F(x)}{x}=\frac{1+F(y)}{y+2}$ for all $x$ , $y$ , so both parts are constant $c$ .
Thus $c=\frac{1+cy}{y+2}$ identically, whence $c=\frac 12$ .

Moral: if the problem is solvable, the limit is $F(b_0)=\frac{b_0}2$ . If we understand anything about limits on contest problems at all, it is that it always makes sense to subtract them from the expressions. So, let now $F_n(b_0,\dots,b_n)=\frac{b_0}2+S_n(b_0,\dots,b_n)$ be the partial sum of $n$ terms. We get the relation $S_n(b_0,\dots,b_n)=\frac{b_0}{b_1+2}S_{n-1}(b_1,\dots,b_n)$ , which is a piece of cake to solve: $S_n(b_0,\dots,b_n)=\prod_{j=0}^{n-1}\frac{b_j}{b_{j+1}+2}=\frac{b_0}{b_n+2}\prod_{j=1}^{n-1}\frac{b_j}{b_{j}+2}$ . The rest is obvious.

Note that the key point of this solution is that it requires no brainpower or ingenuity whatsoever, just strong faith in the existence of the solution plus some basic common sense. I wish we could play the same game in religion

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

36 posts

#6 h Dec 5, 2011, 11:12 PM • 6 Y

Y by Kezer, anser, v4913, kamatadu, Adventure10, Mango247

$\frac{1}{a_1 a_2 \dots a_n}$ = $\frac{1}{a_1 a_2 \dots a_n}*\frac{b_{n-1}a_n - b_n}{2}$ = $\frac{b_{n-1}}{2a_1 a_2 \dots a_{n-1}} - \frac{b_n}{2a_1 a_2 \dots a_n}$ .

Then we add them up, and get the partial sum $3/2 - \frac{b_N}{2a_1 a_2 \dots a_N}$ .

$\frac{b_N}{a_1 a_2 \dots a_N} = \frac{b_2}{b_2+2}\dots \frac{b_N}{b_N+2}$ which converges to 0 since $\frac{b_n}{b_n+2}$ is bounded by a positive number less than 1 by the boundedness of { $b_n$ }.

So the answer is $3/2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

723 posts

codyj

#7 h Nov 4, 2015, 2:37 AM • 3 Y

Y by e_plus_pi, Adventure10, Mango247

Prove inductively that $\sum_{n=1}^N\frac1{a_1a_2\dots a_n}=\frac32-\frac12\left(\prod_{k=2}^N(1+\frac2{b_i})\right)^{-1}$ . Then that is $<\frac32$ and $>\frac32-\frac12\left(\frac{M}{M+2}\right)^N>\frac32-\epsilon$ for all $\epsilon>0$ and large enough $N$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SymplecticCamel

6 posts

SymplecticCamel

#9 h Aug 30, 2021, 11:08 PM

Y by

Define
$S_n = \frac{3}{2}\left (1 - \prod_{k=1}^n \frac{b_k}{b_{k }+ 2} \right).$
Note that since $a_n = \frac{b_n + 2}{b_{n -1}}$ , we have that
$2S_n = 3 + \frac{3b_n}{b_{1} + 2}\prod_{k=2}^{n} \frac{b_{k-1}}{b_{k} + 2} = 3 + \frac{b_n}{a_1\dots a_n}.$
It follows that
$\begin{align*} 2S_n - 2S_{n-1} &= \frac{b_n}{a_1 \dots a_n} - \frac{b_{n-1}}{a_1 \dots a_{n-1}} \\ &= \frac{b_n - b_{n-1}a_n}{a_1 \dots a_n} \\ &= \frac{2}{a_1 \dots a_n}. \end{align*}$ Therefore, $S_n = \sum_{k=1}^n \frac{1}{a_1 \dots a_k}$ .

It is clear that $(S_n)$ is monotone, and using the original expression for $S_n$ , we see that $S_n$ is also bounded by $3/2$ . It follows that $S_n$ converges by the monotone convergence theorem.

Furthermore, note that $\prod_{k=1}^n \frac{b_k}{b_{k} + 2} \to 0$ as $n \to \infty$ , so it follows that $S = \lim_{n \to \infty} S_n = \frac{3}{2}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

Fafnir

#12 h Feb 19, 2022, 2:16 PM

Y by

Answer : $S= \frac{3}{2}$

It is easy to see that $a_n = \frac{b_n+2}{b_{n-1}}$ We can rewrite $S$ in terms of $b_i$ $S = 1+\sum_{n=2}^{\infty} \frac{b_2b_3 \dots b_{n-1}}{(b_2+2)(b_3+2) \dots (b_n+2)}$ It can be obseved that $\frac{b_2b_3 \dots b_n}{(b_2+2)(b_3+2) \dots (b_n+2)} = \frac{b_2b_3 \dots b_{n-1}}{(b_2+2)(b_3+2) \dots (b_{n-1}+2)} - 2\frac{b_2b_3 \dots b_{n-1}}{(b_2+2)(b_3+2) \dots (b_n+2)}$ $\frac{b_2b_3 \dots b_{n-1}}{(b_2+2)(b_3+2) \dots (b_n+2)} = \frac{1}{2} (\frac{b_2b_3 \dots b_{n-1}}{(b_2+2)(b_3+2) \dots (b_{n-1}+2)} - \frac{b_2b_3 \dots b_n}{(b_2+2)(b_3+2) \dots (b_n+2)})$
Take $c_n = \frac{b_2b_3 \dots b_n}{(b_2+2)(b_3+2) \dots (b_n+2)}$ $S = 1 + \frac{1}{2}(\sum_{n=2}^{\infty} c_{n-1}-c_{n})$ Note : $c_1=1$

Now lets say $0<b_i<x$ so it can be said that $\frac{b_i}{b_i+2} \le \frac{x}{x+2} < 1$
$S_n = \frac{3}{2} - \frac{1}{2} \frac{b_2b_3 \dots b_n}{(b_2+2)(b_3+2) \dots (b_n+2)}$
We can say that $S_n < \frac{3}{2}$
Also $S_n \ge 3/2 - \frac{1}{2} (\frac{x}{x+2})^n$
$3/2 > S_n \ge \frac{3}{2} - \frac{1}{2} (\frac{x}{x+2})^n$
On taking limit $n \to \infty$ , we get $S$ to converge at $\frac{3}{2}$

This post has been edited 2 times. Last edited by Fafnir, Feb 19, 2022, 2:17 PM
Reason: t

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2807 posts

#14 h Dec 29, 2022, 4:19 PM

Y by

Note that $\frac{b_n + 2}{b_{n-1}} = a_n$ , and $\frac{b_{n-1}a_n - b_n}{2} = 1$ .

Hence $\begin{align*} \sum_{n=1}^{\infty}\frac1{a_1\cdots a_n} & = \sum_{n=1}^{\infty}\frac{b_{n-1}a_n - b_n}{2a_1\cdots a_n} \\ &= \sum_{n=1}^{\infty}\frac{b_{n - 1}}{2a_1\cdots a_{n-1}} - \frac{b_{n}}{2a_1\cdots a_{n-1}a_n} \\ &= \frac{b_0}{2a_0} - \frac{b_1}{2a_1} + \frac{b_1}{2a_1} + \dots - \frac{b_n}{2a_1a_2\cdots a_n} \\ &= \frac{3}{2} - \frac{b_n}{2a_1a_2\cdots a_n}. \end{align*}$ Note that $\frac{b_n}{2a_1a_2\cdots a_n} = \frac{b_n}{2a_2\cdots a_n} = \frac{b_2 b_3 \cdots b_n}{2(b_1 + 2)(b_2 + 2)\cdots(b_n + 2)}.$ Furthermore, $\lim_{n \to \infty} \prod_{j=1}^{n} \frac{b_j}{b_j + 2} = 0$ because $b_j$ is bounded.

Therefore, $S$ converges and it evaluates to $\frac{3}{2}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#16 h Jan 1, 2023, 5:09 AM • 4 Y

Y by kamatadu, GrantStar, Sagnik123Biswas, NicoN9

$b_n$ looks like a geometric series, so how do we encode that?

Simply substitute $1 = \frac{b_{n-1}a_n-b_n}2$ and see magic happen. The sum $S = \sum_{n=1}^\infty \frac{b_{n-1}a_n-b_n}{2a_1a_2\cdots a_n} = \frac 12 \sum_{n=2}^\infty \frac{b_{n-1}}{a_1a_2 \cdots a_{n-1}} - \frac{b_n}{a_1 a_2 \cdots a_n} + 1 = \frac 12 \cdot \frac{b_1}{a_1} + 1 = \frac 32.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#17 h Sep 22, 2023, 1:03 AM

Y by

What if we miss the telescoping solution?

Write a few earlier terms and notice patterns.

I want my denominator to look nice, so I let $x_n = b_n+2$ , so $a_n = \frac{x_n}{x_{n-1}-2}$ and then $\frac{1}{a_2} = \frac{1}{x_2}, \frac{1}{a_2a_3} = \frac{x_2-2}{x_2x_3}, \frac{1}{a_2a_3a_4} = \frac{(x_2-2)(x_3-2)}{x_2x_3x_4}$ .

At this point, it I expand this, note

$\frac{1}{a_2} + \frac{1}{a_2a_3} + \frac{1}{a_2a_3a_4} = \frac{1}{x_2} + \frac{1}{x_3} + \frac{1}{x_4} - \frac{2}{x_2x_3} - \frac{2}{x_2x_4} - \frac{2}{x_3x_4} + \frac{4}{x_2x_3x_4}$

$= \frac 12 (y_2+y_3+y_4-y_2y_3-y_3y_4-y_2y_4 + y_2y_3y_4)$
Where $y_j = \frac{2}{x_j}$

Let $S = y_2+y_3+y_4-y_2y_3-y_3y_4-y_2y_4 + y_2y_3y_4$ This expression not only looks like PIE, but in fact, $1-S = (1-y_2)(1-y_3)(1-y_4)$ . Therefore, we can induct on $n$ to show that the sum of the first $n$ terms is actually $1 + \frac 12 ( 1 - (1-y_2)(1-y_3)(1-y_4) \cdots (1-y_n))$ which tends to $\frac 32$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

657 posts

#18 h Nov 14, 2023, 3:30 AM

Y by

Let $x_{n} = \frac{1}{a_{1}a_{2}\cdots a_{n}}$ . Note that
$\begin{align*} b_{n} &= b_{n-1}a_{n}-2 \\ &= b_{n-2}a_{n-1}a_{n}-2a_{n}-2 \\ &= b_{n-3}a_{n-2}a_{n-1}a_{n}-2a_{n-1}a_{n}-2a_{n}-2 \\ &= \cdots \\ &= a_{n}a_{n-1}\cdots a_{1}-2a_{n}a_{n-1}\cdots a_{2} \cdots \\ &= \frac{1}{d_{n}}-2\frac{d_{n-1}}{d_{n}}-2\frac{d_{n-2}}{d_{n}}\cdots -2\frac{d_{n}}{d_{n}} \end{align*}$ Multiplying by $d_{n}$ on both sides and subtracting 3 yields
$b_{n}d_{n}-3 = -2\displaystyle\sum_{k=1}^{n}{d_{k}}$ Note that as $n$ approaches $\infty$ , then $b_{n}d_{n}$ approaches $0$ , because $b$ is bounded and $d$ approaches $0$ . Thus, we have that it converges to $\boxed{\frac{3}{2}}$ .

This post has been edited 1 time. Last edited by Spectator, Nov 14, 2023, 3:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

815 posts

#19 h Jan 9, 2024, 3:17 AM • 1 Y

Y by OronSH

Define $P_n=\prod_{i=1}^n a_i$ and $S_i=\sum_{i=1}^n \frac{1}{P_i}$ . Note that $b_n=P_n-2\left(\sum{i=2}^{n-1}\frac{P_{n}}{P_{i}}\right)=P_n(3-2S_{n-1})$ Using $b_n$ and $P_n$ are positive, we get $S_{n-1}<\frac 32$ .
Now, suppose $c>b_i$ for all $b_i$ and $C$ is large, so $c>P_n(3-2S_{n-1}) \iff P_n>\frac{3-2S_{n-1}}{c} \iff S_n>\frac{S_{n-1}(c-2)+3}{c}.$ Then, if $K_n=\frac 32 -S_n$ , we have $\frac 32 -K_n >\frac{\left(\frac 32 -K_{n-1}\right)(c-2)+3}{c}=\frac{(c-2)(-K_{n-1})}{c}+\frac 32$ which rearranges into $K_{n-1}\cdot \frac{c-2}{c}\geq K_n$ which implies $K_n$ goes to $0$ so $S_n$ goes to $\frac 32$ .

This post has been edited 1 time. Last edited by GrantStar, Jan 9, 2024, 3:18 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CrazyVideoGamez

11 posts

CrazyVideoGamez

#20 h Dec 1, 2024, 3:40 AM

Y by

HamstPan38825 wrote:

$b_n$ looks like a geometric series, so how do we encode that?

Simply substitute $1 = \frac{b_{n-1}a_n-b_n}2$ and see magic happen. The sum $S = \sum_{n=1}^\infty \frac{b_{n-1}a_n-b_n}{2a_1a_2\cdots a_n} = \frac 12 \sum_{n=2}^\infty \frac{b_{n-1}}{a_1a_2 \cdots a_{n-1}} - \frac{b_n}{a_1 a_2 \cdots a_n} + 1 = \frac 12 \cdot \frac{b_1}{a_1} + 1 = \frac 32.$

Does this imply that the boundedness of $b$ condition is unnecessary?

This post has been edited 1 time. Last edited by CrazyVideoGamez, Dec 1, 2024, 3:40 AM
Reason: more details

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1010 posts

#21 h Feb 19, 2025, 9:42 AM

Y by

One may computationally verify that $\frac{b_N}{\prod_{j=1}^N a_j}=1-2\sum_{n=2}^N\frac1{\prod_{j=1}^n a_j}.$ Since $a_1=1$ , it follows that $\sum_{n=1}^N\frac1{\prod_{j=1}^n a_j}=\frac32-\frac{b_N}{2\prod_{j=1}^N a_j}\le\frac32-\frac{M}{2\prod_{j=1}^Na_j},$ where the $b_i$ are bounded above by $M$ . Hence, the sequence of partial sums leading up to the series $\sum_{n=1}^\infty\frac1{\prod_{j=1}^n a_j}$ is increasing but must always reside in the interval $(0,\frac32)$ . Hence it must converge. In fact, it must converge to $\frac32$ as any other value would require the $a_i$ to converge to $1$ , contradicting the fact that the $b_i$ are positive. Thus $S=\boxed{\frac32}$ . $\blacksquare$

This post has been edited 1 time. Last edited by smileapple, Feb 19, 2025, 9:42 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

97 posts

NicoN9

#22 h Apr 1, 2025, 3:25 AM

Y by

The answer is $S=3/2$ . Note that $a_n=(b_n+2)/b_{n-1}$ . The idea is to use telescoping. We have $\begin{align*} \sum_{n=1}^\infty \frac{1}{a_1\dots a_n} = 1+\sum_{n=2}^\infty \frac{b_2b_3\dots b_{n-1}}{(b_2+2)\dots (b_n+2)} &= 1+\sum_{n=2}^\infty \frac{b_2b_3\dots b_{n-1}}{2(b_2+2)\dots (b_{n-1}+2)} - \frac{b_2\dots b_n}{2(b_2+2)\dots (b_n+2)}\\ &= 1+\frac{1}{2} \\ &= \frac{3}{2} \end{align*}$ As $(b_j)$ is bounded, we are done.

This post has been edited 1 time. Last edited by NicoN9, Apr 1, 2025, 3:30 AM
Reason: typo

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a