Unit 3

Question 1

Blank is a method that finds new values using previous values.

Answer 1

Recursion

Question 2

To denote the nth term you write blank.

Answer 2

a base n

Question 3

A blank is an equation that expresses a new term using previous terms. To write the equation you need two pieces of information: the initial terms and a rule defining the new term based on the previous term.

Answer 3

recurrence relation

Question 4

The initial terms of the sequence are often notated blank or blank.

Answer 4

a base 0 or a base 1

Question 5

Recursion is a method that finds new values using blank.

Answer 5

previous values

Question 6

A blank is an equation that expresses a new term using previous terms. It includes the intitial terms and the rule to get a new term using only the previous term. For example, a base n = a base n-1 + 3
is the equation for the sequence {7, 10, 13, 16, 19, 22, 25, …}.

Answer 6

recurrence relation

Question 7

Recurrence relation defining an blank
a0 = a (initial value)
an = d + an-1 for n ≥ 1 (recurrence relation)
Initial value = a. Common difference = d.

Answer 7

arithmetic sequence

Question 8

In a blank, each number is obtained by multiplying the previous number by a fixed constant.

Answer 8

geometric sequence

Question 9

Recurrence relation defining an blank
a0 = a (initial value)
an = r⋅ an-1 for n ≥ 1 (recurrence relation)
Initial value = a. Common ratio = r.

Answer 9

geometric sequence

Question 10

To determine if it is a geometric sequence, blank each term by the previous term and compare the quotients. If the quotients of any two consecutive terms are the same, a common ratio exists and the sequence is geometric.

Answer 10

divide

Question 11

Terms in an arithmetic sequence change by a constant amount called the blank. To determine if it is an arithmetic sequence find the differences between each term; if the difference is constant it is an arithmetic sequence.

Answer 11

“common difference.”

Question 12

Blank is used to express the sum of terms in a numerical sequence

Answer 12

Summation notation

Question 13

In the summation, the variable k
is called the blank of the summation.

Answer 13

index

Question 14

In the summation, the variable n
is the blank of the summation.

Answer 14

upper limit

Question 15

In the summation, The variable s
is the blank

Answer 15

lower limit

Question 16

A blank for a sum is a mathematical expression that expresses the value of the sum without summation notation.

Answer 16

closed form

Question 17

You can use a variable to denote the lower or upper limit of a sum; however, the blank of the variable must be provided in order to evaluate the sum.

Answer 17

value

Question 18

To change the variables in a summation:

Answer 18

Find the new initial index by substituting the old initial index into the substitution.
Find the new final index by substituting the old final index into the substitution.
Find the new term by solving substitution for the old variable, and substituting the result into the old term.

Question 19

A blank for a sum is a mathematical expression that expresses the value of the sum without summation notation.

Answer 19

closed form

Question 20

The two components of an inductive proof.

The blank establishes that the theorem is true for the first value in the sequence.

The blank establishes that if the theorem is true for k, then the theorem also holds for k + 1.

Answer 20

base case
inductive step

Question 21

The principle of blank states that if the base case (for n = 1) is true and inductive step is true, then the theorem holds for all positive integers.

Answer 21

mathematical induction

Question 22

Principle of blank

Let S(n) be a statement parameterized by a positive integer n. Then S(n) is true for all positive integers n, if:

S(1) is true (the base case).
For all k ∈ Z+, S(k) implies S(k+1) (the inductive step).

Answer 22

mathematical induction

Question 23

The blank is a compact way to state that an infinite sequence of implications are true:

For all k ∈ Z+, S(k) implies S(k+1)
if and only if
[S(1) implies S(2)] and [S(2) implies S(3)] and [S(3) implies S(4)] and …

Answer 23

inductive step

Question 24

In the statement “S(k) implies S(k+1)” of the inductive step, the supposition that S(k) is true is called the blank.

Answer 24

inductive hypothesis

Question 25

The base of an blank is the first case: n=1 or n=0. It is usually proved by simply substituting in 1 or 0 and validating the result.

Answer 25

inductive proof

Question 26

The blank of an inductive proof is the case that depends on the assumption that the previous steps are true for n and that it is true for n + 1…; or, for all n∈N, f(n) implies f(n+1). Try to think of proofs as a series of if-then statements, e.g., if x is true then it logically follows that y is true.

Answer 26

inductive step

Question 27

To be valid, an inductive proof must have a blank and blank.

Answer 27

base case
at least one inductive step

Question 28

Use induction to prove that a series is equal to a given formula.

Answer 28

