Show that this matrix series is positive semi-definite $A = B^\top B$ is a $k \times k$ symmetric positive semi-definite matrix and $\|A\|_2 \leq 1$. Consider the following sum for $c$:
$$S_n = \sum_{i=0}^{n-1} (n-i) A^{i} - \frac{1}{c} \sum_{i=0}^n A^{i}$$
Is $S_n$ PSD for a large enough constant $c$? 

My attempt: 
$S_n$ is clearly greater than zero when $ k = 1$. Similarly, if $A$ is diagonal, $S_n$ is PSD because each diagonal elements is greater than or equal to zero. For example, for $n=2$ and $A$ diagonal:
\begin{align}
S_2 = (1-1/c)I - 1/cA \preceq (1-1/c)I - 1/cI = (1-2/c)I
\end{align}
This matrix is PSD if $c \geq 2$. Can we show that for a general $A$? Is the assumption $\|A\|_2 \leq 1$ necessary or can we show this for $\|A\|_2 \leq \alpha$ for $\alpha > 1$ and modifying $c$ based on $\alpha$? 
 A: First notice why this should be true by dropping the second term. You see just a sum of positive semidefinte matrices given by the $(n-i)A^i$. When $c$ is large, you are only subtracting off something small.
$$
S_n = \sum_{i=0}^{n-1} (n-i) A^i - \frac{1}{c} \sum_{i=0}^n A^i\\
= \sum_{i=0}^{n-1} (n-1-(i-1)) A^i - \frac{1}{c} \sum_{i=0}^n A^i\\
= n I + \sum_{i=1}^{n-1} (n-1-(i-1)) A^i - \frac{1}{c} \sum_{i=0}^n A^i\\
= n I + A \sum_{j=0}^{n-2} (n-1-j) A^j - \frac{1}{c} \sum_{i=0}^n A^i\\
= n I + A \sum_{j=0}^{n-2} (n-1-j) A^j - \frac{1}{c} (I + A \sum_{i=1}^n A^{i-1})\\
= n I + A \sum_{j=0}^{n-2} (n-1-j) A^j - \frac{1}{c} (I + A \sum_{j=0}^{n-1} A^j)\\
= (n - \frac{1}{c}) I + A ( \sum_{j=0}^{n-2} (n-1-j) A^j - \frac{1}{c} \sum_{j=0}^{n-1} A^j)\\
= (n- \frac{1}{c}) I + A S_{n-1}\\
S_0 = I - \frac{1}{c} (I + A)\\
$$
See that $S_n$ can be expressed as some polynomial in $A$. You will also need to show that if $S_n$ is positive semidefinite for $c=c_0$, then it is also positive semi-definite for $c>c_0$ as well. From these parts and properties of PSD matrices under addition, scaling and products of commuting factors, you can finish the proof.
