# Formula for sums of rows of a “triangle” of arithmetic progressions

Due to my lack of mathematical training, I'm having a hard time phrasing this question, so please bear with me.

Let '$a_{(1,j)}$' define the following series: $a_{(1,1)}=1$, $a_{(1,n)}=a_{(1,(n-1))}+2$. Let $a_{(i,j)}$ define the following arithmetic progression for $i>1$: $a_{(i,1)}=a_{((i-1),1)}+1+i$, $a_{(i,n)}=a_{(i,(n-1))}+2\cdot i$. Constructing a triangle whose diagonals consist of elements of arithmetic progressions defined along this line, we get (assuming I got everything right):

1
4  3
8  8  5
13 14 12 7
19 21 20 16 9
26 29 29 26 20 11
34 38 39 37 32 24 13
43 48 50 49 45 38 28 15
. . .


Where the elements of the ith diagonal (starting from the top) are the elements of $a_{(i,j)}$.

• Can we find an explicit formula for the row sums of this triangle, and prove that it is valid? An emphasis on the 'proof' part because using semi-intuitive techniques from high school (that's as far as I go) I've found the following formula, which seems to work: $\frac{1}{2}(n^3+2n^2-n)$. But of course I have no proof that this formula is inductively correct.
• Assuming the formula I found earlier is correct, would the fact that it is a polynomial of 3rd degree hold for other 'triangles of arithmetic progressions'? (This interests me because of the seeming connection between the number '3' and our 'triangle' of sorts.)

-
It would be great if someone could format this. I would do it but I don't know how! "a_1_n=(a_1_(n-1))+2" is rather hard to read. Thanks. – judien Sep 25 '11 at 18:14
I've edited your question so that $\LaTeX$ appears for the mathematics. You can view what I did if you click on the edit link. – Matt Groff Sep 25 '11 at 19:14
Thanks, exactly what I wanted! – judien Sep 25 '11 at 21:21
Welcome to math.stackexchange! I can't resist the temptation to suggest a book that explores summations similar to this, called "generatingfunctionology" by Herbert Wilf. Here's a link to a free download, just in case you're interested: math.upenn.edu/~wilf/DownldGF.html – Matt Groff Sep 25 '11 at 23:56

Your formula is indeed correct, and something similar does hold for similarly formed triangles. In deference to your stated lack of background, I’ve included a lot of algebraic detail; I hope that it isn’t too messy to wade through.

What you have is a sequence of arithmetic progressions whose differences themselves form an arithmetic progression: in your case the differences are $2,4,6,8,\dots$. Moreover, the first terms of your progressions behave in a regular way: they form a sequence, $\langle 1,4,8,13,19,\dots\rangle$, that isn’t arithmetic, but whose difference sequence is. By difference sequence I mean the sequence of differences between consecutive terms: $\langle 3,4,5,6,\dots\rangle$.

Suppose that you have such a collection of arithmetic progressions:

• for each $n$, $\langle a_{n,1},a_{n,2},a_{n,3},\dots\rangle$ is an arithmetic progression with constant difference $d_n$;

• $\langle d_1,d_2,d_3,\dots\rangle$ is an arithmetic progression with constant difference $d$; and

• the sequence $\langle a_{1,1},a_{2,1},a_{3,1},\dots\rangle$ of first terms is not arithmetic, but its difference sequence $\langle a_{2,1}-a_{1,1},a_{3,1}-a_{2,1},a_{4,1}-a_{3,1},\dots\rangle$ is, with constant difference $e$.

Now you build a triangle just as you did with your specific progressions. We can calculate the row sums as follows.

The terms in the $n$-th row are $a_{n,1},a_{n-1,2},a_{n-2,3},\dots,a_{1,n}$. In other words, they are the terms $a_{k,n+1-k}$ for $k=1,2,\dots,n$. Now $a_{k,n+1-k}$ is the $(n+1-k)$-th term in the $k$-th progression, so $$a_{k,n+1-k} = a_{k,1} + ((n+1-k)-1)d_k = a_{k,1}+(n-k)d_k,$$ and $d_k$ is the $k$-th difference, so $$d_k = d_1+(k-1)d.$$ Thus, \begin{align*}a_{k,n+1-k} &= a_{k,1} + (n-k)(d_1+(k-1)d)\\ &= a_{k,1} + (n-k)d_1 + (n-k)(k-1)d\\&= a_{k,1} + nd_1 - kd_1 +(nk - n - k^2 + k)d\\ &= a_{k,1} + n(d_1-d) + ((n+1)d-d_1)k-dk^2, \end{align*}

and the sum of the terms in the $n$-th row is \begin{align*} \sum\limits_{k=1}^n a_{k,n+1-k} &= \sum\limits_{k=1}^n \left(a_{k,1} + n(d_1-d) + ((n+1)d-d_1)k-dk^2\right)\\ &= \sum\limits_{k=1}^n a_{k,1} + \sum\limits_{k=1}^n n(d-d_1) + \sum\limits_{k=1}^n ((n+1)d-d_1)k - \sum\limits_{k=1}^n dk^2\\ &= \sum\limits_{k=1}^n a_{k,1} + n^2(d-d_1) + ((n+1)d-d_1)\sum\limits_{k=1}^n k - d\sum\limits_{k=1}^n k^2. \end{align*}

The summations $\sum\limits_{k=1}^n k = \dfrac12n(n+1)$ and $\sum\limits_{k=1}^n k^2 = \dfrac16n(n+1)(2n+1)$ are well-known, so \begin{align*} \sum\limits_{k=1}^n a_{k,n+1-k} &= \sum\limits_{k=1}^n a_{k,1} + n^2(d-d_1) + \frac12((n+1)d-d_1)n(n+1) - \frac16dn(n+1)(2n+1)\\ &= \sum\limits_{k=1}^n a_{k,1} + d\left(n^2 + \frac12n(n+1)^2 - \frac16n(n+1)(2n+1)\right) - d_1\left(n^2 + \frac12n(n+1)\right)\\ &= \sum\limits_{k=1}^n a_{k,1} + \frac{d}6\left(6n^2 + 3n(n+1)^2 - n(n+1)(2n+1)\right) - \frac{d_1}2(3n^2+n)\\ &= \sum\limits_{k=1}^n a_{k,1} + \frac{d}6\left(6n^2 + (3n^3+6n^2+3n) - (2n^3+3n^2+n)\right)-\frac{d_1}2(3n^2+n)\\ &= \sum\limits_{k=1}^n a_{k,1} + \frac{d}6(n^3+9n^2+2n)-\frac{d_1}2(3n^2+n)\\ &= \sum\limits_{k=1}^n a_{k,1} + \frac{d}6 n^3 + \frac{3d-3d_1}{2}n^2 + \frac{2d-3d_1}{6}n. \end{align*}

Now we need to evaluate $\sum\limits_{k=1}^n a_{k,1}$ in terms of $n$. This takes a little work, since the sequence of $a_{k,1}$’s isn’t arithmetic. Let $e_k = a_{k+1,1}-a_k$; we assumed that the sequence $\langle e_1, e_2, e_3,\dots\rangle$ is arithmetic with constant difference $e$, so $e_k = e_1 + (k-1)e$. Thus, \begin{align*} a_{k,1} &= a_{1,1} + e_1 + e_2 + \dots + e_{k-1}\\ &= a_{1,1} + \sum\limits_{i=1}^{k-1} (e_1 + (i-1)e)\\ &= a_{1,1} + \sum\limits_{i=1}^{k-1} e_1 + e\sum\limits_{i=1}^{k-1} (i-1)\\ &= a_{1,1} + (k-1)e_1 + e\sum\limits_{i=0}^{k-2} i\\ &= a_{1,1} + (k-1)e_1 + \frac12 e(k-2)(k-1)\\ &= a_{1,1} + e_1k - e_1 + \frac{e}2 k^2 - \frac{3e}{2}k+e\\ &= \frac{e}2 k^2 + \frac{2e_1-3e}{2}k + (a_{1,1}+e-e_1), \end{align*}

and therefore \begin{align*} \sum\limits_{k=1}^n a_{k,1} &= \sum\limits_{k=1}^n \left(\frac{e}2 k^2 + \frac{2e_1-3e}{2}k + (a_{1,1}+e-e_1)\right)\\ &= \frac{e}{2}\sum\limits_{k=1}^n k^2 + \frac{2e_1-3e}{2}\sum\limits_{k=1}^n k + \sum\limits_{k=1}^n (a_{1,1}+e-e_1)\\ &= \frac{e}{12}n(n+1)(2n+1) + \frac{2e_1-3e}{4}n(n+1) + (a_{1,1}+e-e_1)n\\ &= \frac{e}{12}(2n^3+3n^2+n) + \frac{2e_1-3e}{4}(n^2+n) + (a_{1,1}+e-e_1)n\\ &= \frac{e}6 n^3 + \frac{e_1-e}{2}n^2 + \frac{6a_{1,1}+2e-3e_1}{6}n. \end{align*}

Finally, then, the $n$-th row sum is \begin{align*} &\sum\limits_{k=1}^n a_{k,1} + \frac{d}6 n^3 + \frac{3d-3d_1}{2}n^2 + \frac{2d-3d_1}{6}n =\\ &\frac{e}6 n^3 + \frac{e_1-e}{2}n^2 + \frac{6a_{1,1}+2e-3e_1}{6}n + \frac{d}6 n^3 + \frac{3d-3d_1}{2}n^2 + \frac{2d-3d_1}{6}n =\\ &\frac{e+d}6 n^3 + \frac{e_1-e+3d-3d_1}2 n^2 + \frac{6a_{1,1}+2(e+d)-3(e_1+d_1)}6 n,\tag{1} \end{align*}

which is indeed cubic in $n$.

As a quick check on all this algebra, note that in your original example $a_{1,1}=1$, $d_1=2$, $d=2$, $e_1=3$, and $e=1$, so $(1)$ reduces to $$\frac12 n^3 + n^2 - \frac12 n,$$ as we know it should.

-

From $a(1,1) = 1$ and $a(i,1) = a(i-1,1) + 1 + i$ we get $$a(i,1) = 1 + \sum_{k=2}^i (1+k) = \frac{i^2}{2} + \frac{3i}{2} - 1.$$ From that and $a(i,j) = a(i,j-1) + 2i$ we get $$a(i,j) = \frac{i^2}{2} + \frac{3i}{2} - 1 + \sum_{k=2}^j 2i = \frac{i^2}{2} + \frac{3i}{2} - 1 + 2 i (j-1).$$ Then your $i$'th row sum is \begin{align*} \sum_{k=1}^i a(i+1-k,k) &= \sum_{k=1}^i \left(-\frac{3}{2}{k}^{2}+\frac{3}{2}k+ik-1+\frac{1}{2}{i}^{2}+\frac{1}{2}i\right)\\ &= \frac{i^3}{2} + i^2 - \frac{i}{2}\text{(after some simplification)}. \end{align*}

-
Thank you, this clears up my first question. Do you also have an answer for the second one? – judien Sep 25 '11 at 21:23
As long as the expression for $a(i+1-k,k)$ is a polynomial of total degree $2$ in $i$ and $k$, you will (in the absence of cancellation) get a cubic for $\sum_{k=1}^i a(i+1-k,k)$. – Robert Israel Sep 25 '11 at 23:13

For your second question, you would expect a third degree polynomial for the row sums. As the columns are increasing by one more each row, they are quadratic in the row number. Then the number of items in each row increases linearly with row number, so the row sum will be cubic.

-
Very nice, this answers everything. Thank you. Now my problem is I don't know which answer I should select since your and Robert's answers complement each other... – judien Sep 25 '11 at 22:25
@judien: He did a lot more work than I did, so go ahead and accept his. – Ross Millikan Sep 25 '11 at 22:38