$\frac{a_n - a_{n+1}}{a_n} \approx \frac{1}{n}$? (part of 2010 Putnam exam)

Given a non-negative sequence $a_n$, strictly decreasing and tending to zero, can we show that (for large $n$)

$$\frac{a_n - a_{n+1}}{a_n} \approx \frac{a_n}{na_n} = \frac{1}{n} \text{ }?$$

Obviously, we are inspired to attempt this by noticing that $a_n - a_{n+1} \to l \implies \frac{a_n}{n} \to l$, since the latter is (roughly) the Cesaro mean of the former (i.e., the Cesaro mean of the sequence $b_n = a_n - a_{n+1}$). If we had $l \neq 0$, then we could just note that the quotient of these two sequences would head towards 1, which would quickly give the result. However, I can't think of a way to handle this for the case where the sequence $a_n$ tends to zero.

Examples ($\frac{1}{n}, \frac{1}{\sqrt{n}}, \frac{\log(n)}{n},$ etc.) suggest that the claim is true.

• So your question is: for every non-negative decreasing sequence $(a_n)$, $(a_n-a_{n+1})/a_n\sim \frac{1}{n}$? – Hanul Jeon Nov 3 '14 at 5:13
• There is a counterexample which converges to 0 much slower: consider $a_n=1/\ln(2+n)$. – Hanul Jeon Nov 3 '14 at 5:14
• @HanulJeon you're right! There are many counterexamples to the claim. – user98186 Feb 12 '16 at 16:28

Try something that converges faster, like $a_n = 2^{-n}$.

Or more generally, for any $f$ with $0 < f(n) < 1$ and $c > 0$, you can define a sequence satisfying your conditions by

$$a_0 = c \qquad \qquad a_{n+1} = a_n (1 - f(n))$$

that has

$$\frac{a_n - a_{n+1}}{a_n} = f(n)$$

• Arrrgh. I don't know how I missed that. (Although I had a bad feeling about this plan from the beginning....) – Chris Nov 3 '14 at 5:17
• Hurkyl, would you do me a favor and delete your answer, so I can delete this betise myself? – Chris Nov 3 '14 at 5:21