EF Exercises

Skip to main content

Exercises 11.6 Exercises

1.

Compute each of the terms

s_{2}, s_{3}, s_{4}, s_{5}, s_{6}

for the sequence defined recursively by

s_{n} = \sqrt{s_{n - 2}^{2} + s_{n - 1}^{2}}, n \geq 2,

with initial terms

s_{0} = 3

and

s_{1} = 4 .

Solving by iteration.

In each of Exercises 2–8, use iteration to determine an expression for the

n^{th}

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{matrix} 1 + 2 + 3 + \dots + m = \frac{m (m + 1)}{2} \\ 1^{2} + 2^{2} + 3^{2} + \dots + m^{2} = \frac{m (m + 1) (2 m + 1)}{6} \\ r^{0} + r^{1} + r^{2} + \dots + r^{m - 1} = \frac{r^{m} - 1}{r - 1}, r \neq 0, 1 \end{matrix}

2.

a_{n} = 2 n a_{n - 1},

a_{0} = 1 .

3.

a_{n} = (2 n - 1) a_{n - 1},

a_{0} = 1 .

4.

a_{n} = a_{n - 1} + 3^{n - 1},

a_{0} = 1 .

5.

a_{n} = a_{n - 1} + n - 1,

a_{0} = 1 .

6.

a_{n} = a_{n - 1} + n + n^{2},

a_{0} = 1 .

7.

a_{n} = f (a_{n - 1}),

where

f (x)

is the linear function

f (x) = m x + b

for some fixed constants

m, b,

and with arbitrary initial term

a_{0} .

8.

a_{n} = 4 a_{n - 2},

n \geq 2,

a_{0} = 1,

a_{1} = 2 .

Treat the cases

n

even and

n

odd separately.

9.

Fibonacci numbers are those that appear in the sequence defined recursively by

\begin{aligned} a_{n} & = a_{n - 1} + a_{n - 2}, & n & \geq 2, \end{aligned}

for some choice of initial terms

a_{0}, a_{1} .

Using initial terms

a_{0} = a_{1} = 1,

use mathematical induction to prove that every Fibonacci number

a_{n}

satisfies

a_{n} < 2^{n}

(except, of course, for

a_{0} .

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 = 100 i,

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

n^{th}

year relative to the previous year.

(b)

Use iteration to determine an expression for the population in the

n^{th}

year as a formula in

n,

i,

and the initial population

P_{0} .

(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},

and use iteration to determine an expression for the population in the

n^{th}

year as a formula in

n,

i,

A,

and the initial population

P_{0} .

11.

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.

(p_{1} \land p_{2}) \to ((\neg p_{3} \lor p_{1}) \leftrightarrow (p_{3} \land \neg p_{2}))

12.

The set

C

of constructible numbers can be defined inductively as follows.

Base clause.

Assume

1 \in C .

Inductive clauses.

🔗
Whenever $a, b \in C,$ then so are
$a + b, a b, a / b, \sqrt{a} .$
🔗
Whenever $a, b \in 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

2 x^{2} - 3 x + \frac{7}{8}

are both constructible numbers.

13.

Consider the following inductively defined set

A \subseteq N .

Base clause.

Assume

32879 \in 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 .

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 \neq n,$ is $m > n$ or is $n > m$ ?

<Prev ^Top Next>