Section 7: Problem 9 Solution

Working problems is a crucial part of learning mathematics. No one can learn topology merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

This exercise shows that one has to be careful in defining recursive functions, as an arbitrary recursive relation may “define” several functions or a function that does not exist.

(a) The formula $\begin{array}{cccclcc} & & h(1) & = & 1,\\ (\ast) & & h(2) & = & 2,\\ & & h(n) & = & [h(n+1)]^{2}-[h(n-1)]^{2} & & \mbox{ for }n\ge2 \end{array}$ is not one to which the principle of recursive definition applies. Show that nevertheless there does exist a function $h:\mathbb{Z}_{+}\rightarrow\mathbb{R}$ satisfying this formula. [Hint: Reformulate $(\ast)$ so that the principle will apply and require $h$ to be positive.]

(b) Show that the formula $(\ast)$ of part (a) does not determine $h$ uniquely. [Hint: If $h$ is a positive function satisfying $(\ast)$ , let $f(i)=h(i)$ for $i\neq3$ , and let $f(3)=-h(3)$ .]

(c) Show that there is no function $h:\mathbb{Z}_{+}\rightarrow\mathbb{R}$ satisfying the formula $\begin{array}{cccclcc} & & h(1) & = & 1,\\ \,\,\, & & h(2) & = & 2,\\ & & h(n) & = & [h(n+1)]^{2}+[h(n-1)]^{2} & & \mbox{ for }n\ge2. \end{array}$

(a) The last expression can be rewritten as $[h(n+1)]^{2}=h(n)+[h(n-1)]^{2}$ . By taking the positive root we ensure that $h$ takes positive values only, and, hence, always exists (as the sum of the two terms on the right will be always positive). In other words, we rewrite the last expression as $h(n)=\sqrt{h(n-1)+[h(n-2)]^{2}}$ for $n\ge3$ . Now, the recursive formula is well-defined, and the principle of recursive definition applies to it.

(b) Let $h$ and $f$ be two functions both satisfying the recursive relation described by

such that $h(1)=f(1)=1$ , $h(2)=f(2)=2$ , $h(3)=\sqrt{3}$ , $f(3)=-\sqrt{3}$ , and for $n\ge4$ , $\begin{array}{c} h\\ f \end{array}(n)=\sqrt{\begin{array}{c} h\\ f \end{array}(n-1)+\left[\begin{array}{c} h\\ f \end{array}(n-2)\right]^{2}}$ (I am not sure why Munkres says $f(i)=h(i)$ for $i\neq3$ ).

Subpages

Section 7: Problem 9 Solution

Section 7: Problem 9 Solution