11.6: Exercises
( \newcommand{\kernel}{\mathrm{null}\,}\)
Compute each of the terms s2,s3,s4,s5,s6 for the sequence defined recursively by
sn=√s2n−2+s2n−1,n≥2,
with initial terms s0=3 and s1=4.
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.
1+2+3+⋯+m=m(m+1)212+22+32+⋯+m2=m(m+1)(2m+1)6r0+r1+r2+⋯+rm−1=rm−1r−1,r≠0,1
an=2nan−1, a0=1.
an=(2n−1)an−1, a0=1.
an=an−1+3n−1, a0=1.
an=an−1+n−1, a0=1.
an=an−1+n+n2, a0=1.
an=f(an−1), where f(x) is the linear function f(x)=mx+b for some fixed constants m,b, and with arbitrary initial term a0.
an=4an−2, n≥2, a0=1, a1=2.
- Hint.
-
Treat the cases n even and n odd separately.
Fibonacci numbers are those that appear in the sequence defined recursively by
an=an−1+an−2,n≥2,
for some choice of initial terms a0,a1.
- See.
Using initial terms a0=a1=1, use mathematical induction to prove that every Fibonacci number an satisfies an<2n (except, of course, for a0.
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, 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.)
- Write down a recurrence relation that expresses the population Pn in the nth year relative to the previous year.
- Use iteration to determine an expression for the population in the nth year as a formula in n, i, and the initial population P0.
- 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 Pn, and use iteration to determine an expression for the population in the nth year as a formula in n, i, A, and the initial population P0.
Explicitly describe how to construct the following logical statement in a finite number of steps using the inductive definition for L, the set of all possible logical statements, given in Example 11.4.1.
(p1∧p2)→((¬p3∨p1)⇔(p3∧¬p2))
The set C of constructible numbers can be defined inductively as follows.
Base clause.
Assume 1∈C.
Inductive clauses.
Whenever a,b∈C, then so are
a+b,ab,a/b,√a.
Whenever a,b∈C with a>b, then a−b is also in C.
Limiting clause.
The set 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 2x2−3x+78 are both constructible numbers.
Consider the following inductively defined set A⊆N.
Base clause.
Assume 32879∈A.
Inductive clauses.
When a is an element of A, then each of the prime factors of a is also an element of A.
Whenever prime p is an element of A, then p+1 is also an element of A.
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.
- Hint.
-
To help with this question, you may wish to search for “list of small primes” on the internet.
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∈N with m≠n, is m>n or is n>m ?