Question

Show that each of these proposed recursive definitions of a function on the set of positive integers does not produce a well-defined function.

$\begin{array}{r}\mathbf{F}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{F}\mathbf{(}\mathbf{\lfloor }\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{/}\mathbf{2}\mathbf{\rfloor }\mathbf{)}\mathbf{\text{for}}\mathbf{n}\mathbf{\ge }\mathbf{1}\mathbf{\text{and}}\mathbf{F}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{1}\\ \mathbf{F}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{F}\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{2}\mathbf{)}\mathbf{\text{for}}\mathbf{n}\mathbf{\ge }\mathbf{2}\mathbf{\text{, and}}\mathbf{F}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{0}\\ \mathbf{F}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{F}\mathbf{(}\mathbf{n}\mathbf{/}\mathbf{3}\mathbf{)}\mathbf{\text{for}}\mathbf{n}\mathbf{\ge }\mathbf{3}\mathbf{,}\mathbf{F}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{1}\mathbf{,}\mathbf{F}\mathbf{\left(}\mathbf{2}\mathbf{\right)}\mathbf{=}\mathbf{2}\mathbf{\text{and}}\mathbf{F}\mathbf{\left(}\mathbf{3}\mathbf{\right)}\mathbf{=}\mathbf{3}\\ \mathbf{F}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{F}\mathbf{(}\mathbf{n}\mathbf{/}\mathbf{2}\mathbf{)}\mathbf{\text{if}}\mathbf{n}\mathbf{\text{is even and}}\mathbf{n}\mathbf{\ge }\mathbf{2}\\ \mathbf{F}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{F}\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{2}\mathbf{)}\mathbf{\text{if}}\mathbf{n}\mathbf{\text{is odd,}}\mathbf{F}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{1}\\ \mathbf{F}\mathbf{\left(}\mathbf{n}\mathbf{\right)}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{F}\mathbf{\left(}\mathbf{F}\mathbf{\right(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{\left)}\mathbf{\right)}\mathbf{\text{if}}\mathbf{n}\mathbf{\ge }\mathbf{2}\mathbf{\text{and}}\mathbf{F}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{2}\end{array}$

Short answer

1. It is does not produce a well-defined function.
2. The function is not well-defined.
3. The function is not well-defined.
4. is not defined because is not defined.
5. The function is not well-defined.

Step-by-step solution

Introduction

A recursive function is a function that its value at any point can be calculated from the values of the function at some previous points.

(a) Find  F (n) = 1 + F [n + 1 / 2]

Let us consider the following function

$\mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}\left(\left[\frac{\mathrm{n}+1}{2}\right]\right)\text{for}\mathrm{n}\ge 1\text{and}\mathrm{F}\left(1\right)=1$

For n = 1

$\begin{array}{r}\mathrm{F}\left(1\right)=1+\mathrm{F}\left(⌊\frac{1+1}{2}⌋\right)\\ \mathrm{F}\left(1\right)=1+\mathrm{F}(\lfloor 1\rfloor )\\ \mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}\left(1\right)\end{array}$

But F (1) is undefined

Thus, it is does not produce a well-defined function

(b) Find  F (n) = 1 +F (n - 2)

Consider a function

$$\begin{gathered} \mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}(\mathrm{n}-2) \\ \mathrm{For}\mathrm{n}=2 \\ \mathrm{F}\left(2\right)=1+\mathrm{F}(2-2) \\ =1+\mathrm{F}\left(0\right) \end{gathered}$$

So, F (2) is not defined because F (0) is not defined.

Therefore, the function is not well-defined.

(c) Find  F (n) = 1 + F (n / 3)

Consider a function

$\begin{array}{r}\mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}\left(\frac{\mathrm{n}}{3}\right)\text{for}\mathrm{n}\ge 3\text{and}\\ \begin{array}{rl}\mathrm{F}\left(1\right)=& 1,\mathrm{F}\left(2\right)=2\text{, and}\mathrm{F}\left(3\right)=3\\ & \mathrm{For}\mathrm{n}=3\\ \mathrm{F}\left(3\right)& =3+\mathrm{F}\left(\frac{3}{3}\right)\\ & =3+\mathrm{F}\left(1\right)\\ & =3+1\\ & =4\end{array}\end{array}$

The existence of value of F (3) is not possible because F (3) = 3 and F (3) = 4

Therefore, the function is not well-defined.

(d) Find  F(n) = 1 + F (n/2)

Consider a function

$\begin{array}{r}\mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}\left(\frac{\mathrm{n}}{2}\right)\text{if}\mathrm{n}\text{is even and}\mathrm{n}\ge 2\text{and}\\ \mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}(\mathrm{n}-2)\text{if}\mathrm{n}\text{is odd and}\mathrm{F}\left(1\right)=1\\ \mathrm{If}\mathrm{n}\mathrm{is}\mathrm{even}:\\ \mathrm{For}\mathrm{n}=2\\ \mathrm{F}\left(2\right)=1+\mathrm{F}\left(\frac{2}{2}\right)\left(\therefore \mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}\left(\frac{\mathrm{n}}{2}\right)\right)\\ =1+\mathrm{F}\left(1\right)\end{array}$

So, F (2) is not defined because F (1) is not defined.

(e) Find  F(n) = 1 + F (n-1)

Consider a function

$\begin{array}{r}\mathrm{F}\left(\mathrm{n}\right)=1+\mathrm{F}\left(\mathrm{F}\right(\mathrm{n}-1\left)\right)\text{for}\mathrm{n}\ge 2\text{and}\mathrm{F}\left(1\right)=2\\ \mathrm{For}\mathrm{n}=2\\ \mathrm{F}\left(2\right)=1+\mathrm{F}\left(\mathrm{F}\right(2-1\left)\right)\\ =1+\mathrm{F}\left(\mathrm{F}\right(1\left)\right)\\ =1+\mathrm{F}\left(2\right)(\therefore \mathrm{F}(1)=2)\end{array}$

It follows that F(2) = 1 + F (2)

This is not defined.

Therefore, the function is not well-defined.