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} &amp;= \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} \\
&amp;= 3 \sum_{j=1}^{2i-1} x^{(i)}_{j} = 3S_i = 3 \cdot3^{i-1} = 3^i.
\end{align*}
$$