# Proving that the the sequence $x_n = \frac{n^{100}}{2^n}$ converges using only elementary methods

I realise that there are already questions on the site about this sequence or related sequences, but I'm looking for a completely elementary method that doesn't use:

• L'Hopital's Rule
• Tests like the comparison test or ratio test
• Logarithms
• Statements like "exponentials grow faster than polynomials"

I'm trying to show that the sequence $$x_n = \frac{n^{100}}{2^n}$$ converges as $$n \to \infty$$, where $$n$$ is a positive integer. I haven't been able to find a way to do this directly using the epsilon definition for convergence. Is there a completely elementary way to show that this converges (not necessarily needing to show what it converges to) without using any of the things mentioned above?

• I don't think there is a proof without using mathematics, or brains. – user436658 Nov 21 '20 at 16:36
• @ProfessorVector I completely agree! I really do not at all understand people's obsession with "solve ___ without using ___", especially when it comes to limits without using L'Hospitals rule. The whole reason why these more advanced and powerful techniques exist is so that we don't have to use cumbersome $\epsilon, \delta$ methods. – K.defaoite Nov 21 '20 at 17:34
• @K.defaoite In that case, then what are your thoughts on students being asked to do exercises without using results that they haven't proved yet? – Integral12 Nov 21 '20 at 18:01
• In that case, you'd better add that motivation to your question, together with a list of results those students have proved, so far. Excluding logarithms while reasoning about limits makes that quite a bit... erm... dubious, though. I mean, logarithms were introduced not later than 1614, while the concept of "limit" seems to be newer. – user436658 Nov 21 '20 at 18:52

I think this is the most elementary we can get. Look at the ratio between two consecutive terms: $$\frac{x_{n+1}}{x_n}=\frac{(n+1)^{100}/2^{n+1}}{n^{100}/2^n}\\ =\frac{(n+1)^{100}}{2n^{100}}\\ =\frac12\left(1+\frac1n\right)^{100}$$ Now note that from some point on, $$1+\frac1n<\sqrt[100]2$$. This means that from that point on, we get $$\frac{x_{n+1}}{x_n}<1$$, which means that the sequence is monotonically decreasing. At the same time, it is trivial that $$x_n>0$$ for all $$n$$. Thus $$x_n$$ must converge.

• That's what the OP calls "ratio test". Too hard. – user436658 Nov 21 '20 at 16:44
• @ProfessorVector You sure? Because that's not what I call "ratio test". That would be testing the ratio between $x_{n+1}-x_n$ and $x_{n}-x_{n-1}$. – Arthur Nov 21 '20 at 16:46
• I'm not sure. But given that the ratio test is meant not for sequences, but for series, it's my best guess what the OP thinks it means. – user436658 Nov 21 '20 at 16:50

Let $$h=\sqrt[200]2-1$$ and note that $$h>0$$. Then using Bernoulli's inequality $$2^n=(2^{n/200})^{200}=((1+h)^n)^{200}\ge (1+hn)^{200}>h^{200}n^{200}$$ so that $$0<\frac{n^{100}}{2^n}<\frac{1}{h^{200}n^{100}}<\epsilon$$ as soon as $$n>{\frac1{h^2\sqrt[100]\epsilon}}$$.

• Isn't Bernoulli's inequality equivalent to "exponentials grow faster than polynomials"? – Infinity_hunter Nov 21 '20 at 17:03
• @Infinity_hunter It is the statement that one certain linear polynomial grows slower than one particular exponential function. So it's not quite that general. At least on the face of it. – Arthur Nov 21 '20 at 17:11

$$\frac{n^{100}}{2^n} =2^{100} \frac{n^{100}}{2^{n+100}}$$ Now $$2^{n+100}> \binom{n+100}{101} = \frac{(n+100)(n+99) \cdots (n+1)n}{101 !}> \frac{n^{101}}{101!}$$

Therefore $$\frac{n^{100}}{2^n} < 2^{100}\cdot 101! \cdot \frac{1}{n}$$

• $\sum \frac1n = \infty$ – Dark Malthorp Nov 21 '20 at 17:36
• it doesn't help prove convergence of the series. – Dark Malthorp Nov 23 '20 at 15:15

As an elementary method, note that for $$n>10$$, we have $$n+1< 1.1n$$ hence the numerator of $$x_n$$ increases at a rate of at most $$1.1$$ and the denominator increases at a rate of exactly $$2$$, a sufficient condition for $$x_n\to0$$.