Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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*}$$

share|cite|improve this question
Could it be that $\dfrac12n$ was intended where $\dfrac12$ appears in the piecewise definition of $g$? – Michael Hardy Jan 13 '13 at 1:44
Note that $g$ is not the same function as $f$: $g(3)=1$, but $f(3)=10$. – Brian M. Scott Jan 13 '13 at 1:46
Ah, I did indeed miss out the 'n's! I see that f and g obviously don't do the same thing, but it is presumably no coincidence that g has been written in the way that it has. I think I'll sleep on that and take another look at it tomorrow(!) – Seraphina Jan 13 '13 at 2:15
up vote 1 down vote accepted

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?

share|cite|improve this answer
Thanks so much for your answer. I think I can see the thinking behind this now- well, I get how the algebra works anyway, and mostly get the rest of it... In answer to your questions- I am referring to f in the context of inferring the parity of n, i.e. $\chi_E$ This is what I meant by f and g doing the same thing. The overall topic in the textbook that I'm reading is 'characteristic functions'. Just one more thought- presumably $\chi_E$ would only be valid for the two cases 'n even' and 'n odd'? – Seraphina Jan 13 '13 at 13:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.