Show the base case is true
Assume that if it is true for n then it must be true for n + 1.

Question 29

Use induction to prove that blank are true.

Answer 29

inequalities

Question 30

To determine if a blank is valid, verify that the given algebraic equation is equivalent to the given statement.

Answer 30

divisibility proof

Question 31

Identify which statement is equivalent to the blank.

Answer 31

inductive hypothesis

Question 32

Write the blank as an equivalent algebraic expression. For example, “for every positive integer n, 2 evenly divides 2n” as “for some integer m, 2m=2k”.

Answer 32

inductive hypothesis

Question 33

Use induction to prove that a blank is true.
Show it is true for the base case
Show that if it is true for n then it must be true for n + 1

Answer 33

divisibility statement

Question 34

Find the base step of an blank by substituting in n = 0 or n = 1.

Answer 34

induction proof

Question 35

Find the blank of an induction proof by substituting in n + 1.

Answer 35

inductive step

Question 36

Check that the base and inductive steps of a blank are satisfied.

Answer 36

recurrence proof

Question 37

Prove the blank for a recurrence relation using induction. Show the base case by substituting in n = 0 or n = 1. Next substitute n + 1 into the formula. Algebraically manipulate the result so the case for n is separated. The n case is assumed to be true; now leverage this to show that the remaining parts are true. For recursion, this often means isolating the fn+1 term.

Answer 37

explicit formula

Question 38

The notation used in blank in strong and generalized induction is: for every k≥1,S(0)∧S(1)∧S(2)∧…∧S(k); it means for case from the base of to the kth case.

Answer 38

inductive steps

Question 39

When using blankl, you must assume that the statement is true for n and assume that all the previous cases are also true. That is, you must show that it is true for S(0) and then assume that S(0) through S(k) are true.

Answer 39

strong induction

Question 40

When using blank, you must show the base cases up to the ith case are true and then assume that every case afterwards is true. For example, show that S(0), S(1) and S(3) are true and then assume that S(3) through S(k) are true.

Answer 40

generalized induction

Question 41

The blank says that any non-empty subset of the non-negative integers has a smallest element.

Answer 41

well-ordering principle

Question 42

Use the following three steps to apply the well-ordering principle:

Answer 42

Define a set of counterexamples
Assume the set is not empty; by the well-ordering principle, a minimum element exists
Use the existence of the minimum element to reach a contradiction

Question 43

The blank f(n) = n! for n ≥ 0 can be defined as:

f(n) = n! = n * (n-1) ….1

Answer 43

factorial function

Question 44

In a blank of a function, the value of the function is defined in terms of the output value of the function on smaller input values.

Answer 44

recursive definition

Question 45

One can use the recursive definition for n! to determine the value of the factorial function on a particular value for n by starting at 0, multiplying 0! by 1 to get the value of 1! then multiplying by 2 to get 2!, and so on, until the desired n! has been reached. The process is called blank.

Answer 45

recursion

Question 46

blank is the process of computing the value of a function using the result of the function on smaller input values.

Answer 46

Recursion

Question 47

The basis of a recursive definition is the initial term(s), usually denoted
blank.

Answer 47

f(0)

Question 48

Similar to a recurrence relation, the blank in a function defines how to find the next term using previous terms. It is denoted f(n)
and should be read as the value output for the nth time the recursion rule has been applied.

Answer 48

recursive rule

Question 49

How to compute the nth value of function defined recursively:

Answer 49

apply the recursive rule to the basis value,
apply the rule to the output, and
repeat as many times as necessary.

Question 50

The set of all binary strings without any restriction on length (denoted by B*) is an blank.

Answer 50

infinite set

Question 51

The blank(denoted by the symbol λ) is the unique string whose length is 0. Since B0 is the set of all binary strings of length 0, B0 = {λ}.

Answer 51

empty string

Question 52

The recursive definition of B* does not require using an infinite union of finite sets. The blank constructs a longer string from a shorter string by concatenating 0 or 1. The recursive definition of B* is:

Base case: λ ∈ B*
Recursive rule: if x ∈ B* then,

x0 ∈ B*
x1 ∈ B*
Every binary string can be constructed by starting with λ and repeatedly concatenating 0 or 1 to the end of the string.

Answer 52

recursive rule

Question 53

A blank explicitly states that one or more specific elements are in the set.

Answer 53

basis

Question 54

A blank shows how to construct larger elements in the set from elements already known to be in the set. (There is often more than one blank).

Answer 54

recursive rule

Question 55

