Proof for Minimum number of insertions to convert a string to a palindrome
As D.W. indicates, you use proof by induction. I'll explain this with some hints on the case $S[i] = S[j]$. The intuition is that if $S[i] = S[j]$ then the best way of converting $S[i],\ldots,S[j]$ into a palindrome is converting $S[i+1],\ldots,S[j-1]$ into one, and then converting this to a solution for $S[i],\ldots,S[j]$ at no further cost (how?).

Formally, we need to prove two things:


$c[i,j] \leq c[i+1,j-1]$.
$c[i,j] \geq c[i+1,j-1]$.


For the first inequality, you need to show that if you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting $m$ characters, then you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting at most $m$ characters. You get the first inequality by taking $m = c[i+1,j-1]$. The proof is not difficult and left to you.

The second inequality is more delicate. Now you need to show that if you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting $m$ characters then you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting at most $m$ characters. To show this, consider the insertions converting $S[i],\ldots,S[j]$ into a palindrome:
$$
w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j],w_j.
$$
Here the $w_t$'s are words which may be empty. 


  Claim: We can modify this solution to a solution with possibly less insertions in which at least one of $w_{i-1},w_j$ is empty.


(Proof left to you.)
If both $w_{i-1},w_j$ are empty then it is easy to complete the proof (details left to you). Otherwise, suppose without loss generality that $w_j$ is empty, that is, the insertions are

$$
w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j].
$$

Since $w_{i-1}$ is non-empty and the word is a palindrome, it must start with $S[j]=S[i]$. Writing $w_{i-1} = S[j] x$, we can rewrite this solution as

$$
S[i],x,S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j].
$$

I'll let you finish the proof of this case from here, and to mimic this proof for the case $S[i] \neq S[j]$.