How to evaluate this limit?

Calculus Level 3

lim ⁡ n → ∞ ∑ k = 1 n k 2 + k n 3 + k \lim_{n\to\infty}\sum_{k=1}^{n}\dfrac{k^2+k}{n^3+k}

If the above limit results as p q \dfrac{p}{q} , where p p and q q are positive coprime integers, what is the value of p + q ? p+q?


The answer is 4.

Utkarsh Verma by Utkarsh Verma , 20, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Brian Moehring
Aug 24, 2018

We can compare the two sums J n = ∑ k = 1 n k 2 + k n 3 + k , I n = ∑ k = 1 n k 2 n 3 J_n = \sum_{k=1}^n \frac{k^2+k}{n^3+k},\qquad I_n = \sum_{k=1}^n \frac{k^2}{n^3} as ∣ J n − I n ∣ = ∣ ∑ k = 1 n ( k 2 + k n 3 + k − k 2 n 3 ) ∣ = ∑ k = 1 n k ( n 3 − k 2 ) n 3 ( n 3 + k ) ≤ n ⋅ max ⁡ 1 ≤ k ≤ n k ( n 3 − k 2 ) n 3 ( n 3 + k ) ≤ n ⋅ n ( n 3 − 0 ) n 3 ( n 3 + 0 ) = 1 n → n → ∞ 0 \begin{aligned} |J_n - I_n| &= \left|\sum_{k=1}^n \left(\frac{k^2+k}{n^3+k} - \frac{k^2}{n^3}\right)\right| \\ &= \sum_{k=1}^n \frac{k(n^3-k^2)}{n^3(n^3+k)} \\ &\leq n\cdot \max_{1\leq k\leq n} \frac{k(n^3-k^2)}{n^3(n^3+k)} \\ &\leq n\cdot \frac{n(n^3-0)}{n^3(n^3+0)} \\ &= \frac{1}{n} \xrightarrow{n\to\infty} 0 \end{aligned}

This allows us to conclude lim ⁡ n → ∞ ∑ k = 1 n k 2 + k n 3 + k = lim ⁡ n → ∞ J n = lim ⁡ n → ∞ I n = lim ⁡ n → ∞ ∑ k = 1 n ( k n ) 2 ⋅ 1 n = ∫ 0 1 x 2 d x = 1 3 x 3 ∣ 0 1 = 1 3 \begin{aligned} \lim_{n\to\infty} \sum_{k=1}^n \frac{k^2+k}{n^3+k} &= \lim_{n\to\infty} J_n \\ &= \lim_{n\to\infty} I_n \\ &= \lim_{n\to\infty} \sum_{k=1}^n \left(\frac{k}{n}\right)^2 \cdot \frac{1}{n} \\ &= \int_0^1 x^2 \,dx \\ &= \left.\frac{1}{3}x^3\right|_0^1 \\ &= \frac{1}{3} \end{aligned}

and therefore p + q = 1 + 3 = 4 p+q = 1+3 = \boxed{4}

9 Helpful 0 Interesting 0 Brilliant 0 Confused

Can I take n^3 as the common factor in the denominator in the first step and make k/n^3 = 0 ?? It makes the solution simpler but I don't know whether it is correct.

Vishal Krishna - 2 years, 9 months ago
Mathis Pasquier
Aug 29, 2018

