Free Practice Quiz Question List

05 Induction and Recursion Online Quiz Questions

Use this free practice quiz with 20 questions to review 05 Induction and Recursion, test your knowledge, and prepare for your next test or exam.

20 questions

True or false

1 point

True or false: A well-formed recursive definition requires at least a base clause and a recursive clause.

A
True
B
False

Choose one

1 point

Which statement is the well-ordering principle as presented in the material?

A
Every nonempty set of real numbers has a least element.
B
Every nonempty subset of the nonnegative integers has a least element.
C
Every nonempty set of integers, including all integers, has a least element.
D
Every nonempty set of positive rational numbers has a least element.

Choose all

1 point

Select all situations for which the indicated proof method is an appropriate match.

A
Use ordinary induction when proving the next case depends naturally only on the immediately preceding case.
B
Use strong induction when the next case may depend on several earlier cases.
C
Use well-ordering whenever a recursively defined object has two constructors.
D
Use structural induction when proving a property of trees generated by construction rules.

Fill in the blank

1 point

Complete the recursive generation rules for balanced parentheses: the base object is ; one rule forms a new string by ; and another forms one by .

Fill in the blank

1 point

An induction proof has two essential stages: the establishes the starting proposition, and the proves that truth at an arbitrary index implies truth at the next index.

True or false

1 point

True or false: In a least-counterexample proof, choosing the smallest counterexample means that no facts about smaller integers can be used.

A
True
B
False

True or false

1 point

True or false: Structural induction requires an inductive case for each recursive construction rule in the definition of the objects.

A
True
B
False

Choose one

1 point

Which statement correctly describes the principle of ordinary mathematical induction for a proposition P(n) defined for integers n ≥ n₀?

A
Prove P(k+1) directly for one selected value of k.
B
Prove P(n₀), then prove P(k) implies P(k+1) for every k ≥ n₀.
C
Assume P(k+1) and use it to prove P(k).
D
Prove only that P(n₀) is true.

Choose one

1 point

In a recursive definition of a set, what is the purpose of the closure condition?

A
It supplies an additional arbitrary starting object.
B
It replaces every recursive clause with a direct formula.
C
It ensures that only objects generated by the stated rules belong to the collection.
D
It allows any object that resembles a generated object to be included.

Written response

1 point

Using the recursive definition 0! = 1 and (n+1)! = (n+1)n!, what is the value of 4!?

Written response

1 point

The induction formula $1+2+\cdots+n=\frac{n(n+1)}{2}$ holds for n ≥ 1. Using this formula, what is $1+2+\cdots+6$ ?

Written response

1 point

Given the recursive definition F₀ = 0, F₁ = 1, and Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2, what is F₅?

Choose one

1 point

Which set is guaranteed by the well-ordering principle to have a least element whenever it is nonempty?

A
Every nonempty subset of the positive rational numbers.
B
Every nonempty subset of all integers.
C
Every nonempty subset of the nonnegative integers.
D
Every nonempty subset of the real numbers.

Choose one

1 point

Why is strong induction appropriate for proving that every integer greater than 1 has a prime factor?

A
The case k+1 can always be proved without any hypothesis.
B
Only the base case is available in strong induction.
C
All earlier cases can be used, including cases much smaller than k.
D
Strong induction applies only to recursive sets, not integers.

Choose one

1 point

A binary tree is formed by adding a root above two binary subtrees T₁ and T₂. In a structural-induction proof about all such trees, which inductive step is appropriate?

A
Assume the property only for the new root.
B
Assume the property for both immediate subtrees and prove it for the constructed tree.
C
Assume the property for every possible tree without proving a basis.
D
Assume the property only for trees with one leaf.

Choose one

1 point

The recursively defined set of balanced-parentheses strings is closed under concatenation. If (()) and ()() are balanced strings, which option is obtained by concatenating the first string with the second, in that order and with no separator?

A
(()())()
B
(())()()
C
()(())()
D
(())(())

Choose one

1 point

A function is defined recursively by $f(0)=4$ and $f(n+1)=f(n)+2$ for $n\geq 0$ . Which equation correctly gives $f(3)$ ?

A
f(3)=4+2
B
f(3)=4+3
C
f(3)=4+2+2+2
D
f(3)=4\cdot 2^3

Choose all

1 point

Which statements accurately characterize the relationship between induction and recursion? Select all correct choices.

A
Induction can establish a property for all stages by combining an initial case with a propagation argument.
B
Recursion can define an object or value in terms of smaller instances of the same type.
C
A recursive rule by itself proves every property of the objects it generates.
D
An inductive proof must explicitly construct every object to which its conclusion applies.

Written response

1 point

A sequence is defined by $a_0=1$ and $a_{n+1}=2a_n+1$ for $n\geq 0$ . What is $a_4$ ?

Open ended

1 point

Let $a_0=1$ and $a_{n+1}=2a_n+1$ for every $n\geq 0$ . Derive a closed formula for $a_n$ , and prove that your formula is correct for every nonnegative integer $n$ .