How to prove the existence and uniqueness of Cholesky decomposition?

A classical way is to use the induction. Let $A\in\mathbb{R}^{n\times n}$ be positive definite. It is trivial for $n=1$, just take the square root. Assume that a Cholesky factorization exists for positive definite matrices of dimension $n-1$ and partition $A$ as $$ A = \begin{bmatrix} \tilde{A}&a\\a^T&\alpha \end{bmatrix}, $$ where $\tilde{A}\in\mathbb{R}^{(n-1)\times(n-1)}$. Since a principal submatrix of a positive definite matrix is positive definite, $\tilde{A}$ has a Cholesky factorization $\tilde{A}=\tilde{L}\tilde{L}^T$. Consider $$\tag{1} L_1^{-1}AL_1^{-T} := \begin{bmatrix} \tilde{L}^{-1}&0\\ 0&1 \end{bmatrix} \begin{bmatrix} \tilde{A}&a\\ a^T&\alpha \end{bmatrix} \begin{bmatrix} \tilde{L}^{-T}&0\\ 0&1 \end{bmatrix} = \begin{bmatrix} I&b\\ b^T&\alpha \end{bmatrix} =:B, \quad b:=\tilde{L}^{-1}a. $$ Next we eliminate $b$ by $$\tag{2} L_2^{-1}BL_2^{-T} := \begin{bmatrix} I&0\\-b^T&1 \end{bmatrix} \begin{bmatrix} I&b\\ b^T&\alpha \end{bmatrix} \begin{bmatrix} I&-b\\0&1 \end{bmatrix} = \begin{bmatrix} I&0\\0&\alpha-b^Tb \end{bmatrix} = \begin{bmatrix} I&0\\0&\alpha-a^TA^{-1}a \end{bmatrix}. $$ The diagonal matrix on the right-hand side of (2) is a result of congruence transformations applied to $A$, so the right-hand side of (2) is positive definite and $0<\alpha-a^TA^{-1}a=\lambda^2$ for some real $\lambda$. Set $$ L_3:=\begin{bmatrix}I&0\\0&\lambda\end{bmatrix} $$ so $L_2^{-1}BL_2^{-T}=L_3L_3^T$. From (1) we have $$ L_2^{-1}L_1^{-1}AL_1^{-T}L_2^{-T}=L_3L_3^T, $$ so $$ A=LL^T, \quad L:=L_1L_2L_3 = \begin{bmatrix} \tilde{L}&0\\ 0&1 \end{bmatrix} \begin{bmatrix} I&0\\b^T&1 \end{bmatrix} \begin{bmatrix} I&0\\ 0&\lambda \end{bmatrix} = \begin{bmatrix} \tilde{L}&0\\ b^T&\lambda \end{bmatrix} = \begin{bmatrix} \tilde{L}&0\\ a^T\tilde{L}^{-T}&\lambda \end{bmatrix} $$ is a Cholesky factorization of $A$.

There is a source of non-uniqueness of the factorization in the choice of the sign of $\lambda$. As soon as one requires the signs of the diagonal terms of the Cholesky factors to be fixed (e.g., positive), the factorization is unique.

A simple way to confirm this can be made as follows. Assume $$ A=LL^T=MM^T $$ are two Cholesky factors of $A$. This gives $$\tag{3} I=L^{-1}MM^TL^{-T}=(L^{-1}M)(L^{-1}M)^T $$ and $$\tag{4} (L^{-1}M)=(L^{-1}M)^{-T}. $$ The left-hand and right-hand sides of (4) are, respectively, lower and upper triangular matrices which means that $D:=L^{-1}M$ is both lower and upper triangular and hence a diagonal matrix. From (3) we have $I=D^2$ so $D$ is a diagonal matrix with $\pm 1$ diagonal entries and $M=LD$ meaning that two Cholesky factors of $A$ differ by the signs of their columns.