Let us write S n = ∑ k = 1 n k 2 + k n 3 + k . S_n = \sum_{k=1}^{n} \frac{k^2+k}{n^3+k}. We can write this partial sum as a unique fraction instead of a sum of fractions, by changing their denominators : S n = 1 2 + 1 n 3 + 1 + ⋯ + n 2 + n n 3 + n = 1 ∏ i = 1 n ( n 3 + i ) × ∑ k = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) \begin{aligned} S_n &= \frac{1^2+1}{n^3+1} + \dots + \frac{n^2+n}{n^3+n}\\ &= \frac{1}{\prod_{i=1}^{n}(n^3+i)}\times \sum_{k=1}^{n} \left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right) \end{aligned} Asymptotically, as n → ∞ n \to \infty we can say that we have 1 ∏ i = 1 n ( n 3 + i ) ∼ n − 3 n \frac{1}{\prod_{i=1}^{n}(n^3+i)} \sim n^{-3n} and ∑ k = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) ∼ ∑ k = 1 n ( k 2 + k ) n 3 ( n − 1 ) . \sum_{k=1}^{n} \left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right) \sim \sum_{k=1}^{n} (k^2+k)n^{3(n-1)}. Since ∑ k = 1 n ( k 2 + k ) = ∑ k = 1 n k 2 + ∑ k = 1 n k = n ( n + 1 ) ( 2 n + 1 ) 6 + n ( n + 1 ) 2 = 2 n 3 + 6 n 2 + 4 n 6 ∼ 2 6 n 3 \begin{aligned} \sum_{k=1}^{n} (k^2+k) &= \sum_{k=1}^{n} k^2 + \sum_{k=1}^{n} k \\ &= \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}\\ &= \frac{2n^3+6n^2 +4n}{6}\\ &\sim \frac{2}{6}n^3 \end{aligned} we can now rewrite S n ∼ n − 3 n 1 3 n 3 n 3 n − 3 ∼ 1 3 . \begin{aligned} S_n &\sim n^{-3n}\frac{1}{3}n^3n^{3n-3}\\ &\sim \frac{1}{3}. \end{aligned} Hence the result: ∑ k = 1 n k 2 + k n 3 + k → n → ∞ p q where p = 1 , q = 3 \sum_{k=1}^{n} \frac{k^2+k}{n^3+k} \xrightarrow[n \to \infty]{} \frac{p}{q} \quad \text{where} \quad p = 1, q = 3 which leads to p + q = 4. p+q = 4.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Can you explain your reasoning for the following?

1 ∏ i = 1 n ( n 3 + i ) ∼ n − 3 n \frac{1}{\prod_{i=1}^{n}(n^3+i)} \sim n^{-3n}

∑ k = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) ∼ ∑ k = 1 n ( k 2 + k ) n 3 ( n − 1 ) \sum_{k=1}^{n} \left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right) \sim \sum_{k=1}^{n} (k^2+k)n^{3(n-1)}

Brian Moehring - 2 years, 9 months ago

Log in to reply

Yes, excuse me, it is true that it is not so clear. I must say that I did this somehow "mechanically", since it sounded right to me. Here is how I would try to explain that.

For the first one, since all the terms in the product are positive numbers, we have ∏ i = 1 n ( n 3 + i ) ≤ ∏ i = 1 n ( n 3 + n ) ≤ ( n 3 + n ) n ≤ n 3 n ( 1 + 1 n 2 ) n \begin{aligned} \prod_{i=1}^{n} (n^3+i) &\leq \prod_{i=1}^{n} (n^3+n)\\ &\leq (n^3+n)^n\\ &\leq n^{3n}\left(1+\frac{1}{n^2}\right)^n \end{aligned} and, similarly, ∏ i = 1 n ( n 3 + i ) ≥ ∏ i = 1 n ( n 3 + 0 ) ≥ n 3 n . \begin{aligned} \prod_{i=1}^{n} (n^3+i) &\geq \prod_{i=1}^{n} (n^3+0)\\ &\geq n^{3n}. \end{aligned}

Therefore, we have 1 ≤ ∏ i = 1 n ( n 3 + i ) n 3 n ≤ ( 1 + 1 n 2 ) n . 1\leq \frac{\prod_{i=1}^{n} (n^3+i)}{n^{3n}}\leq \left(1+\frac{1}{n^2}\right)^n.

Thanks to Taylor expansions, ( 1 + 1 n 2 ) n = exp ⁡ ( n ln ⁡ ( 1 + 1 n 2 ) ) = n → ∞ exp ⁡ ( n ( 1 n 2 + o ( 1 n 2 ) ) ) = n → ∞ 1 + 1 n + o ( 1 n ) \begin{aligned} \left(1+\frac{1}{n^2}\right)^n &= \exp\left(n\ln \left(1+\frac{1}{n^2}\right)\right)\\ &\underset{n\to \infty}{=} \exp\left(n\left(\frac{1}{n^2} + o\left(\frac{1}{n^2}\right)\right)\right)\\ &\underset{n\to \infty}{=} 1 + \frac{1}{n} + o\left(\frac{1}{n}\right)\\ \end{aligned} which shows that ( 1 + 1 n 2 ) n → n → ∞ 1 \left(1+\frac{1}{n^2}\right)^n \xrightarrow[n\to \infty]{} 1 and allows us to conclude that ∏ i = 1 n ( n 3 + i ) n 3 n → n → ∞ 1. \frac{\prod_{i=1}^{n} (n^3+i)}{n^{3n}} \xrightarrow[n\to \infty]{} 1.

