2
$\begingroup$

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:

enter image description here

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 .

$\endgroup$
1
2
$\begingroup$

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*} $$

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – kasra
    Mar 8 '21 at 12:06
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Steven
    Mar 8 '21 at 12:47
  • $\begingroup$ Thanks a lot :) $\endgroup$
    – kasra
    Mar 8 '21 at 13:55
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.