Exercise 7.9

Question

\def\condgap{\hspace{1cm}}
\begin{enumerate}[label=(\alph*)]
\item The formula
\begin{align*}
& & h(1) &= 1\,, \
&(*) & h(2) &= 2\,, \
& & h(n) &= [h(n+1)]^2 - [h(n-1)]^2 \condgap 	ext{for $n \geq 2$}
\end{align*}
is not one to which the principle of recursive definition applies.
Show that nevertheless there does exist a function $h : {{\mathbb{Z}}_+} 	o {\mathbb{R}}$ satisfying this formula.
[Hint: Reformulate $(*)$ so that the principle will apply and require $h$ to be positive.]
\item Show that the formula $(*)$ of part~(a) does not determine $h$ uniquely.
[Hint: If $h$ is a positive function satisfying $(*)$, let $f(i) = h(i)$ for $i 
eq 3$, and let $f(3) = -h(3)$.]
\item Show that there is no function $h: {{\mathbb{Z}}_+} 	o {\mathbb{R}}$ satisfying the formula
\begin{align*}
h(1) &= 1 \,, \
h(2) &= 2 \,, \
h(n) &= [h(n+1)]^2 + [h(n-1)]^2 \condgap 	ext{for $n \geq 2$.}
\end{align*}
\end{enumerate}

Dan Whitman · Accepted Answer

