Putnam 2012 B4

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

No tags match your search

M

Putnam 2012 B4

G H J

Reveal topic tags

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 3, 2012, 12:19 AM • 2 Y

Y by Adventure10, Mango247

Suppose that $a_0=1$ and that $a_{n+1}=a_n+e^{-a_n}$ for $n=0,1,2,\dots.$ Does $a_n-\log n$ have a finite limit as $n\to\infty?$ (Here $\log n=\log_en=\ln n.$ )

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 3, 2012, 12:20 AM • 5 Y

Y by Adventure10, Mango247, MS_asdfgzxcvb, and 2 other users

We will show that in fact, $\lim_{n\to\infty}(a_n-\log n)=0.$

A lemma we will use (from Taylor's theorem): there is a positive constant $C$ such that if $0\le x\le 1,$ then $1+x\le e^x\le 1+x+Cx^2.$

Let $b_n=e^{a_n}$ so that $a_n = \log(b_n).$ The recursion becomes $\log(b_{n+1})=\log(b_n)+\frac1{b_n}.$ Exponentiate that to get
$b_{n+1}=b_n\cdot e^{1/b_n}.$
Note that $b_n$ is increasing and clearly $b_n\ge 1$ so that $\frac1{b_n}\le 1.$

By the estimate we gave above:
$\begin{align*}b_n\left(1+\frac1{b_n}\right)&\le b_{n+1}\le b_n\left(1+\frac1{b_n}+\frac{C}{b_n^2}\right)\\ b_n+1&\le b_{n+1}\le b_n+1+\frac{C}{b_n}\\ 1&\le b_{n+1}-b_n\le 1+\frac{C}{b_n}\end{align*}$
The left hand inequality, plus an induction, assures us that $b_n\ge n.$ Then we can write the right hand inequality as $b_{n+1}-b_n\le 1+\frac{C}n.$ Sum this and we get a partial sum of the harmonic series. The known growth rate of the harmonic series tells us that $n\le b_n\le n+\alpha+C\log n$ for some constant $\alpha.$ Take the logarithm of this to get
$\log n\le \log(b_n)\le \log(n+\alpha+ C\log n)=\log n+\log\left(1+\frac{\alpha}n+\frac{C\log n}n\right)$
$0\le a_n-\log n\le \log\left(1+\frac{\alpha}n+\frac{C\log n}n\right)$
Since the right hand side of this tends to zero as $n\to\infty,$ we get that the quantity $(a_n-\log n)$ is squeezed to zero.

Z K Y

The post below has been deleted. Click to close.

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

3311 posts

#3 h Dec 3, 2012, 1:35 AM • 2 Y

Y by Adventure10, Mango247

You have a slight typo. In the first line of the three inequalities, the left most hand side should be $b_n\left(1 + \frac{1}{b_n}\right)$ .

Z K Y

The post below has been deleted. Click to close.

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

2057 posts

#4 h Dec 3, 2012, 1:52 AM • 2 Y

Y by Adventure10, Mango247

I'm not sure how rigorous this is, but I'll post it anyway.

From $a_{n+1} = a_{n} + e^{-a_n}$ , we get that $a_n$ is strictly increasing, and that $e^{a_n}(a_{n+1}-a_n) = 1$ .

Since $e^x$ is strictly increasing, a left endpoint Riemann sum will underestimate the value of an integral, i.e.:
$e^{a_n}-e$ $= \int_{1}^{a_n}e^x\,dx$ $> \sum_{k = 0}^{n-1}e^{a_k}(a_{k+1}-a_k)$ $= \sum_{k = 0}^{n-1} 1 = n$

Thus, $a_n > \log(n+e)$ , and $a_n - \log n > \log(1+\tfrac{e}{n}) \to 0$ as $n \to \infty$ .

Since $e^x$ is strictly increasing, a right endpoint Riemann sum will overestimate the value of an integral, i.e.:
$e^{a_n}-e$ $= \int_{1}^{a_n}e^x\,dx$ $< \sum_{k = 0}^{n-1}e^{a_{k+1}}(a_{k+1}-a_k)$ $= \sum_{k = 0}^{n-1} e^{e^{-a_k}}\cdot e^{a_k}(a_{k+1}-a_k)$ $< \sum_{k = 0}^{n-1} e^{\tfrac{1}{k+e}} = : S_n$

Thus, $a_n < \log(S_n+e)$ , and $a_n - \log n < \log(\tfrac{1}{n}S_n+\tfrac{e}{n})$ .

Since $\lim_{k \to \infty}e^{\tfrac{1}{k+e}} = 1$ , we have $\lim_{n \to \infty}\dfrac{1}{n}S_n = 1$ . Thus, $\log(\tfrac{1}{n}S_n+\tfrac{e}{n}) \to \log(1+0) = 0$ as $n \to \infty$ .

From this, we can conclude that $\lim_{n \to \infty}(a_n - \log n) = 0$ .

EDIT: Dumb question: If the limit was $0$ , as opposed to something that didn't have a closed form, then why did they not bother asking us to find the limit?

Z K Y

The post below has been deleted. Click to close.

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

2043 posts

Zhero

#5 h Dec 3, 2012, 2:58 AM • 2 Y

Y by Adventure10 and 1 other user

We claim the answer is yes. For $n \geq 1$ , let $b_n = a_n - \ln n$ . We wish to show that $\{b_n\}$ converges. Note that we have $b_1 = a_1 > 0$ . Substituting $a_n = b_n + \ln n$ into our recurrence $a_{n+1} = a_n + e^{-a_n}$ gives $b_{n+1} = b_n + \ln(\frac{n}{n+1}) + \frac{e^{-b_n}}{n}$ .

We claim that $b_n \geq 0$ for all $n$ . Note that since $e^x \geq x+1$ for all real $x$ , we have $e^{-b_n} \geq 1 - b_n$ . Additionally, for $x = \frac{1}{n}$ we have $e^{\frac{1}{n}} \geq 1 + \frac{1}{n}$ , which rearranges to $\frac{1}{n} + \ln(\frac{n}{n+1}) \geq 0$ . Thus, $b_{n+1} = b_n + \ln(\frac{n}{n+1}) + \frac{e^{-b_n}}{n} \geq b_n + \ln(\frac{n}{n+1}) + \frac{1-b_n}{n} \geq \frac{1}{n} + \ln(\frac{n}{n+1})+ b_n (1 - \frac{1}{n}) \geq b_n (1 - \frac{1}{n}).$
Since $b_1, b_2 > 0$ , it follows by induction that $b_n > 0$ for all $n$ .

It follows that
$b_{n+1} = b_n + \ln(\frac{n}{n+1}) + \frac{e^{-b_n}}{n} \leq b_n + \frac{1}{n} - \ln(1 + \frac{1}{n+1}) = b_n + \frac{1}{2n^2} - O(\frac{1}{n^3}),$
so there is some positive constant $c$ for which $b_{n+1} \leq b_n + \frac{c}{n^2}$ for all $n$ . It follows that for all $n>1$ and $k>0$ that
$b_{n+k} - b_n = \sum_{i=n}^{n+c-1} (b_{i+1} - b_i) \leq \sum_{i=n}^{n+c-1} \frac{c}{i^2} < \sum_{i=n}^{\infty} \frac{c}{i^2} < c \int_{i=n-1}^{\infty} \frac{1}{i^2} = \frac{c}{n-1}.$

Since $\{b_n\}$ is bounded from below, it has a limit inferior $L$ . Let $\epsilon$ be any positive real number. Then there is some $N$ such that for all $n>N$ , it holds that $b_n > L - \epsilon$ . There also exist arbitrarily large $M$ with $b_M < L + \frac{\epsilon}{2}$ . Take any such $M$ for which $\frac{c}{M-1} < \frac{\epsilon}{2}$ . Then for all $n > \max(M,N)$ , we have $b_n > L - \epsilon$ and $b_n < b_M + (b_n - b_M) < (L + \frac{\epsilon}{2}) + \frac{\epsilon}{2} = L + \epsilon$ , i.e., $|b_n - L| < \epsilon$ . Thus, $\{b_i\}$ converges to $L$ , as desired.

Note: It's not too hard to show from here that we must have $L=0$ . Since $b_i \geq 0$ , $L \geq 0$ , so we suppose for the sake of contradiction that $L>0$ . If we take $\epsilon = \frac{L}{2}$ , then there is some $N$ such that whenever $n>N$ it holds that $b_n > \epsilon$ . Now,
$\begin{align*} b_{n+1} &= b_n + \ln(\frac{n}{n+1}) + \frac{e^{-b_n}}{n} = b_n - \ln(1 + \frac{1}{n}) + \frac{e^{-b_n}}{n} \\ &= b_n - \frac{1}{n} + O(\frac{1}{n^2}) + \frac{e^{-b_n}}{n} = b_n + \frac{e^{-b_n} - 1}{n} + O(\frac{1}{n^2}) \\ &\leq b_n + O(\frac{1}{n^2}) + \frac{e^{-\epsilon} - 1}{n} \end{align*}$
Summing these from $N$ to $N+m$ for some $m$ , we have
$b_{N+m} \leq b_N + O(\frac{1}{N+m}) + (e^{-\epsilon} - 1) \sum_{i=N}^{N+m} \frac{1}{i},$
which is impossible since $e^{-\epsilon} - 1 < 0$ and $\sum_{i=N}^{N+m} \frac{1}{i}$ diverges as $m$ goes to infinity.

Z K Y

The post below has been deleted. Click to close.

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

1 post

Wells

#6 h Dec 3, 2012, 2:06 PM • 4 Y

Y by hnhuongcoi, Adventure10, Mango247, and 1 other user

If $a_n$ was convergent, it would be null, which is absurd. Therefore, $a_n$ is divergent.

Now, notice that $\lim_{n\to\infty}(e^{a_{n+1}}-e^{a_n}) = \lim_{n\to\infty}\frac{e^{e^{-a_n}}-1}{e^{-a_n}}$ .

Using the Heine definition of the limit, it's easy to see that the latter limit is equal to $1$ ; indeed, the sequence $e^{-a_n}$ converges to $0$ and $\lim_{x\to 0}{\frac{e^x-1}{x}} = 1$ .

Now, according to the Stolz–Cesàro theorem, we get that $\lim_{n\to\infty}\frac{e^{a_n}}{n} = 1$ . Thus, $a_n-\log 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

#7 h Dec 3, 2012, 11:18 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Anyway, it looks like including at least one old problem discussed on AoPS to the Putnam test has become a tradition

.

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

#8 h Dec 3, 2012, 11:32 PM • 1 Y

Y by Adventure10

To be technical, asking that $\lim a_n-\log n$ exist is a little more stringent than asking that $\lim\frac{a_n}{\log n}=1.$ But it is the same sequence.

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

#9 h Dec 4, 2012, 12:05 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

And, moreover, most solutions in that thread actually give you the limit of the difference...

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

#10 h Dec 4, 2012, 12:17 AM • 5 Y

Y by J.Y.Choi, Adventure10, Mango247, MS_asdfgzxcvb, and 1 other user

A bit of motivation right from the start: the analogous differential equation is $y'=e^{-y}.$ You can solve that by separation of variables to get $y=\ln(x+C),$ and it's clear that $\lim_{x\to\infty}y-\ln x=0.$ That's not in itself a proof, but it does suggest we're in the right place. The substitution $a_n=\ln(b_n)$ was then partly motivated by that separation of variables.

Z K Y

The post below has been deleted. Click to close.

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

82 posts

soshi

#11 h Dec 4, 2012, 4:52 AM • 2 Y

Y by Adventure10, Mango247

I think I'm missing something but you said to consider the
euler's approximation $y' = e^{-y}$ , but you have to introduce
an $1/n$ , or a step size of sort which $a_{n+1} = a_{n} + e^{-a_{n}}$
doesn't seem to have? Does that come form the $ln(\frac{e^{a_{n}}}{n})$

Z K Y

The post below has been deleted. Click to close.

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

2 posts

#12 h Dec 4, 2012, 5:03 AM • 2 Y

Y by Adventure10, Mango247

I tried to show this was a Cauchy sequence: |(a_(n+1) - log(n+1)) - (a_n - log n) |----> 0 as n goes to infinity. (Sorry for no LaTeX, haven't learned how to use it yet, but kind of interested in an answer to my question so I didn't want to go through the FAQ for an hour...).

So with the triangle inequality I got that the expression above is less than or equal to |e^(-a_n)| + |log(n+1) - logn|. I was able to show that the second absolute value went to 0 as n went to infinity (derivative 1/n ----> 0, so it becomes flatter and flatter, right?), but I couldn't show that the first absolute value went to 0 because I couldn't show that a_n diverges! (I wrote on my exam that I was pretty sure a_n went to infinity so the first absolute value would go to zero. Any idea how much partial credit they would give me on this?)

More importantly, though, how do you show a_n goes to infinity?

Thanks.

Z K Y

The post below has been deleted. Click to close.

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

2142 posts

#13 h Dec 4, 2012, 5:22 AM • 3 Y

Y by ferranti, Adventure10, Mango247

ferranti wrote:

I tried to show this was a Cauchy sequence: |(a_(n+1) - log(n+1)) - (a_n - log n) |----> 0

The Cauchy criterion for $(x_n)_{n=1}^\infty$ converging is that $\lim_{N\to\infty}\sup_{m,n\geq N}|x_m-x_n|=0$ , not that $\lim_{n\to\infty}|x_{n+1}-x_n|=0$ . That the second condition is not sufficient can be seen easily with a simple counterexample (namely, $x_n=\sum_{j=1}^n\frac 1j$ ).

Z K Y

The post below has been deleted. Click to close.

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

2 posts

#14 h Dec 4, 2012, 5:39 AM • 2 Y

Y by Adventure10, Mango247

Well, that's too bad. But thanks for letting me know!

Z K Y

The post below has been deleted. Click to close.

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

2057 posts

#15 h Dec 4, 2012, 5:52 AM • 2 Y

Y by ferranti, Adventure10

ferranti wrote:

More importantly, though, how do you show a_n goes to infinity?

As Yongyi781 pointed out, your approach would not work. However, you can show that $a_n \to \infty$ as follows:
Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

2 posts

#16 h Dec 4, 2012, 7:11 PM • 2 Y

Y by Adventure10, Mango247

Here's what I tried, first I noted that since $a_{n+1} = a_n + e^{-a_n}$ , then you could instead write $a_n$ as a series ${\sum^{n}}_{i=0} b_i$ of the sequence $b_{n+1} = e^{-b_n}$ , with $b_0 = 1$ .

So we then have

$a_n - log(n) = 1 + e^{-1} + {\sum^{n}}_{i=2} b_i - (log(n) - log(n-1))$ .

Then I just used that the sequence $log(n/n-1)$ converges to 0, as $n/(n-1)$ converges to 1. $b_i$ cannot converge to 0 as if it $b_i$ was arbitrarily close to 0 then $b_{i+1}$ would be arbitrarily close to 1, so by the divergence test

$1 + e^{-1} + {\sum^{n}}_{i=2} b_i - (log(n) - log(n-1))$

diverges, so $a_n - log(n)$ is a divergent sequence.

Mind you I got a bit messy while writing this out, so even if this reasoning were correct, I doubt I got the marks. It would also be great if someone told me where I went wrong, as I likely did.

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

#17 h Dec 4, 2012, 7:49 PM • 1 Y

Y by Adventure10

soshi wrote:

I think I'm missing something but you said to consider the
euler's approximation $y' = e^{-y}$ , but you have to introduce
... a step size ...

The step size is $1.$

DizzyCow: In your notation, $b_{n+1}=e^{-a_n},$ not $e^{-b_n}.$

One additional comment: you might ask how fast $a_n-\log n$ tends to zero. That should be apparent from my solution above: it's $O\left(\frac{\log n}n\right),$ which isn't all that fast.

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

#18 h Dec 5, 2012, 5:21 PM • 2 Y

Y by Adventure10, Mango247

Xantos C. Guin wrote:

EDIT: Dumb question: If the limit was $0$ , as opposed to something that didn't have a closed form, then why did they not bother asking us to find the limit?

There's a fairly well-established tradition of misdirection in what Putnam questions claim to be asking for. One classic example from a couple of years back: an $n\times n$ determinant with entries given trigonometrically, and the question was about the limit of the determinant as $n\to\infty.$ So that makes it a calculus/analysis question, and there will be estimates and inequalities and growth rates and epsilons? Well, no - that was misdirection. It was purely a linear algebra (and trig identity) question, and the determinant was exactly zero for all $n\ge 3.$

You do have to take what they tell you with a certain level of skepticism.

Z K Y

The post below has been deleted. Click to close.

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

3083 posts

Ravi B

#19 h Dec 5, 2012, 6:21 PM • 2 Y

Y by Adventure10, Mango247

Also, one solution to the problem is to show that $a_n -\log n$ is a decreasing sequence of positive numbers, which is enough to deduce a limit, without knowing what the limit is. You can find such a solution in the writeup by Kiran Kedlaya and Lenny Ng, currently posted at http://math.ucsd.edu/~kedlaya/2012s.pdf.

Z K Y

The post below has been deleted. Click to close.

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

6 posts

#20 h Dec 6, 2012, 5:19 AM • 2 Y

Y by Adventure10, Mango247

I agree with everyone that the limit is zero, but I'm afraid that the solution I wrote down is probably not rigorous enough. Basically what I wrote down is the following:

consider that lim $a_{n+1}$ = lim $a_n$ + lim $e^{-a_n}$ = lim $a_n$ + 0 as $n\to\infty$ since we can make $a_n$ arbitarily large since it is a sum of its previous terms; this means that lim $a_{n+1}$ = lim $a_n$ = $\infty$ as $n\to\infty$ . Now consider that lim $log n$ = $\infty$ as $n\to\infty$ . It follows that lim $a_n-\log n$ = $\infty$ - $\infty$ = 0 .

Z K Y

The post below has been deleted. Click to close.

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

12096 posts

jmerry

#21 h Dec 6, 2012, 6:33 AM • 3 Y

Y by ericksosam, Adventure10, Mango247

ericksosam wrote:

Basically what I wrote down is the following:

consider that $\lim a_{n+1} = \lim a_n + \lim e^{-a_n} = \lim a_n + 0$ as $n\to\infty$ since we can make $a_n$ arbitrarily large since it is a sum of its previous terms; this means that $\lim a_{n+1} = \lim a_n = \infty$ as $n\to\infty$ . Now consider that $\lim log n = \infty as n\to\infty$ . It follows that $\lim a_n-\log n = \infty - \infty = 0$ .

[Quote inserted due to new page in the thread. Edited for formatting and a typo. By the way, $\LaTeX$ recognizes \lim.]

That is most certainly not a proof, ericksosam. $\infty-\infty$ is what is known as an indeterminate form, in that if $\lim f=\infty$ and $\lim g=\infty$ , $\lim f-g$ can be anything. After all, $\lim_{x\to\infty} 2x-x$ isn't zero.

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

#22 h Dec 6, 2012, 12:00 PM • 2 Y

Y by Adventure10, Mango247

Moreover, even if your knowledge of how to operate infinities was somewhat shaky, you still should be able to recognize that something is fishy by noticing that you have never used that it is $\log n$ and not, say, $e^n$ : your argument remains equally (un)convincing if you use $e^n$ instead of $\log n$ everywhere, and the statement cannot be true for both.

Z K Y

The post below has been deleted. Click to close.

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

6 posts

#23 h Dec 7, 2012, 4:34 AM • 2 Y

Y by Adventure10, Mango247

I see both of your points. Somewhere in my mind I feel that I have seen a problem involving the indeterminate form in calc II when we learned about l'hopitals rule, I just can't remember exactly how the two relate right now.

Z K Y

The post below has been deleted. Click to close.

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

5564 posts

#24 h Dec 8, 2012, 1:02 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

This problem was discussed in my paper "The second term in asymptotic expansion"

I posted here ( in Mar 24, 2011, 12:34 pm)

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=722&t=398470

it is Application3 or see the file.

Attachments:

Asymptotic expansion Article Mathlinks.pdf (35kb)

Z K Y

The post below has been deleted. Click to close.

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

6 posts

#25 h Dec 16, 2012, 4:42 AM • 2 Y

Y by Adventure10, Mango247

I would like everone to dismiss what I said in my previous post on this topic as they were foolish mistakes on my part.

Z K Y

The post below has been deleted. Click to close.

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

1479 posts

#26 h Aug 24, 2013, 7:47 PM • 2 Y

Y by Adventure10, Mango247

$\{a_n\}$ is strictly increasing and $wlog$ we can take $a_n>0$ for all $n>m$ for some $m$ . Now if we would have $a_n\leq log n$ for all $n$ then increasing of $a_n-log n$ gives us result, now it can't be that $a_n>log n \implies a_{n+1}<log (n+1)$ else we would have $(1+\frac{1}{n})^n>e$ , so we can take $a_n\geq log n$ for all $n>n_0$ for some $n_0$ . Now note, taking $\epsilon_0=[e-e^{\frac{1}{\epsilon}}]$ we've if $a_n=log n +\epsilon$ then $a_{n+1}<log (n+1)+\epsilon$ where $\epsilon_0=(1+\frac{1}{n})^n$ . So we get $\{a_n-log n\}$ is decreasing for all $n>N$ for some $N>n_0$ and it's will never be negative again,so it converges to some $L$ and hence limit is finite.

Z K Y

The post below has been deleted. Click to close.

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

371 posts

#27 h Nov 24, 2013, 8:15 AM • 2 Y

Y by Adventure10, Mango247

Let $c_n=a_n-\log n$ . Then, by substituting $a_n$ in the original relationship between $a_n$ and $a_{n+1}$ by $c_n$ , we obtain
$c_{n+1}=c_n + \frac{1}{n} e^{-c_n} -\log \frac{n+1}{n}. \ \cdots (1)$
Step 1. If $c_n > -\log \log 2$ , then $c_{n+1} \le c_n$ .
proof. To satisfy $\frac{1}{n} e^{-c_n} -\log \frac{n+1}{n}\le 0$ , one should have $e^{-c_n}\le \log \left ( 1+\frac{1}{n} \right ) ^n$ , which is equal to $c_n \ge -\log \log \left (1+\frac{1}{n} \right ) ^n$ . But by $\left (1+\frac{1}{n} \right ) ^n >2$ , we obtain
$c_n>-\log \log 2> -\log \log \left ( 1+\frac{1}{n} \right ) ^n.$
Hence $c_n \le c_{n+1}$ .
Step 2. If $c_n<0$ , then $c_n \le c_{n+1}$ .
proof. To satisfy $\frac{1}{n} e^{-c_n} -\log \frac{n+1}{n} \ge 0$ , one should have $e^{-c_n}\ge \log \left (1+\frac{1}{n} \right )^n$ , which is equal to $c_n \le -\log \log \left (1+\frac{1}{n} \right )^n$ . But by $\left (1+\frac{1}{n} \right ) ^n < e$ , we obtain
$c_n <0 < -\log \log \left (1+\frac{1}{n} \right ) ^n.$
Hence $c_n \le c_{n+1}$ .
Step 3. $| c_n | \le M, n=1,2,...$ for some $M>0$ ,. i.e. $c_n$ is a bounded sequence.
proof. At first, we claim that $|c_{n+1} -c_n| \le M'$ for some $M'>0$ . From the original recursive definition of $a_n$ , we have $a_n < a_{n+1}< a_n +1$ because $a_n>0$ for all $n=0,1,2,...$ and then $e^{-a_n}<e^{-a_0}=1$ . Substituting $a_n = c_n +\log n$ to this, we obtain
$c_n +\log n < c_{n+1} +\log (n+1) < c_n + \log n +1,$
which leads
$-\log \left ( 1+\frac{1}{n} \right ) < c_{n+1} -c_n < -\log \left ( 1+\frac{1}{n} \right ) +1$
and then
$|c_{n+1} - c_n | \le \log \left ( 1+\frac{1}{n} \right ) +1 < M'$
for some $M'>0$ since $RHS$ is a bounded sequence. Combining step 1 and 2, we obtain
$-M' \le c_n \le -\log \log 2 +M',$
which means that $c_n$ is a bounded sequence.

Now, let's return to the recurrence relation $(1)$ . Let $p>0$ be an integer. Then by $(1)$ , telescoping sum of the form $c_{k+1} - c_k$ from $k=n$ to $k=n+p-1$ yields
$c_{n+p}-c_n=\frac{1}{n}e^{-c_n} +\frac{1}{n+1} e^{-c_{n+1}} +\cdots +\frac{1}{n+p-1}e^{-c_{n+p-1}}-\log \frac{n+p}{n}.$
I wanted to say that $c_n$ diverges by the boundedness of $c_n$ , divergent of the series $\sum \frac{1}{n}$ and the Cauchy criterion, but I found an error while writing down this post...I don't have any idea with the last $\log$ term.

Z K Y

The post below has been deleted. Click to close.

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

22 posts

#28 h Jun 25, 2014, 5:18 PM • 2 Y

Y by Adventure10, Mango247

sorry, i assumed that $a_1=1$ instead of $a_0=1$ , but that won't change anything...
the sequence $y_n=e^{a_n}/n$ starts from $e$ and satisfies $y_{n+1}=\frac{n}{n+1}y_ne^{\frac{1}{ny_n}}.$ by induction we show easily that $y_n>\frac{1}{n\log(1+1/n)}\,,$ since the function $te^{1/(nt)}$ is increasing in $t$ .
Then it follows immediately that the sequence is decreasing and bounded from below by 1. So it converges to a reasonable constant. Now $a_n-\log(n)$ converges to the log of that constant.

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

#29 h Sep 12, 2015, 10:43 PM • 2 Y

Y by Adventure10, Mango247

Suppose it doesn't converge, and let $b_n:=a_n-\log n$ . Then

$b_{n+1}-b_n=\frac1n(e^{-b_n}-1)+\underbrace{\frac1n-\log(1+\frac1n)}_{this>0}$

If $b_n>0$ , then $b_{n+1}-b_n<0$ ; if $b_n<0$ then $b_{n+1}-b_n>0$ . So $b_n$ is bounded, let $M=\max|b_n|$ . Choose large enough $n$ such that

$b_{n+1}-b_n=\underbrace{\frac1n(e^{-b_n}-1)}_{|this|\le\frac{M}n}+\underbrace{\frac1n-\log(1+\frac1n)}_{0<that<\epsilon}$

for some $\epsilon>0$ , so that $|b_{n+1}-b_n|<\frac{|M|}n+\epsilon<\epsilon'$ .

This post has been edited 1 time. Last edited by codyj, Sep 12, 2015, 10:58 PM
Reason: took the absolute value of a positive number, makes me look tarded

Z K Y

The post below has been deleted. Click to close.

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

109 posts

#30 h Oct 24, 2017, 10:40 PM • 2 Y

Y by Adventure10, Mango247

Michael Penn solved this using Stolz-Cesaro: https://www.youtube.com/watch?v=Dc3LXFiXcmY

This post has been edited 2 times. Last edited by Popescu, Oct 3, 2023, 10:13 PM
Reason: Wrong

Z K Y

The post below has been deleted. Click to close.

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

118 posts

#31 h Mar 24, 2025, 6:34 AM

Y by

Moreover we shall see that $\left(a_n-\log n \right)_{n\ge 1}\to 0$ .
As $\Delta a_n=e^{-a_n}$ , computing the limit of $\left(a_n-\log n\right)_{n\ge 1}$ is same as computing the limit of $\left(\log(\Delta a_n \times n)\right)_{n\ge 1}$ . Our primary goal is to find an appropriate upper bound for $\Delta a_n$ and we shall see that this can be achieved by evaluating the Riemann lower sum of the function $e^x$ in the interval $[1, a_n]$ (idea borrowed from @Xanthos C. Guin). But you may ask what does finding an upper bound to $\Delta a_n$ have anything to do with finding some random Riemann lower sum? remember : $e^{a_n}\Delta a_n=1$ . Consider the partition $P_n=\{a_0, a_1,\ldots, a_{n-1}\}$ and as $e^x$ is strictly increasing we know $\inf_{a_{i}\le x\le a_{i+1}}(e^x)=e^{a_i}$ for each $i=0,1,\ldots, n-1$ then,
$e^{a_n}-e=\int_{1}^{a_n}e^x\ge \sum_{0\le i\le n-1}e^{a_i}\Delta a_{i}=n.$ It is not hard to see that $\Delta a_n=e^{-a_n}\le\frac{1}{n+e}$ and we then have,
$\left\lvert\log(\Delta a_n\times n) \right\lvert\le \underbrace{\left\lvert\log\frac{n}{n+e}\right\lvert.}_{\text{can be made arbitrarily small}}$ Our claim then follows from the very definition of convergence and we are done. $\square$

This post has been edited 1 time. Last edited by anudeep, Mar 24, 2025, 6:49 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a