Primitive recursive functions and characteristic functions. Methods of proof- examples. Illumination.

Question

I am puzzling over a sentence in an example in a textbook, showing that a function $f$, defined by cases, is primitive recursive.

Let $E$ be the set of even natural numbers. The function $f$ defined by

$$ f(n) = \begin{cases} \frac12n,&\text{if }n\in E\\\\ 3n + 1,& \text{if }n \notin E \end{cases}$$

is primitive recursive.

Now let $g: \mathbb{N} \longrightarrow \mathbb{N}$ be the function defined by

$$g(n)=\begin{cases} \frac12n,&\text{if }n\in E\\\\ \frac12(n-1),&\text{if }n\notin E\;. \end{cases}$$

My understanding is that the function $g$ has been picked, because it does the same thing as $f$, and also because it is easier to convert into primitive recursive form. Am I right?

This is the sentence that is puzzling me:

'We observe that $g(n+1) = g(n)$ if $n+1$ is odd and $g(n+1)=g(n)+1$ if $n+1$ is even'

I'm sure the thinking behind this is incredibly simple, and I've just experienced a moment of blindness. For example, has this observation come about through substitution, or am I looking at it the wrong way? Some illumination would be fantastic- and any alternative proofs. Just one final note- would I be right in understanding that there are lots of different ways of writing a function $f$ which determines whether $n$ is odd or even (defined by two cases)?

The proof concludes: we have $n+1 = \operatorname{succ}(n)$, so $g$ can be defined by the equations

$$\begin{align*} &g(0)=0\\ &g(n+1) = g(n) + \chi_E(\operatorname{succ}(n))\;. \end{align*}$$

Answer 1

If $n+1$ is odd, then $g(n+1)=\frac12\big((n+1)-1\big)=\frac12n=g(n)$, while if $n+1$ is even, then $g(n+1)=\frac12(n+1)=\frac12\big((n-1)+2\big)=\frac12(n-1)+1=g(n)+1$, since $n$ is odd.

However, $g$ and $f$ are clearly not the same function, as can be seen by evaluating them at any odd natural number. I’m not sure exactly what you mean by ‘a function $f$ which determines whether $n$ is odd or even (defined by two cases)’. Do you mean a function $f$ such that by looking at $f(n)$ (perhaps in conjunction with $n$) one can infer the parity of $n$, like $\chi_E$? Or do you simply mean one whose definition requires two cases, one to cover odd arguments and the other to cover even arguments?