Unit 3 Flashcards
Blank is a method that finds new values using previous values.
Recursion
To denote the nth term you write blank.
a base n
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.
recurrence relation
The initial terms of the sequence are often notated blank or blank.
a base 0 or a base 1
Recursion is a method that finds new values using blank.
previous values
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, …}.
recurrence relation
Recurrence relation defining an blank
a0 = a (initial value)
an = d + an-1 for n ≥ 1 (recurrence relation)
Initial value = a. Common difference = d.
arithmetic sequence
In a blank, each number is obtained by multiplying the previous number by a fixed constant.
geometric sequence
Recurrence relation defining an blank
a0 = a (initial value)
an = r⋅ an-1 for n ≥ 1 (recurrence relation)
Initial value = a. Common ratio = r.
geometric sequence
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.
divide
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.
“common difference.”
Blank is used to express the sum of terms in a numerical sequence
Summation notation
In the summation, the variable k
is called the blank of the summation.
index
In the summation, the variable n
is the blank of the summation.
upper limit
In the summation, The variable s
is the blank
lower limit
A blank for a sum is a mathematical expression that expresses the value of the sum without summation notation.
closed form
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.
value
To change the variables in a summation:
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.
A blank for a sum is a mathematical expression that expresses the value of the sum without summation notation.
closed form
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.
base case
inductive step
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.
mathematical induction
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).
mathematical induction
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 …
inductive step
In the statement “S(k) implies S(k+1)” of the inductive step, the supposition that S(k) is true is called the blank.
inductive hypothesis
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.
inductive proof
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.
inductive step
To be valid, an inductive proof must have a blank and blank.
base case
at least one inductive step
Use induction to prove that a series is equal to a given formula.
Show the base case is true
Assume that if it is true for n then it must be true for n + 1.
Use induction to prove that blank are true.
inequalities
To determine if a blank is valid, verify that the given algebraic equation is equivalent to the given statement.
divisibility proof
Identify which statement is equivalent to the blank.
inductive hypothesis
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”.
inductive hypothesis
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
divisibility statement
Find the base step of an blank by substituting in n = 0 or n = 1.
induction proof
Find the blank of an induction proof by substituting in n + 1.
inductive step
Check that the base and inductive steps of a blank are satisfied.
recurrence proof
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.
explicit formula
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.
inductive steps
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.
strong induction
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.
generalized induction
The blank says that any non-empty subset of the non-negative integers has a smallest element.
well-ordering principle
Use the following three steps to apply the well-ordering principle:
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
The blank f(n) = n! for n ≥ 0 can be defined as:
f(n) = n! = n * (n-1) ….1
factorial function
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.
recursive definition
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.
recursion
blank is the process of computing the value of a function using the result of the function on smaller input values.
Recursion
The basis of a recursive definition is the initial term(s), usually denoted
blank.
f(0)
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.
recursive rule
How to compute the nth value of function defined recursively:
apply the recursive rule to the basis value,
apply the rule to the output, and
repeat as many times as necessary.
The set of all binary strings without any restriction on length (denoted by B*) is an blank.
infinite set
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 = {λ}.
empty string
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.
recursive rule
A blank explicitly states that one or more specific elements are in the set.
basis
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).
recursive rule
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.
exclusion statement
A recursive definition of a set shows how to construct elements in the set by putting together blank.
smaller elements
Components of a recursive definition of a set include what:
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.
A tree has blank (denoted by a circle) and blank (denoted by line segments) which connect pairs of vertices.
vertices
edges
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.
root
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).
number of steps
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.
2n
A blank is an algorithm that calls itself
recursive algorithm
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.
base case
An algorithm’s calls to itself are known as blank.
recursive calls
The base case in an algorithm is the same concept as the basis of a recursive definition. It is the return value for blank.
n=0
The recursive call is the same as the recursive rule of a definition. It is the return value for input greater than the blank.
basis (n≥1)
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.
recursive call
Each number in a sequence defined by a blank recurrence relation is a linear combination of numbers that occur earlier in the sequence.
linear homogeneous
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.
homogeneous
The expression is a sum of terms all of which are a constant times fn-j for some j.
Linear, homogenous
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.
non-linear
All the fn-j terms are multiplied by a constant, so the recurrence relation is linear. However, the +1 term makes the recurrence blank.
non-homogeneous
A recurrence relation is blank if any of the f base n-j
terms are multiplied by non-constants. Otherwise the recurrence is blank.
non-linear
linear
A linear recurrence relation is blank if there are any terms without a f base n-j
.
non-homogeneous
A linear recurrence relation is blank if all of the terms have a
f base n-j
homogeneous
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.
characteristic equation
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).
p(x) = 0
Once the characteristic equation has been determined, the next step is to find all blank that solve the equation.
values of x
The expression denoting the infinite set of solutions to a recurrence relation without initial values is called the blank to the recurrence relation.
general solution
If gn and hn satisfy a linear blank then so does fn = s·gn + t·hn for any real numbers s and t.
homogeneous recurrence relation
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.
golden ratio
