Trouble with building a matrix (Fixed-point iteration) can you help me out with a certain task from the book in a chapter that covers fixed-point iterarion:

N.S. Bakhvalov, A.V. Lapin, E.V. Chizhonkov Chislennye metody v
zadachakh i uprazhneniyakh.- M: Binom. - 2010, 240 str.

here's the translation of that task:
Build a square matrix $A[31][31]$ with elements $|a_{ij} \le 1|$ and it's eigenvalues $|λ(A)| \le 1$, so that $||  A^{30}  ||_\infty \ge 10^9$
Here's what I did so far:
The book has an answer:
$A =
\begin{cases}
1,  & \text{if $i=j$} \\
1,  & \text{if $i+1=j$} \\
0, & \text{else}
\end{cases}$
Using that knowledge I managed to find the "sorta-works solution".
Using python's library numpy I created the matrix with described dimensions, filled the respective entries with 1's according to the answer, raised the matrix to the power of 30, determined inf-norm, determined eigenvalues and eigenvectors.
Inf-norm happened to be $1073741824$ which is larger then $10^9$.
So all is fine. The answer corresponds.
But the problem is that I have to prove this by contradiction on a piece of paper, without using any programming.
All the steps required leave me puzzled, and I don't know what to do and how to do it.
Thank you in advance!
 A: If you look at the sum of the first line in the $k \times k$ case, and just take the first three terms, you can easily establish that $\|A^{k-1}\|_{\infty}> 2^k$. This is a very conservative lower bound but it is enough for the purpose of showing that, in the $31 \times 31$ case:
$$
\|A^{30}\|_{\infty} > 2^{30}> 10^9.
$$
A: Your matrix has the form of $I+S_1$, where $S_k$ is the matrix with the $k$th super-diagonal filled with $1$. Note $S_iS_j=S_{i+j}$ and $S_k=0$ if $k$ is greater than or equal the matrix size.
Now apply the binomial theorem
$$
(I+S_1)^n=I+nS_1+\binom{n}{2}S_2+\binom{n}{3}S_3+...+\binom{n}{30}S_{30}
$$
Thus in the first row of $A^{30}$ you get the row sum
$$
1+30+\binom{30}{2}+\binom{30}{3}+...+\binom{30}{30}=2^{30}.
$$
All the other row sums are smaller.
You could also have started with $A=I+S_1+...+S_{30}$, which is still upper triangular with eigenvalue $1$ of multiplicity $31$. This is formally equal to $(I-S_1)^{-1}$, using $S_1$ as generator. So by expansion of the formal binomial series
$$
A^{30}=(I-S_1)^{-30}=I+30S_1+\binom{31}{2}S_1^2+\binom{32}{3}S_1^3+...+\binom{59}{30}S_1^{30}
$$
using
$$
(-1)^k\binom{-30}{k}=(-1)^k\frac{-30(-30-1)...(-30-k+1)}{k!}
=\binom{29+k}k=\binom{29+k}{29}.
$$
Here the last term alone is already sufficient for the claim.,
$$
\binom{59}{29}=\frac{59·58·...·31}{29·28·...·3·2·1}
=\frac{59·58·...·46}{29·28·...·16}·\frac{45·44·...·41}{15·14·...·11}·\frac{40·39·...·31}{10·9·...·1}
\ge 2^{14}·3^{5}·4^{10}.
$$
