We have the lower-triangular matrix
A = [ 1 0 0 1 1 0 1 1 1 ] A=\begin{bmatrix}1&0&0\\1&1&0\\1&1&1\end{bmatrix} A = 1 1 1 0 1 1 0 0 1
and we want the sum of the three numbers that appear in the first column of B = A 20 . B=A^{20}\,. B = A 20 . Let us denote, for every positive integer n , n, n ,
A n = [ a 11 ( n ) a 12 ( n ) a 13 ( n ) a 21 ( n ) a 22 ( n ) a 23 ( n ) a 31 ( n ) a 32 ( n ) a 33 ( n ) ] . A^{n}=\begin{bmatrix}a_{11}^{(n)}&a_{12}^{(n)}&a_{13}^{(n)}\\[2pt]
a_{21}^{(n)}&a_{22}^{(n)}&a_{23}^{(n)}\\[2pt]
a_{31}^{(n)}&a_{32}^{(n)}&a_{33}^{(n)}\end{bmatrix}. A n = a 11 ( n ) a 21 ( n ) a 31 ( n ) a 12 ( n ) a 22 ( n ) a 32 ( n ) a 13 ( n ) a 23 ( n ) a 33 ( n ) .
The required sum is therefore
S n = a 11 ( n ) + a 21 ( n ) + a 31 ( n ) . S_{n}=a_{11}^{(n)}+a_{21}^{(n)}+a_{31}^{(n)}. S n = a 11 ( n ) + a 21 ( n ) + a 31 ( n ) .
We now build up the powers step by step so that every algebraic detail is visible and a pattern can be recognised.
Power 1. We clearly have
A 1 = A = [ 1 0 0 1 1 0 1 1 1 ] , A^{1}=A=\begin{bmatrix}1&0&0\\1&1&0\\1&1&1\end{bmatrix}, A 1 = A = 1 1 1 0 1 1 0 0 1 ,
so
( a 11 ( 1 ) , a 21 ( 1 ) , a 31 ( 1 ) ) = ( 1 , 1 , 1 ) \bigl(a_{11}^{(1)},\,a_{21}^{(1)},\,a_{31}^{(1)}\bigr)=(1,1,1) ( a 11 ( 1 ) , a 21 ( 1 ) , a 31 ( 1 ) ) = ( 1 , 1 , 1 )
and therefore
S 1 = 1 + 1 + 1 = 3. S_{1}=1+1+1=3. S 1 = 1 + 1 + 1 = 3.
Power 2. Using plain matrix multiplication, and writing every scalar product explicitly, we have
A 2 = A ⋅ A = [ 1 ⋅ 1 + 0 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 0 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 0 ⋅ 0 + 0 ⋅ 1 1 ⋅ 1 + 1 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 1 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 1 ⋅ 0 + 0 ⋅ 1 1 ⋅ 1 + 1 ⋅ 1 + 1 ⋅ 1 1 ⋅ 0 + 1 ⋅ 1 + 1 ⋅ 1 1 ⋅ 0 + 1 ⋅ 0 + 1 ⋅ 1 ] A^{2}=A\!\cdot\!A=\begin{bmatrix}
1\cdot1+0\cdot1+0\cdot1 & 1\cdot0+0\cdot1+0\cdot1 & 1\cdot0+0\cdot0+0\cdot1\\[4pt]
1\cdot1+1\cdot1+0\cdot1 & 1\cdot0+1\cdot1+0\cdot1 & 1\cdot0+1\cdot0+0\cdot1\\[4pt]
1\cdot1+1\cdot1+1\cdot1 & 1\cdot0+1\cdot1+1\cdot1 & 1\cdot0+1\cdot0+1\cdot1
\end{bmatrix} A 2 = A ⋅ A = 1 ⋅ 1 + 0 ⋅ 1 + 0 ⋅ 1 1 ⋅ 1 + 1 ⋅ 1 + 0 ⋅ 1 1 ⋅ 1 + 1 ⋅ 1 + 1 ⋅ 1 1 ⋅ 0 + 0 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 1 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 1 ⋅ 1 + 1 ⋅ 1 1 ⋅ 0 + 0 ⋅ 0 + 0 ⋅ 1 1 ⋅ 0 + 1 ⋅ 0 + 0 ⋅ 1 1 ⋅ 0 + 1 ⋅ 0 + 1 ⋅ 1
which simplifies to
A 2 = [ 1 0 0 2 1 0 3 2 1 ] . A^{2}=\begin{bmatrix}1&0&0\\2&1&0\\3&2&1\end{bmatrix}. A 2 = 1 2 3 0 1 2 0 0 1 .
Thus
( a 11 ( 2 ) , a 21 ( 2 ) , a 31 ( 2 ) ) = ( 1 , 2 , 3 ) \bigl(a_{11}^{(2)},\,a_{21}^{(2)},\,a_{31}^{(2)}\bigr)=(1,2,3) ( a 11 ( 2 ) , a 21 ( 2 ) , a 31 ( 2 ) ) = ( 1 , 2 , 3 )
and
S 2 = 1 + 2 + 3 = 6. S_{2}=1+2+3=6. S 2 = 1 + 2 + 3 = 6.
Power 3. Multiplying A 2 A^{2} A 2 by A A A again, while displaying every dot product,
A 3 = A 2 A = [ 1 0 0 2 1 0 3 2 1 ] [ 1 0 0 1 1 0 1 1 1 ] A^{3}=A^{2}A=\begin{bmatrix}
1&0&0\\2&1&0\\3&2&1\end{bmatrix}
\begin{bmatrix}
1&0&0\\1&1&0\\1&1&1
\end{bmatrix} A 3 = A 2 A = 1 2 3 0 1 2 0 0 1 1 1 1 0 1 1 0 0 1
gives
A 3 = [ 1 ⋅ 1 + 0 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 0 ⋅ 1 + 0 ⋅ 1 1 ⋅ 0 + 0 ⋅ 0 + 0 ⋅ 1 2 ⋅ 1 + 1 ⋅ 1 + 0 ⋅ 1 2 ⋅ 0 + 1 ⋅ 1 + 0 ⋅ 1 2 ⋅ 0 + 1 ⋅ 0 + 0 ⋅ 1 3 ⋅ 1 + 2 ⋅ 1 + 1 ⋅ 1 3 ⋅ 0 + 2 ⋅ 1 + 1 ⋅ 1 3 ⋅ 0 + 2 ⋅ 0 + 1 ⋅ 1 ] = [ 1 0 0 3 1 0 6 3 1 ] . \begin{aligned}
A^{3}&=\begin{bmatrix}
1\cdot1+0\cdot1+0\cdot1 & 1\cdot0+0\cdot1+0\cdot1 & 1\cdot0+0\cdot0+0\cdot1\\[4pt]
2\cdot1+1\cdot1+0\cdot1 & 2\cdot0+1\cdot1+0\cdot1 & 2\cdot0+1\cdot0+0\cdot1\\[4pt]
3\cdot1+2\cdot1+1\cdot1 & 3\cdot0+2\cdot1+1\cdot1 & 3\cdot0+2\cdot0+1\cdot1
\end{bmatrix}\\[6pt]
&=\begin{bmatrix}1&0&0\\3&1&0\\6&3&1\end{bmatrix}.
\end{aligned} A 3 = 1 ⋅ 1 + 0 ⋅ 1 + 0 ⋅ 1 2 ⋅ 1 + 1 ⋅ 1 + 0 ⋅ 1 3 ⋅ 1 + 2 ⋅ 1 + 1 ⋅ 1 1 ⋅ 0 + 0 ⋅ 1 + 0 ⋅ 1 2 ⋅ 0 + 1 ⋅ 1 + 0 ⋅ 1 3 ⋅ 0 + 2 ⋅ 1 + 1 ⋅ 1 1 ⋅ 0 + 0 ⋅ 0 + 0 ⋅ 1 2 ⋅ 0 + 1 ⋅ 0 + 0 ⋅ 1 3 ⋅ 0 + 2 ⋅ 0 + 1 ⋅ 1 = 1 3 6 0 1 3 0 0 1 .
Hence
( a 11 ( 3 ) , a 21 ( 3 ) , a 31 ( 3 ) ) = ( 1 , 3 , 6 ) \bigl(a_{11}^{(3)},\,a_{21}^{(3)},\,a_{31}^{(3)}\bigr)=(1,3,6) ( a 11 ( 3 ) , a 21 ( 3 ) , a 31 ( 3 ) ) = ( 1 , 3 , 6 )
and
S 3 = 1 + 3 + 6 = 10. S_{3}=1+3+6=10. S 3 = 1 + 3 + 6 = 10.
Writing the sums that we have found so far, we notice the sequence
S 1 = 3 , S 2 = 6 , S 3 = 10. S_{1}=3,\qquad S_{2}=6,\qquad S_{3}=10. S 1 = 3 , S 2 = 6 , S 3 = 10.
The successive differences are 3 3 3 and 4 , 4, 4 , then 4 4 4 and ? ? ? in the next step, so it looks like the pattern is the familiar triangular-number pattern. Indeed, the first three terms can be matched exactly by the well-known formula for the k k k -th triangular number, namely
T k = k ( k + 1 ) 2 . T_{k}=\frac{k(k+1)}{2}. T k = 2 k ( k + 1 ) .
Re-indexing appropriately, we suspect that
S n = ( n + 1 ) ( n + 2 ) 2 = ( n + 2 2 ) . S_{n}=\frac{(n+1)(n+2)}{2}=\binom{n+2}{2}. S n = 2 ( n + 1 ) ( n + 2 ) = ( 2 n + 2 ) .
Formal proof of the pattern by mathematical induction.
Base case n = 1 n=1 n = 1 has already been calculated: S 1 = 3 = ( 3 2 ) . S_{1}=3=\binom{3}{2}. S 1 = 3 = ( 2 3 ) .
Now assume for some n = k n=k n = k that
S k = a 11 ( k ) + a 21 ( k ) + a 31 ( k ) = ( k + 2 2 ) . S_{k}=a_{11}^{(k)}+a_{21}^{(k)}+a_{31}^{(k)}=\binom{k+2}{2}. S k = a 11 ( k ) + a 21 ( k ) + a 31 ( k ) = ( 2 k + 2 ) .
To pass from A k A^{k} A k to A k + 1 , A^{k+1}, A k + 1 , we right-multiply by A . A. A . Concerning only the first column, we use the fact that the first column of A A A itself is
[ 1 1 1 ] , \begin{bmatrix}1\\1\\1\end{bmatrix}, 1 1 1 ,
so
[ a 11 ( k + 1 ) a 21 ( k + 1 ) a 31 ( k + 1 ) ] = A k [ 1 1 1 ] = [ a 11 ( k ) ⋅ 1 + a 12 ( k ) ⋅ 1 + a 13 ( k ) ⋅ 1 a 21 ( k ) ⋅ 1 + a 22 ( k ) ⋅ 1 + a 23 ( k ) ⋅ 1 a 31 ( k ) ⋅ 1 + a 32 ( k ) ⋅ 1 + a 33 ( k ) ⋅ 1 ] . \begin{bmatrix}a_{11}^{(k+1)}\\ a_{21}^{(k+1)}\\ a_{31}^{(k+1)}\end{bmatrix}=A^{k}\begin{bmatrix}1\\1\\1\end{bmatrix}=
\begin{bmatrix}
a_{11}^{(k)}\cdot1+a_{12}^{(k)}\cdot1+a_{13}^{(k)}\cdot1\\[4pt]
a_{21}^{(k)}\cdot1+a_{22}^{(k)}\cdot1+a_{23}^{(k)}\cdot1\\[4pt]
a_{31}^{(k)}\cdot1+a_{32}^{(k)}\cdot1+a_{33}^{(k)}\cdot1
\end{bmatrix}. a 11 ( k + 1 ) a 21 ( k + 1 ) a 31 ( k + 1 ) = A k 1 1 1 = a 11 ( k ) ⋅ 1 + a 12 ( k ) ⋅ 1 + a 13 ( k ) ⋅ 1 a 21 ( k ) ⋅ 1 + a 22 ( k ) ⋅ 1 + a 23 ( k ) ⋅ 1 a 31 ( k ) ⋅ 1 + a 32 ( k ) ⋅ 1 + a 33 ( k ) ⋅ 1 .
That is,
a 11 ( k + 1 ) = a 11 ( k ) + a 12 ( k ) + a 13 ( k ) , a 21 ( k + 1 ) = a 21 ( k ) + a 22 ( k ) + a 23 ( k ) , a 31 ( k + 1 ) = a 31 ( k ) + a 32 ( k ) + a 33 ( k ) . \begin{aligned}
a_{11}^{(k+1)}&=a_{11}^{(k)}+a_{12}^{(k)}+a_{13}^{(k)},\\
a_{21}^{(k+1)}&=a_{21}^{(k)}+a_{22}^{(k)}+a_{23}^{(k)},\\
a_{31}^{(k+1)}&=a_{31}^{(k)}+a_{32}^{(k)}+a_{33}^{(k)}.
\end{aligned} a 11 ( k + 1 ) a 21 ( k + 1 ) a 31 ( k + 1 ) = a 11 ( k ) + a 12 ( k ) + a 13 ( k ) , = a 21 ( k ) + a 22 ( k ) + a 23 ( k ) , = a 31 ( k ) + a 32 ( k ) + a 33 ( k ) .
Adding these three equalities together we get
S k + 1 = S k + ( a 12 ( k ) + a 22 ( k ) + a 32 ( k ) ) + ( a 13 ( k ) + a 23 ( k ) + a 33 ( k ) ) . S_{k+1}=S_{k}+ \bigl(a_{12}^{(k)}+a_{22}^{(k)}+a_{32}^{(k)}\bigr)+
\bigl(a_{13}^{(k)}+a_{23}^{(k)}+a_{33}^{(k)}\bigr). S k + 1 = S k + ( a 12 ( k ) + a 22 ( k ) + a 32 ( k ) ) + ( a 13 ( k ) + a 23 ( k ) + a 33 ( k ) ) .
But A k A^{k} A k is lower triangular with ones on the diagonal, so
a 12 ( k ) = 0 a_{12}^{(k)}=0 a 12 ( k ) = 0 and a 13 ( k ) = a 23 ( k ) = 0. a_{13}^{(k)}=a_{23}^{(k)}=0. a 13 ( k ) = a 23 ( k ) = 0.
Therefore
S k + 1 = S k + a 22 ( k ) + a 32 ( k ) + a 33 ( k ) . S_{k+1}=S_{k}+a_{22}^{(k)}+a_{32}^{(k)}+a_{33}^{(k)}. S k + 1 = S k + a 22 ( k ) + a 32 ( k ) + a 33 ( k ) .
Since every diagonal entry of any power of a unit lower-triangular matrix is 1 , 1, 1 , we know a 22 ( k ) = a 33 ( k ) = 1. a_{22}^{(k)}=a_{33}^{(k)}=1. a 22 ( k ) = a 33 ( k ) = 1. Furthermore, the (3,2) entry is precisely k , k, k , because we can check directly for k = 1 , 2 , 3 k=1,2,3 k = 1 , 2 , 3 and see by induction that one unit is added at each new multiplication. Hence
S k + 1 = S k + 1 + k + 1 = S k + k + 2. S_{k+1}=S_{k}+1+k+1=S_{k}+k+2. S k + 1 = S k + 1 + k + 1 = S k + k + 2.
Using the induction hypothesis S k = ( k + 1 ) ( k + 2 ) 2 , S_{k}=\dfrac{(k+1)(k+2)}{2}, S k = 2 ( k + 1 ) ( k + 2 ) , we get
S k + 1 = ( k + 1 ) ( k + 2 ) 2 + k + 2 = ( k + 1 ) ( k + 2 ) + 2 ( k + 2 ) 2 = ( k + 2 ) ( k + 3 ) 2 = ( ( k + 1 ) + 2 2 ) . \begin{aligned}
S_{k+1}&=\frac{(k+1)(k+2)}{2}+k+2\\[4pt]
&=\frac{(k+1)(k+2)+2(k+2)}{2}\\[4pt]
&=\frac{(k+2)(k+3)}{2}\\[4pt]
&=\binom{(k+1)+2}{2}.
\end{aligned} S k + 1 = 2 ( k + 1 ) ( k + 2 ) + k + 2 = 2 ( k + 1 ) ( k + 2 ) + 2 ( k + 2 ) = 2 ( k + 2 ) ( k + 3 ) = ( 2 ( k + 1 ) + 2 ) .
Thus the induction is complete and the formula
S n = ( n + 1 ) ( n + 2 ) 2 = ( n + 2 2 ) S_{n}=\frac{(n+1)(n+2)}{2}=\binom{n+2}{2} S n = 2 ( n + 1 ) ( n + 2 ) = ( 2 n + 2 )
holds for every positive integer n . n. n .
Evaluating for n = 20. n=20. n = 20.
Substituting n = 20 n=20 n = 20 in the proven expression, we obtain
S 20 = ( 20 + 1 ) ( 20 + 2 ) 2 = 21 ⋅ 22 2 = 231. S_{20}=\frac{(20+1)(20+2)}{2}=\frac{21\cdot22}{2}=231. S 20 = 2 ( 20 + 1 ) ( 20 + 2 ) = 2 21 ⋅ 22 = 231.
Therefore, the sum of the elements of the first column of B = A 20 B=A^{20} B = A 20 equals 231. 231. 231.
Hence, the correct answer is Option D.