How to prove that a function is non-negative definite? The function I am trying to prove is $\exp(-2\lvert j-k\rvert)$.
Here is what I  have tried; 
$\sum_{j=1}^n \sum_{k=1}^n\ a_j \bar{a_k}\exp(-2\lvert j-k\rvert)$
=$\sum_{j=1}^n \sum_{k=1}^n\ a_j \bar{a_k}\exp(-2\lvert j-k\rvert)$
=$\sum_{j>k} \ a_j \bar{a_k}\exp(-2j)\exp(2k)+\sum_{k>j} \ a_j \bar{a_k}\exp(2j)\exp(-2k) + \sum_{j=k} \lvert a_j\rvert^2$
but I am not sure if it is the right path or not. 
 A: This answer follows the lines of the proof of Bochner's theorem that I mentioned in the comment. Since $$
e^{-2|\xi|}=\frac1{\pi}\int_{-\infty}^\infty e^{-2i \xi t}\frac{dt}{1+t^2},
$$ we have
$$\begin{align*}
\sum_{j,k}a_j\bar a_ke^{-2|x_j-x_k|}&=\frac1{\pi}\int_{-\infty}^\infty \sum_{j,k}a_j\bar a_ke^{-2i (x_j-x_k) t}\frac{dt}{1+t^2}\\&=\frac1{\pi}\int_{-\infty}^\infty \left|\sum_j a_j e^{-2ix_jt}\right|^2\frac{dt}{1+t^2}\\&\ge 0.
\end{align*}$$ So $x\mapsto e^{-2|x|}$ is non-negative definite.
Note: What you indeed need to show is $\sum_{j,k}a_j\bar a_ke^{-2|x_j-x_k|}\ge 0$ for every $(a_j)_{j=1}^n$ and $(x_j)_{j=1}^n$. We cannot restrict to $x_j=j$.
A: Terminology: The inequality you're trying to prove actually says that the function $e^{-2|j|}$ is positive definite on $\Bbb Z$.
I think the "best" proof is by the trivial half of Bochner's Theorem, as in the other answer. But you can also do it directly.
Notation: To save typing I'm going to write $$f(t)=e^{-2|t|}$$and $$\alpha=\sum|a_j|^2.$$
Note that $$\sum_{j,k}a_j\overline{a_k}f(j-k)=\alpha+\left(\sum_{n=-\infty}^{-1}+\sum_{n=1}^\infty\right)f(n)\sum_ja_j\overline{a_{j+n}}.$$
Cauchy-Schwarz shows that $$\left|\sum_ja_j\overline{a_{j+n}}\right|\le\alpha,$$
which gives $$\sum_{j,k}a_j\overline{a_k}f(j-k)\ge\alpha\left(1-2\sum_{n=1}^\infty f(n)\right).$$So you're done if $$1-2\sum_1^\infty f(n)>0,$$which is true if I added the geometriic series correctly.
