Define a symmetric Toeplitz matrix by
H = \begin{bmatrix} 2k(0) & k(s) & k(2s) & \dots & k(NS) \\ k(s) & 2k(0) & k(s) & \dots & k((N-1)S) \\ k(2s) & k(s) & 2k(0) & \dots & k((N-2)S) \\ \vdots & \vdots & \vdots & \ddots \\ k(Ns) & k((N-1)s) & k((N-2)s) & \dots & 2k(0) \end{bmatrix}
k(.) is non-increasing function. e.g k(x) = $e^{-x}$
s, N are known constant.
How to prove that this matrix is positive-definite? Thanks a lot.
This is not true. Consider the $n\times n$ penta-band symmetric Toeplitz matrix $$ \pmatrix{ 2&1&1\\ 1&\ddots&\ddots&\ddots\\ 1&\ddots&\ddots&\ddots&\ddots\\ &\ddots&\ddots&\ddots&\ddots&1\\ & &\ddots&\ddots&\ddots&1\\ & & &1&1&2}. $$ It has positive, negative and zero eigenvalues when $n=11$.
An $n\times n$ matrix $A$ is guaranteed to be positive definite if $a_{ij}=\varphi\left(\|x_i-x_j\|^2\right)$ for some completely monotone function $\varphi:[0,\infty)\to\mathbb R$ (i.e. a function such that $(-1)^m\frac{d^m\varphi}{dx^m}\ge0$ on $(0,\infty)$ for every $m\ge0$) and some set of distinct points $\{x_1,\ldots,x_n\}$ in some Euclidean space $\mathbb R^s$. This is known as Schoenberg interpolation theorem, which is a consequence of Bochner's characterisation of positive definite functions. See chapter 15 of A Course in Approximation Theory by Cheney and Light or sec. 2.5 of this book chapter for more details.
In your case, $\varphi(x)=e^{-\sqrt{x}}$ is known to be completely monotone. So, with this function $\varphi$, $A=H-k(0)I$ is positive definite and so is $H$.