Recursive definitions, mathematical induction, and recurrence relations from an intro discrete mathematics course.
30 cards · basic cards · AI-written, checked twice. Edit anything.
- Define a recursive definition.
- A definition consisting of a base case (initial values) and a recursive case (values defined in terms of previously defined values).
- What is a base case in a recursive definition?
- The initial condition that directly defines the function's value for one or more starting points, without reference to other values.
- What is a recursive case?
- The part of a recursive definition that expresses the function's value for an input in terms of its values at smaller or earlier inputs.
- Write the recursive definition of the factorial function.
- 0! = 1; n! = n * (n-1)! for n > 0
- Write the recursive definition of the Fibonacci sequence.
- F(0) = 0, F(1) = 1; F(n) = F(n-1) + F(n-2) for n >= 2
- State the Principle of Mathematical Induction.
- If a property P holds for a base case n = n0, and if P(k) implies P(k+1) for all k >= n0, then P holds for all integers n >= n0.
- What is the base case in a proof by mathematical induction?
- The proof that the statement is true for the initial value (usually n = 0 or n = 1).
- What is the inductive hypothesis?
- The assumption that the statement is true for an arbitrary case n = k, which is used to prove it for n = k+1.
- What is the inductive step in a proof by mathematical induction?
- The proof that if the statement is true for n = k, then it must also be true for n = k+1.
- Define strong induction (also called complete induction).
- A form of induction where the inductive hypothesis assumes the statement is true for all values from the base case up to k, not just k alone.
- What is a recurrence relation?
- An equation that expresses the value of a function at n in terms of its values at one or more smaller inputs.
- What is a closed-form solution to a recurrence relation?
- An explicit formula for the nth term that does not require computing previous terms, usually expressed without recursion.
- Solve the recurrence T(n) = 2*T(n-1), T(0) = 1.
- T(n) = 2^n
- State the Tower of Hanoi recurrence relation and its solution.
- T(n) = 2*T(n-1) + 1, with T(1) = 1; solution is T(n) = 2^n - 1
- What is a homogeneous linear recurrence relation?
- A recurrence of the form a_n = c_1*a_(n-1) + c_2*a_(n-2) + ... + c_k*a_(n-k), where the right side involves only previous terms and constants.