Let $a$ be the first digit of the string, and let $b$ be
the value of the remaining digits. Let's prove that the
operation is reducing with respect to the lexical order of
$\langle a,b\rangle$, which is one version of interpreting
your phrase "double induction."
First, note that the operation of inserting the $0$ to the
right of the leading digit affects neither the value of $a$
nor $b$.
Next, note that if $b$ is all zero but $a$ is not $0$, then
the operation will end up with $a$ being reduced, because
when you subtract one, you will have to borrow from $a$,
thereby reducing. Thus, the operation will result with a
string having lower $\langle a,b\rangle$ in the lexical
order.
If $b$ is not all zero, however, then the operation will
end up with the $b$ value being value $1$ less (despite the
extra $0$), and so will reduce $\langle a,b\rangle$ in the
lexical order.
Since the lexical order on $\mathbb{N}\times\mathbb{N}$ is a well-order, it follows that
the operation must eventually hit all $0$s.
The argument shows that you can insert any number of $0$s, rather than just one $0$ at each step, although if you insert more, then it will take longer to get to the all $0$ string, since when you borrow, you will get more $9$s.
Two methods:
Direct Approach: To make a palindrome of length $2n$ we may choose the first $n$ however we like, then repeat the string backwards. But there are $2$ ways to choose the first character, $2$ ways to choose the second, up to $2$ ways to choose the $n^{th}$ so there are $2^*2^*\dots^*2=2^n$ ways to do it.
Induction: It is easy to verify the formula for small $n$ (but you should be sure to do it!). Assume we have done it for $n-1$. Thus we know there are $2^{n-1}$ palindromic strings of length $2(n-1)$. Now, to make a palindromic string of lenght $2n$ we choose one of length $2(n-1)$ and select a character (either $1$ or $0$) to surround it (one in front, one at the end). There are, by induction, $2^{n-1}$ ways to choose the string of length $2(n-1)$ and $2$ ways to choose the surrounding character so all in all there are $2^*2^{n-1}=2^n$ ways to make our string of length $2n$, as desired.
Best Answer
Start your induction with the empty string, which I’ll call $\epsilon$ (you may use $\lambda$ for this): prove that $\big(\mbox{oc}(\epsilon)\big)^R=\mbox{oc}(\epsilon^R)$.
For the induction step note that every non-empty string in $\{0,1\}^*$ is of the form $w0$ or $w1$ for some $s\in\{0,1\}^*$. Assuming as your induction hypothesis that $\big(\mbox{oc}(w)\big)^R=\mbox{oc}(w^R)$, prove that $\big(\mbox{oc}(w0)\big)^R=\mbox{oc}\big((w0)^R\big)$ and a similar result for $w1$.
I’ve case this as a structural induction, but you could also do it as an ordinary induction on the length of the string.