# Interesting Taxicab Problem?

I came up with this problem after discussion of taxicab geometry in math class... I thought it was a simple problem, but still pretty neat; however, I am as of yet unsure of whether my answer is correct, or logical.

Let $[X]$ be the area of region $X$, and region $S_n$ be represented by the equation $|x-n|+|y-n|=k-n$ for all $n=0,1,2,\ldots,k-1$. Now let region $R_n$ be the region between $S_n$ and $S_{n+1}$ and $L=\displaystyle\sum_{n=0}^{k-2}{[R_n]}$. Find the smallest positive integer $k$ such that $L > A$. ($A$ is any number you can plug in)

Can anyone else verify my result of $L=\frac{5k^2-k-4}{2}$?

-
If you want to be as general as possible, you should generalize to arbitrary dimension! –  Qiaochu Yuan Aug 28 '10 at 23:27
That's a very good point. However, I'm not yet good enough at 3D to even generalize to volume... and I'm not even going to bother with higher dimensions! –  Eugene Bulkin Aug 28 '10 at 23:54
Is $R_n$ the region inside $S_n$ and outside $S_{n+1}$ or vice versa or something else? –  Isaac Aug 29 '10 at 19:48
inside $S_n$ and outside $S_{n+1}$, yes. –  Eugene Bulkin Aug 29 '10 at 20:08

Each region $S_n$ is a square with sides of slope $\pm 1$, center at $(n,n)$, and side length $\sqrt{2}(k-n)$. Each pair of successive squares is positioned such that $S_{n+1}$ mostly overlaps $S_n$, but not quite. As the top and right vertices of every square are, respectively, on the same horizontal and vertical line and 1 unit apart (the centers of successive squares are shifted 1 unit up and 1 unit to the right), the rectangular region of $S_{n+1}$ that is not inside $S_n$ sticks out by $\frac{1}{\sqrt{2}}$ and has length equal to the side length of $S_{n+1}$, which is $\sqrt{2}(k-(n+1))$, so this rectangular region has area $k-n-1$. Thus, \begin{align} [R_n]&=(\text{area of }S_n)-(\text{area of }S_{n+1})+(\text{area of rectangular region}) \\ &=2(k-n)^2-2(k-n-1)^2+k-n-1 \\ &=5k-5n-3. \end{align} Now,
\begin{align} \sum_{n=0}^{k-2}[R_n]&=\sum_{n=0}^{k-2}(5k-5n-3) \\ &=5k\sum_{n=0}^{k-2}1-5\sum_{n=0}^{k-2}n-3\sum_{n=0}^{k-2}1 \\ &=5k(k-1)-5\left(\frac{(k-2)(k-1)}{2}\right)-3(k-1) \\ &=\frac{10k^2-10k-5k^2+15k-10-6k+6}{2} \\ &=\frac{5k^2-k-4}{2}. \end{align}