An blank states that an element is in the set only if it is given in the basis or can be constructed by applying the recursive rules repeatedly to elements given in the basis.

Answer 55

exclusion statement

Question 56

A recursive definition of a set shows how to construct elements in the set by putting together blank.

Answer 56

smaller elements

Question 57

Components of a recursive definition of a set include what:

Answer 57

A basis that explicitly states one or more specific elements are in the set.
Recursive rules that shows how to construct larger elements in the set from elements already known to be in the set.
An exclusion statement that states that an element is in the set only if it is given in the basis or can be constructed by applying the recursive rules repeatedly to elements given in the basis.

Question 58

A tree has blank (denoted by a circle) and blank (denoted by line segments) which connect pairs of vertices.

Answer 58

vertices
edges

Question 59

Here we give a recursive definition for a particular class of trees called perfect binary trees. Each perfect binary tree has a designated vertex called the blank.

Answer 59

root

Question 60

The blank necessary to construct a perfect binary tree can be determined by counting the height in number of vertices below the root (the root does not count).

Answer 60

number of steps

Question 61

To construct a perfect binary tree, draw the root (a single vertex), and then draw two lines each ending with a vertex. From each of these new vertices, draw two more lines with vertices. Repeat as many times as necessary. Because you are doubling the number of vertices each time, the nth step should have blank vertices.

Answer 61

2n

Question 62

A blank is an algorithm that calls itself

Answer 62

recursive algorithm

Question 63

Like recursively defined sequences and structures, a recursively defined algorithm has a blank in which the output is computed directly on an input of small size or value. On a larger input, the algorithm calls itself on an input of smaller size and uses the result to construct a solution to the larger input.

Answer 63

base case

Question 64

An algorithm’s calls to itself are known as blank.

Answer 64

recursive calls

Question 65

The base case in an algorithm is the same concept as the basis of a recursive definition. It is the return value for blank.

Answer 65

n=0

Question 66

The recursive call is the same as the recursive rule of a definition. It is the return value for input greater than the blank.

Answer 66

basis (n≥1)

Question 67

To determine the output for pseudocode, find the blank value for the basis. Then find the recursive call value of that value and repeat as many times as instructed. Hint: The process is identical to finding values using recursive rules or sequences.

Answer 67

recursive call

Question 68

Each number in a sequence defined by a blank recurrence relation is a linear combination of numbers that occur earlier in the sequence.

Answer 68

linear homogeneous

Question 69

In a blank recurrence relation, there are no additional terms in the expression for fn besides the ones that refer to earlier numbers in the sequence.

Answer 69

homogeneous

Question 70

The expression is a sum of terms all of which are a constant times fn-j for some j.

Answer 70

Linear, homogenous

Question 71

The fn-5 is multiplied by square root of n
which is a function of n and not a constant. Therefore the recurrence relation is not linear.

Answer 71

non-linear

Question 72

All the fn-j terms are multiplied by a constant, so the recurrence relation is linear. However, the +1 term makes the recurrence blank.

Answer 72

non-homogeneous

Question 73

A recurrence relation is blank if any of the f base n-j
terms are multiplied by non-constants. Otherwise the recurrence is blank.

Answer 73

non-linear
linear

Question 74

A linear recurrence relation is blank if there are any terms without a f base n-j
.

Answer 74

non-homogeneous

Question 75

A linear recurrence relation is blank if all of the terms have a
f base n-j

Answer 75

homogeneous

Question 76

While there are mathematical tools to derive the solution to linear homogeneous recurrence relations without resorting to a guess, we know from experience that an exponential function is a good place to start. Plugging in the exponential expression into the recurrence relation, gives rise to an equation called blank for the recurrence. The blank for a linear recurrence relation can be used to solve for x, the base of the exponent in the solution.

Answer 76

characteristic equation

Question 77

In general the characteristic equation for a degree d linear homogeneous recurrence relation will have the form blank, where p(x) is a polynomial of degree d. (The degree of a polynomial is its largest exponent).

Answer 77

p(x) = 0

Question 78

Once the characteristic equation has been determined, the next step is to find all blank that solve the equation.

Answer 78

values of x

Question 79

The expression denoting the infinite set of solutions to a recurrence relation without initial values is called the blank to the recurrence relation.

Answer 79

general solution

Question 80

If gn and hn satisfy a linear blank then so does fn = s·gn + t·hn for any real numbers s and t.

Answer 80

homogeneous recurrence relation

Question 81

The blank describes certain proportions found in natural objects and has been used for thousands of years in man made structures in art and architecture.

Answer 81

golden ratio