For the second one, the process is quite the same : ∑ i = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) ∑ i = 1 n ( k 2 + k ) n 3 ( n − 1 ) = 1 ∑ i = 1 n ( k 2 + k ) × ∑ i = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) n 3 ( n − 1 ) = 1 ∑ i = 1 n ( k 2 + k ) × ∑ i = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) n 3 ( n − 1 ) ) \begin{aligned} \frac{\sum_{i=1}^{n}\left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right)}{\sum_{i=1}^{n}(k^2+k)n^{3(n-1)}} &= \frac{1}{\sum_{i=1}^{n}(k^2+k)}\times \frac{\sum_{i=1}^{n}\left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right)}{n^{3(n-1)}}\\ &= \frac{1}{\sum_{i=1}^{n}(k^2+k)}\times \sum_{i=1}^{n}\left((k^2+k)\times \frac{\prod_{i\neq k}^{}(n^3+i)}{n^{3(n-1)}}\right) \end{aligned} and for the same reason as for the very first equation of this message, we have ∑ i = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) ∑ i = 1 n ( k 2 + k ) n 3 ( n − 1 ) ≤ 1 ∑ i = 1 n ( k 2 + k ) × ∑ i = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + n ) n 3 ( n − 1 ) ) ≤ 1 ∑ i = 1 n ( k 2 + k ) × ( ∑ i = 1 n ( k 2 + k ) ) × ( n 3 + n ) n − 1 n 3 ( n − 1 ) ≤ ( n 3 + n ) n − 1 n 3 ( n − 1 ) \begin{aligned} \frac{\sum_{i=1}^{n}\left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right)}{\sum_{i=1}^{n}(k^2+k)n^{3(n-1)}} &\leq \frac{1}{\sum_{i=1}^{n}(k^2+k)}\times \sum_{i=1}^{n}\left((k^2+k)\times \frac{\prod_{i\neq k}^{}(n^3+n)}{n^{3(n-1)}}\right)\\ &\leq \frac{1}{\sum_{i=1}^{n}(k^2+k)}\times \left(\sum_{i=1}^{n}(k^2+k)\right)\times \frac{(n^3+n)^{n-1}}{n^{3(n-1)}}\\ &\leq \frac{(n^3+n)^{n-1}}{n^{3(n-1)}} \end{aligned} hence 1 ≤ ∑ i = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) ∑ i = 1 n ( k 2 + k ) n 3 ( n − 1 ) ≤ ( 1 + 1 n 2 ) n − 1 . 1\leq \frac{\sum_{i=1}^{n}\left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right)}{\sum_{i=1}^{n}(k^2+k)n^{3(n-1)}} \leq \left(1+\frac{1}{n^2}\right)^{n-1}. which leads to the conclusion ∑ i = 1 n ( ( k 2 + k ) × ∏ i ≠ k ( n 3 + i ) ) ∑ i = 1 n ( k 2 + k ) n 3 ( n − 1 ) → n → ∞ 1. \frac{\sum_{i=1}^{n}\left((k^2+k)\times \prod_{i\neq k}^{}(n^3+i)\right)}{\sum_{i=1}^{n}(k^2+k)n^{3(n-1)}} \xrightarrow[n \to \infty]{} 1.

It is still possible that I made a mistake somewhere, of course, but I tried to be as clear as possible.

Mathis Pasquier - 2 years, 9 months ago

Log in to reply

It looks good to me. The only reason why I asked was that your first solution was dangerously close to suggesting something like ( ∀ k , a k , n ∼ b k , n ) ⟹ ∏ k = 1 n a k , n ∼ ∏ k = 1 n b k , n ∑ k = 1 n a k , n ∼ ∑ k = 1 n b k , n (\forall k, a_{k,n} \sim b_{k,n}) \implies \begin{array}{c} \prod_{k=1}^n a_{k,n} \sim \prod_{k=1}^n b_{k,n} \\ \sum_{k=1}^n a_{k,n} \sim \sum_{k=1}^n b_{k,n}\end{array} which of course isn't true in general--it needs some more assumptions on the trangular arrays a k , n , b k , n a_{k,n}, b_{k,n} in order to be true.

I still like my solution more ;-), but I can vote yours up now.

Brian Moehring - 2 years, 9 months ago

Log in to reply

@Brian Moehring – I see ! I must say that your solution is shorter and lighter. But mine shows a different path leading to the solution, which is why I posted it ;) Having that said, it was a good way for me to dig deeper in a proof. Thank you ! P.S. : could you tell me more about the required assumptions you mention ?

Mathis Pasquier - 2 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...