1.
Compute each of the terms \(s_2,s_3,s_4,s_5,s_6\) for the sequence defined recursively by
\begin{equation*}
s_n = \sqrt{s_{n-2}^2 + s_{n-1}^2}, \quad n \ge 2,
\end{equation*}
with initial terms \(s_0 = 3\) and \(s_1 = 4\text{.}\)
Exercises 11.6 Exercises
Solving by iteration.
In each of Exercises 2–8, use iteration to determine an expression for the \(\nth\) term of the sequence as a formula in \(n\) (and the initial term(s) of the sequence, if necessary).
In some of these, you may find the following formulas useful.
\begin{gather*}
1 + 2 + 3 + \dotsb + m = \frac{m (m+1)}{2} \\
1^2 + 2^2 + 3^2 + \dotsb + m^2 = \frac{m (m+1) (2m+1)}{6} \\
r^0 + r^1 + r^2 + \dotsb + r^{m-1} = \frac{r^m - 1}{r - 1}, \quad r \ne 0,1
\end{gather*}
2.
\(a_n = 2na_{n-1}\text{,}\) \(a_0 = 1 \text{.}\)
3.
\(a_n = (2n-1)a_{n-1}\text{,}\) \(a_0 = 1 \text{.}\)
4.
\(a_n = a_{n-1} + 3^{n-1}\text{,}\) \(a_0 = 1 \text{.}\)
5.
\(a_n = a_{n-1} + n - 1\text{,}\) \(a_0 = 1 \text{.}\)
6.
\(a_n = a_{n-1} + n + n^2\text{,}\) \(a_0 = 1 \text{.}\)
7.
\(a_n = f(a_{n-1})\text{,}\) where \(f(x)\) is the linear function \(f(x) = mx + b \) for some fixed constants \(m,b\text{,}\) and with arbitrary initial term \(a_0\text{.}\)
8.
\(a_n = 4a_{n-2}\text{,}\) \(n \ge 2 \text{,}\) \(a_0 = 1 \text{,}\) \(a_1 = 2\text{.}\)
Hint.
Treat the cases \(n\) even and \(n\) odd separately.
9.
Fibonacci numbers are those that appear in the sequence defined recursively by
\begin{align*}
a_n \amp = a_{n-1} + a_{n-2}, \amp n \amp \ge 2 \text{,}
\end{align*}
for some choice of initial terms \(a_0, a_1\text{.}\)
Using initial terms \(a_0 = a_1 = 1\text{,}\) use mathematical induction to prove that every Fibonacci number \(a_n\) satisfies \(a_n \lt 2^n\) (except, of course, for \(a_0\text{.}\)
10.
You are attempting to predict population dynamics on a yearly basis.
Suppose a population increases by a factor of \(i\) each year. That is, if we set \(p=100i\text{,}\) then the population increases by \(p\) percent. (Careful: This is a description of the increase in population, not the total population. For example, \(i = 1\) means that the population doubles.)
(a)
Write down a recurrence relation that expresses the population \(P_n\) in the \(\nth\) year relative to the previous year.
(b)
Use iteration to determine an expression for the population in the \(\nth\) year as a formula in \(n\text{,}\) \(i\text{,}\) and the initial population \(P_0\text{.}\)
(c)
Suppose that on top of the natural population increase of \(i\) percent per year, immigration increases the population by fixed amount \(A\) people annually. Design a new recurrence relation for \(P_n\text{,}\) and use iteration to determine an expression for the population in the \(\nth\) year as a formula in \(n\text{,}\) \(i\text{,}\) \(A\text{,}\) and the initial population \(P_0\text{.}\)
11.
Explicitly describe how to construct the following logical statement in a finite number of steps using the inductive definition for \(\mathscr{L}\text{,}\) the set of all possible logical statements, given in Example 11.4.1.
\begin{equation*}
(p_1 \lgcand p_2) \lgccond
\bbrac{ (\lgcnot p_3 \lgcor p_1) \lgcbicond (p_3 \lgcand \lgcnot p_2 ) }
\end{equation*}
12.
The set \(\mathscr{C}\) of constructible numbers can be defined inductively as follows.
Base clause.
Assume \(1 \in \mathscr{C}\text{.}\)
Inductive clauses.
- Whenever \(a,b \in \mathscr{C}\text{,}\) then so are\begin{equation*} a+b, \quad ab, \quad a/b, \quad \sqrt{a} \text{.} \end{equation*}
- Whenever \(a,b \in \mathscr{C}\) with \(a>b\text{,}\) then \(a-b\) is also in \(\mathscr{C}\text{.}\)
Limiting clause.
The set \(\mathscr{C}\) contains no elements other than those that can be obtained through a finite number of applications of the base and/or inductive clauses.
Explicitly verify, by listing each application of the relevant clauses, that the roots of the polynomial \(2x^2 - 3x + \frac{7}{8}\) are both constructible numbers.
13.
Consider the following inductively defined set \(A \subseteq \N\text{.}\)
Base clause.
Assume \(32879 \in A\text{.}\)
Inductive clauses.
- When \(a\) is an element of \(A\text{,}\) then each of the prime factors of \(a\) is also an element of \(A\text{.}\)
- Whenever prime \(p\) is an element of \(A\text{,}\) then \(p+1\) is also an element of \(A\text{.}\)
Limiting clause.
The set \(A\) contains no elements other than those that can be obtained through a finite number of applications of the base and/or inductive clauses.
Determine all elements of \(A\text{.}\)
Hint.
To help with this question, you may wish to search for “list of small primes” on the internet.
14.
Devise an algorithm that will produce an answer to the following question in a finite number of applications of the inductive clause that we used to define the natural numbers in Example 11.4.2.
Given \(m,n \in \N\) with \(m \ne n\text{,}\) is \(m \gt n\) or is \(n \gt m\) ?
