1/11
Looks like no tags are added yet.
What is the equation for induction? When can it be used?
[n(n+1)]/2. It c an be used when going to the nth term in a summation
Definition: Method of Induction
Given a statement, it proves the base case and the inductive case
Definition: Base case
Proving the first integer in a summation to be true in terms/equal to the equation of induction
Definition: Inductive case
Proving all consecutive integers also follow the rule that we claim to be true (if we have n, then prove n+1 works as well)
T/F: The equation for induction works for summations going to n+1
False. You would have to take out the n+1 term and add it separately on both sides of the equation
Steps for proof by induction?
1) Prove a base case using the first integer (look at the BOTTOM of a summation)
2) Prove the induction case to be true:
First, assume your proof in k terms (switch out every n for k) is true
Then, mathematically, solve the equation to prove it is true for consecutive integers
What do you HAVE to declare when doing these kinds of proofs?
Where you are using the inductive hypothesis (hew will take off points)
Definition: Telescoping Product
A product in which the denominator of the previous term cancels out the numerator of the next term
Definition: Pre-condition
The initial state of a function
Definition: Post-condition
What is returned after a function
What determines the correctness of a loop?
Variables satisfy the pre-condition/base case, the loop terminates after a finite number of repetitions, and the post-condition (inductive case) is the one we expect
What is considered an “incorrect loop”?
One where a expected input yields an unexpected output (ex/ infinite loop)