# Using Limit method with Big Oh Notation

I'm working on a homework assignment right now and I've hit a snag. We've been given a true statement and a fake proof: The professor wants us to rewrite the proof and say what the limit method actually proves, but I'm confused about why this proof is actually invalid?

Obviously this proof is easy enough to solve on it's own, since it evaluates to cn$^k$ $\in$ cn$^k$$^+$$^1$. But I don't quite understand why this limit method is failing. The limit evaluates to 0, and I think all the calculus is correct.

Any help would be very appreciated!

• What is limit of $\frac 1 n +\frac 1 n+...+\frac 1 n$ where there are n terms each of which is $\frac 1 n$? If you take the limit of each term you get $0+0+...+0$. But that can't be right because $\frac 1 n +\frac 1 n+...+\frac 1 n=1$ for each n. You can take limit for each term and add them up when the number of terms is fixed, not when the number of terms itself tends to $\infty$. – Kavi Rama Murthy Mar 12 '18 at 5:30
• @KaviRamaMurthy So the issue is when they get split up? But wouldn't the limit of them all together still be 0? – Matthew Kerian Mar 12 '18 at 5:33
• "But wouldn't the limit of them all together still be 0?" For a fixed number of them, yes, but not for a number of terms depending on $n$. For every fixed $p$, $$\lim_{n\to\infty}\frac{1^k+2^k+\cdots+p^k}{n^{k+1}}=\lim_{n\to\infty}\frac{1^k}{n^{k+1}}+\lim_{n\to\infty}\frac{2^k}{n^{k+1}}+\cdots+\lim_{n\to\infty}\frac{p^k}{n^{k+1}}=0$$ is perfectly legit, stemming recursively from $$\lim_{n\to\infty}(x_n+y_n)=\lim_{n\to\infty}x_n+\lim_{n\to\infty}y_n$$ when the two limits on the RHS exist. – Did Mar 12 '18 at 7:09
• The line above "$=0+0+...+0$" has $n$ terms but $n$ is not constant. Suppose $k=1.$ Then $f(n)=(n^2+n)/2$ and $g(n)=n^2$ and $f(n)/g(n)\to 1/2$ as $n\to \infty.$ – DanielWainfleet Mar 13 '18 at 1:20

(1). It is not generally true that $\lim_{n\to \infty} \sum_{i=1}^n A(i,n)=\sum_{i=1}^{\infty}\lim_{n\to \infty}A(i,n).$ This is the logical error in the "fake proof".
A simple example is to let $A(n,n)=1$ and to let $A(i,n)=0$ when $i\ne n.$ Then $\sum_{i=1}^nA(i,n)=1$ for each $n$ but $\lim_{n\to \infty}A(i,n)=0$ for each $i.$
(2). For $k\geq 0$ and $m\in \Bbb N$ we have $$\int_{m-1}^mx^kdx \leq\int_{m-1}^mm^kdx =$$ $$=m^k=$$ $$= \int_m^{m+1}m^kdx\leq \int_m^{m+1}x^kdx .$$ Adding from $m=1$ to $m=n,$ we have $$\frac {n^{k+1}}{k+1}=\int_0^nx^kdx\leq$$ $$\leq \sum_{m=1}^n m^k\leq$$ $$\leq \int_1^{n+1} x^kdx=\frac {(n+1)^{k+1}-1}{k+1}.$$ From this we readily obtain $\lim_{n\to \infty}\frac {f(n)}{g(n)}=\frac {1}{k+1}.$
• We can also obtain the limit $1/(k+1)$ for $k\in \Bbb N$ by elementary means (no calculus, just basic algebra)) using a "tricky" but commonly-used technique. – DanielWainfleet Mar 14 '18 at 7:57