[College Calc 01-02. Limits of Sequences] #08

This sequence has its own name: The Lazy Caterer's Sequence .

Suppose we have cut the disk $2$ times, yielding $L_2 = 4$ pieces, and we want to make another cut so that the number of pieces is maximal. When a cut passes through a piece, the piece is split into two, effectively increasing the number of pieces by $1,$ as illustrated below.

That means, we want to maximize the number of pieces the cut passes through. But can a cut pass through every piece? No. When a cut "moves on" to another piece, it has to pass a line. (Otherwise the piece would be the same one as the previous one.) Note that, however, a cut can only meet at most once with each of the other cuts. In this case, there are two lines present, so that the additional cut may pass through at most $3$ pieces, such that $L_3 \leq L_2 + 3 = 7.$ More generally, $L_{n+1} \leq L_n + n+1.$

---

However for us to say that $L_{n+1} = L_n + n + 1,$ we must also prove that such a cut -- meeting with all of the previous cuts inside the circle -- is attainable. Trying to prove that in a fixed circle is difficult, but we can prove it in a different way by thinking in reverse.

Imagine we have made $n$ cuts such that the number of pieces is maximized. We note that increasing the size of the circle, with its center fixed, will not influence the number of pieces. (If it increased the number of pieces, then that would be a contradiction, because the cuts are supposed to be maximal.) We can easily draw a line, not parallel to any of them, and also avoiding their intersections. This way, the line has met all of the $n$ lines. Now we increase the size of the circle, with its center fixed, such that all of the intersections are in its interior. Then, we indeed have a cut that meets with all of the previous $n$ cuts inside the circle.

---

We now have the recurrence relation

$L_{n+1} = L_n + n + 1,$

such that adding these $n-1$ equations --

$\begin{aligned} L_2 &= L_1 &+ 2 \\ L_3 &= L_2 &+ 3 \\ L_4 &= L_3 &+ 4 \\ \vdots & \\ L_n &= L_{n-1} &+ n \end{aligned}$

-- would yield

$L_n = L_1 + \sum_{k=2}^{n} k = 2 + \frac{n(n+1)}{2} - 1 = \frac{1}{2}n^2 + \frac{1}{2}n + 1.$

Then, finding the limit is not too difficult. In order for

$\lim_{n\to\infty} (\sqrt{L_n} - pn)$

to converge, we must have $p=\sqrt{\dfrac{1}{2}} = \dfrac{\sqrt{2}}{2}.$ Referring to the solution of this problem we easily find that

$\lim_{n\to\infty} \left(\sqrt{\frac{1}{2}n^2+\frac{1}{2}n+1} - \sqrt{\frac{1}{2}n^2}\right) = \frac{\frac{1}{2}}{2\sqrt{\frac{1}{2}}} = \frac{\sqrt{2}}{4}.$

Thus, $p+q = \dfrac{\sqrt{2}}{2} + \dfrac{\sqrt{2}}{4} = \boxed{\dfrac{3\sqrt{2}}{4}}.$

We note that $L_0 = 1$ , $L_1 = 2$ , $L_2 = 4$ , $L_3 = 7$ , ... The terms are related as follows:

$\begin{aligned} L_{k+1} & = L_k + k+1 & \small \blue{\text{For }k \ge 0} \\ \sum_{k=0}^n L_{k+1} & = \sum_{k=0}^n L_k + \sum_{k=0}^n k + \sum_{k=0}^n 1 \\ L_{n+1} + \sum_{k=0}^n L_k - \blue{L_0} & = \sum_{k=0}^n L_k + \frac {n(n+1)}2 + n + 1 & \small \blue{\text{Note that }L_0 = 1} \\ L_{n+1} & = \frac {n(n+1)}2 + n + 2 & \small \blue{\text{Replace }n+1 \text{ with }n.} \\ \implies L_n &＝\frac {(n-1)n}2 + n + 1 = \frac {n^2 + n + 2}2 \end{aligned}$

Then we have:

$\begin{aligned} q & = \lim_{n \to \infty} \left(\sqrt{L_n} - pn \right) \\ & = \lim_{n \to \infty} \left(\sqrt{\frac {n^2+n+2}2} - pn \right) & \small \blue{\text{Multiply up and down by }\sqrt{\frac {n^2+n+2}2} + pn} \\ & = \lim_{n \to \infty} \frac {\frac {n^2+n+2}2 - \blue {p^2}n^2}{\sqrt{\frac {n^2+n+2}2} + pn} & \small \blue{\text{For the limit }q \text{ to exist, }p = \frac 1{\sqrt 2}.} \\ & = \lim_{n \to \infty} \frac {\frac {n^2+n+2}2 - \frac {n^2}\blue 2}{\sqrt{\frac {n^2+n+2}2} + \frac n{\sqrt 2}} \\ & = \lim_{n \to \infty} \frac {\frac {n+2}2}{\sqrt{\frac {n^2+n+2}2} + \frac n{\sqrt 2}} & \small \blue{\text{Divide up and down by }n.} \\ & = \lim_{n \to \infty} \frac {\frac 12 + \frac 1n}{\sqrt{\frac 12 + \frac 1{2n} + \frac 1{n^2}} + \frac 1{\sqrt 2}} \\ & = \frac 1{2\sqrt 2} \end{aligned}$

Therefore $p+q = \dfrac 1{\sqrt 2} + \dfrac 1{2\sqrt 2} = \dfrac 3{2\sqrt 2} = \boxed{\frac {3\sqrt 2}4}$ .