\def\condgap{\hspace{1cm}} (a) First, notice that $(*)$ does not satisfy the principle of recursive definition because, for $n \geq 2$, $h(n)$ is not defined strictly in terms of values of $h$ for positive integers less than $n$, since its definition depends on $h(n+1)$. Now we show that there does exist a function satisfying $(*)$. \begin{proof} Consider the following reformulation: \begin{align*} h(1) &= 1\,, \ h(2) &= 2\,, \ h(n) &= \sqrt{h(n-1) + [h(n-2)]^2} \condgap ext{for $n > 2$}\,, \end{align*} where as a convention we take the positive square root for $h(n)$. Clearly for $n \in \left\{1,2 ight\}$ we have that $h(n)$ is positive. Now suppose $n > 2$ and that $h(k)$ is positive for $k < n$ so that $h(n-1)$ and $h(n-2)$ are both positive. Then clearly $h(n-1) + [h(n-2)]^2$ is positive so that $h(n) = \sqrt{h(n-1) + [h(n-2)]^2}$ is defined and is positive. Hence $h(n)$ is positive and well-defined for all $n \in {{\mathbb{Z}}_+}$ by induction. Thus, since $h(n)$ depends only on values of $h$ for integers less than $n$, this satisfies the recursion principle so that a unique $h$ satisfying the above exists. We also claim that this $h$ satisfies $(*)$. Clearly, the explicitly defined values of $h(1)$ and $h(2)$ are satisfied. For $n \geq 2$, we have that $n+1 > 2$ so that, by definition, \begin{gather*} h(n+1) = \sqrt{h((n+1)-1) + [h((n+1)-2)]^2} = \sqrt{h(n) + [h(n-1)]^2} \ [h(n+1)]^2 = h(n) + [h(n-1)]^2 \ h(n) = [h(n+1)]^2 - [h(n-1)]^2 \,, \end{gather*} which is the final constraint of $(*)$ so that it is also satisfied since $n \geq 2$ was arbitrary. \end{proof} (b) First note that for the recursively defined function $h$ from part~(a), \begin{align*} h(3) &= \sqrt{h(2) + [h(1)]^2} = \sqrt{2 + 1^2} = \sqrt{3} \ h(4) &= \sqrt{h(3) + [h(2)]^2} = \sqrt{\sqrt{3} + 2^2} = \sqrt{\sqrt{3} + 4} \,. \end{align*} Now define the function $f$ as in the hint, that is $f(i) = h(i)$ for $i eq 3$ and $f(3) = -h(3)$. Then we clearly have $f(3) = -h(3) = -\sqrt{3}$ while \begin{gather*} [f(4)]^2 - [f(2)]^2 = [h(4)]^2 - [h(2)]^2 = \left(\sqrt{\sqrt{3} + 4} ight)^2 - 2^2 = \sqrt{3} + 4 - 4 = \sqrt{3} \end{gather*} so that $f(n) = -\sqrt{3} eq \sqrt{3} = [f(n+1)]^2 - [f(n-1)]^2$ for $n = 3$, and hence $(*)$ is violated. So it would seem that the hint as given does not exactly work. Now we show that the function satisfying $(*)$ is not unique, taking inspiration from the hint. \begin{proof} We construct a function $f$, different from $h$ from part~(a), that also satisfies $(*)$. We define $f$ using recursion: \begin{align*} f(1) &= 1\,, \ f(2) &= 2\,, \ f(3) &= -\sqrt{3}\,, \ f(n) &= \sqrt{f(n-1) + [f(n-2)]^2} \condgap ext{for $n > 3$}\,. \end{align*} Clearly, since each $f(n)$ is defined only in terms of $f(k)$ for $k < n$ (or without dependence on any values of $f$), $f$ exists uniquely by the recursion principle so long as each $f(n)$ is well-defined. We show this presently by induction. Clearly $f(n)$ is defined for $n \in \left\{1,2,3 ight\}$. For $n=4$ we have $f(n) = f(4) = \sqrt{f(3) + [f(2)]^2} = \sqrt{-\sqrt{3} + 2^2} \sqrt{-\sqrt{3} + 4}$. Now, since $1 < 3$, we have that $\sqrt{3} < 3 < 4$ so that $-\sqrt{3} + 4 = 4 - \sqrt{3} > 0$ and hence the square root, and therefore $f(4)$, is defined and positive. Now consider any $n > 4$ and suppose that $f(n-1)$ is positive. Then clearly $f(n) = \sqrt{f(n-1) + [f(n-2)]^2}$ is defined and positive since $f(n-1) > 0$, noting that even if $f(n-2) \leq 0$, its square is non-negative.. This completes the induction that shows that $f$ is uniquely defined. Clearly $f eq h$ since $f(3) = -\sqrt{3} eq \sqrt{3} = h(3)$. Also obviously $f(n)$ satisfies $(*)$ explicitly for $n \in \left\{1,2 ight\}$. For $n = 2$ we have \begin{gather*} [f(n+1)]^2 - [f(n-1)]^2 = [f(3)]^2 - [f(1)]^2 = [-\sqrt{3}]^2 - 1^2 = 3-1 = 2 = f(n) \,. \end{gather*} Then, for $n > 2$ we have $n+1 > 3$ so that, by definition, \begin{gather*} f(n+1) = \sqrt{f((n+1)-1) + [f((n+1)-2)]^2} = \sqrt{f(n) + [f(n-1)]^2} \ [f(n+1)]^2 = f(n) + [f(n-1)]^2 \ f(n) = [f(n+1)]^2 - [f(n-1)]^2 \,. \end{gather*} Thus the recursive part of $(*)$ holds for $n \geq 2$ so that $(*)$ holds over the whole domain of $f$ as desired. \end{proof} (c) \begin{proof} Suppose that such a function $h$ does exist. Since the recursive property holds for $n \geq 2$, we have \begin{gather*} h(2) = [h(3)]^2 + [h(1)]^2 \ 2 = [h(3)]^2 + 1^2 \ [h(3)]^2 = 2 - 1^2 = 1 \ h(3) = \pm 1 \,. \end{gather*} Similarly, we have \begin{gather*} h(3) = [h(4)]^2 + [h(2)]^2 \ \pm 1 = [h(4)]^2 + 2^2 \ [h(4)]^2 = \pm 1 - 2^2 = \pm 1 - 4 \end{gather*} so that either $[h(4)]^2 = 1 - 4 = -3$ or $[h(4)]^2 = -1-4 = -5$. In either case, we have $[h(4)]^2 < 0$, which is of course impossible since the square of a real number is always non-negative! So it must be that such a function does not exist. \end{proof}

Exercise 7.9

Answers

Comments

Exercise 7.9

Answers

Comments

Add answer