Total number of triangles in a triangular grid

Question

I once tried to find how to quickly find the total number of squares in a bigger, $n\times n$ grid. I’m sure you’ve seen one of these puzzles, and the bigger the grid, the more embedded squares there are and the more chance you have of miscounting. So I finally came up with the answer $$ \sum^n_{k=1}k^2$$ which can be simplified to $$\frac{n(n+1)(2n+1)}{6}$$ Then later on, I wanted to try the same with a triangular (equilateral) grid, where the size $n$ corresponds to the side of the triangle.

So I eventually found a formula that has two summation terms, one inside the other, with some even/odd evaluator ($n$ is the size of a side): $$T(n)=\sum^n_{k=1}\bigg(\frac{3-(-1)^{n-k}}{2}\sum^k_{j=1}j\bigg)$$ The fraction in between the two sums is the even/odd evaluator, and determines if $n-k$ is even or odd. Now this looks long and tedious, and for large grid sizes, only a computer could do it without a chance of mistaking. Now for the important part, my question is this: Is there a way to simplify the formula in a similar way than the square grid one? Yes, I did try Wolfram Alpha, and it just gave me back the summation form of the formula.

Answer 1

Firstly, note that $$-(-1)^{n-k} =(-1)^{n+k+1}. \tag{1}$$ This is true because $$-(-1)^{n-k} =-(-1)^n (-1)^{-k} =-\frac{(-1)^n}{(-1)^k} \color{blue}{\cdot \frac{(-1)^k}{(-1)^k}} =-(-1)^{n+k} =(-1)^{n+k+1}.$$ Plug $(1)$ into $T(n)$ and expand: $$\begin{align} T(n) &= \sum^n_{k=1} \left( \frac{3+(-1)^{n+k+1}}{2} \cdot \frac{k^2+k}{2} \right)\\ &= \frac34\sum^n_{k=1} k^2 +\frac34\sum^n_{k=1} k +\frac{(-1)^n}{4}\sum^n_{k=1} (-1)^{k+1} k^2 +\frac{(-1)^n}{4}\sum^n_{k=1} (-1)^{k+1} k.\\ \end{align}$$

Next, use these formulae

$$\begin{align} \sum^n_{k=1} (-1)^{k+1} k &=(-1)^{n+1} \left\lceil \frac{n}{2} \right\rceil,\\ \sum^n_{k=1} (-1)^{k+1} k^2 &=(-1)^{n+1} \left( \frac{n^2}{2} +\frac{n}{2} \right). \end{align}$$

And noting that $$(-1)^n (-1)^{n+1} = -(-1)^{2n} =-\big((-1)^n\big)^2 =-1,$$ we arrive at $$\begin{align} T(n) &=\frac14 n^3 +\frac58 n^2 +\frac38 n -\frac14 \left\lceil \frac{n}{2} \right\rceil \\&\equiv\frac{n(2n+3)(n+1)}{8} -\frac14 \left\lceil \frac{n}{2} \right\rceil.\end{align}$$

Answer 2

Yes, the formula can be simplified.

In particular, if, for some particular $n$, we define $$S_m=\sum_{k=1}^m\left(\frac{3-(-1)^{n-k}}{2}\frac{k^2+k}{2}\right)$$. Note that $S_n=T_n$, and that $S_m$ satisfies $$S_m=S_{m-1}+\frac{3m^2}{4}+\frac{3m}{4}-\frac{(-1)^n}{4}((-1)^mm^2)-\frac{(-1)^n}{4}((-1)^mm)$$

The general solution to this will be $S_m=Am+P_m$, where $P_m$ is a particular solution of the form $P_m=Bm^3+Cm^2+Dm+E(-1)^mm^2+F(-1)^mm$. You can find the constants $B$, $C$, $D$, $E$ and $F$ from the difference equation, and then $A$ will be given by the initial value $S_0=0$.

Finally, remember that $T_n=S_n$, and you have your formula.

NB - I've assumed your formula is correct, I haven't checked it. You may want to see if it gives correct answers for $T_1$, $T_2$, $T_3$ and maybe $T_4$ before doing any complicated algebra.

Answer 3

First, lets start with what we know. We know that

$$ A_m:= \sum_{k=1}^mk=\frac{m(m+1)}{2} \; \; \; \; \; \; \; \; \; \; \; \; \; \; B_m:=\sum_{k=1}^mk^2=\frac{m(m+1)(2m+1)}{6}$$

Now lets try to work out $$ C_n :=\sum_{k=1}^n(-1)^kk \; \; \; \; \; \; \; \; \; \; \; \; \; \; D_n:=\sum_{k=1}^n(-1)^kk^2$$

assuming tha $n$ is even. Observe that $$C_n=-A_n+4A_{n/2}=-\frac{n(n+1)}{2}+4\frac{\frac n2 (\frac n2+1)}{2}=\frac n2$$

$$D_n=-B_n+8B_{n/2}=-\frac{n(n+1)(2n+1)}{6}+8\frac{\frac n2(\frac n2+1)(n+1)}{6}=\frac{n(n+1)}{2}$$

For $n$ being odd, we simply break the sum into two parts and use the above, i.e.

$$C_n=\sum_{k=1}^n(-1)^kk=\sum_{k=1}^{n-1}(-1)^kk-n=\frac {n-1}{2} -n=-\frac{n+1}{2}$$ Similarly,

$$D_n=\frac{n(n-1)}{2}-n^2=-\frac{n(n+1)}{2}$$

Now, I assume that your formula for $T(n)$ is correct, so using that, we get

\begin{align} \ T(n) & = \sum_{k=1}^n \biggl(\frac{3-(-1)^{n-k}}{2}\sum_{j=1}^kj\biggr) \\ \ & = \sum_{k=1}^n \biggl(\frac{3-(-1)^{n-k}}{2} \frac{k(k+1)}{2} \biggr) \\ \ & = \sum_{k=1}^n \biggl(\frac 34 k^2 + \frac 34 k - \frac{(-1)^{n-k}}{4}k^2-\frac{(-1)^{n-k}}{4}k \biggr) \\ \end{align}

Now supposing that $n$ is even

\begin{align} \ & = \frac 34 \frac{n(n+1)(2n+1)}{6}+ \frac 34 \frac{n(n+1)}{2}-\frac{(-1)^n}{4}\frac{n(n+1)}{2} -\frac{(-1)^n}{4} \frac n2 \\ \ & = \frac{n(n+1)(n+2)}{4} - \frac{(-1)^nn(n+2)}{8} \\ \ & = \frac{n(n+2)(2n+2-(-1)^n)}{8} \\ \ & = \frac{n(n+2)(2n+1)}{8} \end{align}

Similarly, for $n$ odd, we plug in the odd expression for the sums

\begin{align} \ & = \frac 34 \frac{n(n+1)(2n+1)}{6}+ \frac 34 \frac{n(n+1)}{2}+\frac{(-1)^n}{4}\frac{n(n+1)}{2} +\frac{(-1)^n}{4} \frac {n+1}{2} \\ \ & = \frac{n(n+1)(n+2)}{4} + \frac{(-1)^n(n+1)^2}{8} \\ \ & = \frac{(n+1)(2n^2+3n-1)}{8} \end{align}