# Show that the recursively defined function z is neither surjective or injective

• Nov 12th 2012, 03:25 PM
sakuraxkisu
Show that the recursively defined function z is neither surjective or injective
My question is:

The function z from $\mathbb{N}$ to $\mathbb{N}$ is defined recursively by:

z(1)=1 and

$z(n+1) = \begin{cases} 1/2(z(n)+3), & \text{if }z(n)\text{ is odd} \\ z(n)+5, & \text{if }z(n)\text{ is even} \end{cases}$

for all $n\geq 1$.

Show that z is neither an injection or a surjection.

What I've done so far is find the first couple of values of z(n) up to n=7, where I got z(2)=2, z(3)=7, z(4)=5, z(5)=4, z(6)=9, and z(7)=6. At this point, I'm not sure about what to do, so any help would be greatly appreciated!
• Nov 12th 2012, 04:17 PM
ModusPonens
Re: Show that the recursively defined function z is neither surjective or injective
z(9)=z(3), so it's not injective.

From 9 onwards, the sequence is periodic, because z(3+k+6n)=z(3+k), so it's not surjective.
• Nov 13th 2012, 03:10 AM
sakuraxkisu
Re: Show that the recursively defined function z is neither surjective or injective
I'm a bit confused about k, could you explain how you got z(3+k+6n) and z(3+k)? Thank you