Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

11.6: Exercises

( \newcommand{\kernel}{\mathrm{null}\,}\)

Exercise 11.6.1

Compute each of the terms s2,s3,s4,s5,s6 for the sequence defined recursively by

sn=s2n2+s2n1,n2,
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++rm1=rm1r1,r0,1

Exercise 11.6.2

an=2nan1, a0=1.

Exercise 11.6.3

an=(2n1)an1, a0=1.

Exercise 11.6.4

an=an1+3n1, a0=1.

Exercise 11.6.5

an=an1+n1, a0=1.

Exercise 11.6.6

an=an1+n+n2, a0=1.

Exercise 11.6.7

an=f(an1), where f(x) is the linear function f(x)=mx+b for some fixed constants m,b, and with arbitrary initial term a0.

Exercise 11.6.8

an=4an2, n2, a0=1, a1=2.

Hint.

Treat the cases n even and n odd separately.

Exercise 11.6.9

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

an=an1+an2,n2,
for some choice of initial terms a0,a1.

See.

Example 11.2.3.

Using initial terms a0=a1=1, use mathematical induction to prove that every Fibonacci number an satisfies an<2n (except, of course, for a0.

Example 11.6.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, 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.)

  1. Write down a recurrence relation that expresses the population Pn in the nth year relative to the previous year.
  2. Use iteration to determine an expression for the population in the nth year as a formula in n, i, and the initial population P0.
  3. 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.

Example 11.6.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.

(p1p2)((¬p3p1)(p3¬p2))

Example 11.6.12

The set C of constructible numbers can be defined inductively as follows.

Base clause.

Assume 1C.

Inductive clauses.

Whenever a,bC, then so are

a+b,ab,a/b,a.

Whenever a,bC with a>b, then ab 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 2x23x+78 are both constructible numbers.

Example 11.6.13

Consider the following inductively defined set AN.

Base clause.
Assume 32879A.

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.

Example 11.6.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,nN with mn, is m>n or is n>m ?


This page titled 11.6: Exercises is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?