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.
Show answer
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?
Show answer
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?
Show answer
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.
Show answer
0! = 1; n! = n * (n-1)! for n > 0- Write the recursive definition of the Fibonacci sequence.
Show answer
F(0) = 0, F(1) = 1; F(n) = F(n-1) + F(n-2) for n >= 2- State the Principle of Mathematical Induction.
Show answer
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?
Show answer
The proof that the statement is true for the initial value (usually n = 0 or n = 1).- What is the inductive hypothesis?
Show answer
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?
Show answer
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).
Show answer
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?
Show answer
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?
Show answer
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.
Show answer
T(n) = 2^n- State the Tower of Hanoi recurrence relation and its solution.
Show answer
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?
Show answer
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.
FlashKeepers