Closed-form expression for the sums of the rows of the Trinomial triangle

There is a question in the second chapter of the book that I'm unable to solve, and unfortunately algorist.com does not provide a rigorous enough solution, or maybe I can't quite understand it. Here is the question: I've noticed the sums of rows are the powers of 3, and it's intuitively obvious that the sums of rows are multiples of 3, however I can't prove that they are powers of 3.

Any help would be much appreciated.

The Algorithm Design Manual from Steven S. Skiena You can get it from here.

Also here is the solution I found on algorist.com .

Intuitively, each integer on the $$i$$-th row participates exactly three times in the sum of the integers on the $$(i+1)$$-th row. This means that the sum $$S_{i+1}$$ of the integers in the $$(i+1)$$-th row must be exactly $$3$$ times as large as the sum $$S_i$$ of the integers in the $$i$$-th row, i.e., $$S_{i+1}=3S_i$$ (and $$S_1=1)$$. A formal argument is as follows:

Let $$x^{(i)}_j$$ be the $$j$$-th integer on the $$i$$-th row and define $$S_i = \sum_{j=1}^{2i-1} x^{(i)}_j$$. For simplicity define $$x^{(i)}_j = 0$$ whenever $$j \le 0$$ or $$j \ge 2i$$. You can show by induction on $$i$$ that $$S_i = 3^{i-1}$$.

The base case $$i=1$$ is trivially true since $$S_1 = x^{(1)}_1 = 1 = 3^0 = 3^{1-1}$$. Suppose now that the claim holds for $$i\ge 1$$. Then, the claim must also hold for $$i+1$$. Indeed:

\begin{align*} S_{i+1} &= \sum_{j=1}^{2i+1} x^{(i+1)}_j = \sum_{j=1}^{2i+1} \left( x^{(i)}_{j-2} + x^{(i)}_{j-1} + x^{(i)}_{j}\right) = \sum_{j=1}^{2i+1} x^{(i)}_{j-2} + \sum_{j=1}^{2i+1} x^{(i)}_{j-1} + \sum_{j=1}^{2i+1} x^{(i)}_{j} \\ &= 3 \sum_{j=1}^{2i-1} x^{(i)}_{j} = 3S_i = 3 \cdot3^{i-1} = 3^i. \end{align*}

• Thank you so much! just one question, could you please explain how you derived (3∑<j=1><2i-1>{x[(i), j]}) from the equation above? Thanks nonetheless! Mar 8 '21 at 12:06
• Each of the three sums above is equal to $\sum_{j=1}^{2i-1} x^{(i)}_j$. I'll show you how to manipulate the first sum (the other sums are similar): $\sum_{j=1}^{2i+1} x^{(i)}_{j-2} = x^{(i)}_{-1} + x^{(i)}_{0} + \sum_{j=3}^{2i+1} x^{(i)}_{j-2} = 0 + 0 + \sum_{j=1}^{2i-1} x^{(i)}_j = \sum_{j=1}^{2i-1} x^{(i)}_j$. Mar 8 '21 at 12:47
• Thanks a lot :) Mar 8 '21 at 13:55

This is much like Pascal's triangle of course, but adding three neighbours, rather than two. Here is the combinatorial argument, which works just like the binomial case.

Assume in each cell you can move down, moving to the cell below, or two one of the neightbours of it. Then the numbers in the triangle just represent the number of paths that can be taken to move from the top cell to the cell at a specific position. (That can be proved by induction: the paths to a given cell all go through exactly one of the three neighbours above.) Now the sum of the numbers in the $$i$$th row, equals the number of paths to the $$i$$th level. This is a power of $$3$$, because in each level we can move in three directions: $$3\times 3 \times\dots\times 3$$ choices are being made.