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]$.
